On a new algorithm for computing GCD of integer numbers

Article Sidebar

Trends in Computer Science and Information Technology volume5-issue1 articles
PDF HTML
Submitted: June 22, 2020
Published: Jul 6, 2020
DOI: 10.17352/tcsit.000013

Main Article Content

ST Ishmukhametov*
Professor of Kazan Federal University, 420008, Kremlevskya st. 35, Kazan, Russia
BG Mubarakov
Assistant professor of Kazan Federal University, 420008, Kremlevskya st. 35, Kazan, Russia
RG Rubtsova
postgraduate student of the Department of Computer Mathematics, Kazan Federal University, 420008, Kremlevskya st. 35 Kazan, Russia
Al Khalidi Arkan Mohammed
Assistant professor of Kazan Federal University, 420008, Kremlevskya st. 35 Kazan, Russia

Abstract

In the paper we give an introduction to a new algorithm counting the greatest common divisor (GCD) of natural integers called the approximating GCD algorithm introduced by S.Ishmukhametov in 2016. We compare it with the classical Euclidean GCD algorithm and the kary GCD algorithm in spirit of J. Sorenson and K. Weber and outline their advantages and disadvantages.

Downloads

Download data is not yet available.

Article Details

Ishmukhametov, S., Mubarakov, B., Rubtsova, R., & Mohammed, A. K. A. (2020). On a new algorithm for computing GCD of integer numbers. Trends in Computer Science and Information Technology, 5(1), 015–017. https://doi.org/10.17352/tcsit.000013
Short Communications

Copyright (c) 2020 Ishmukhametov ST, et al.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Knuth D (1998) The Art of Computer Programming. 2. Link: https://bit.ly/3itivu2

Stein J (1967) Computational problems associated with Racah algebra. Journal of Computational Physics 1: 397-405. Link: https://bit.ly/2D9bcrr

Sorenson J (1994) Two fast GCD Algorithms. J Alg 16: 110-144. Link: https://bit.ly/31It9r1

Weber K (1995) The accelerated integer GCD algorithm. ACM Trans Math Software 21: 1-12 . Link: https://bit.ly/2Z07GrY

Jebelean T (1993) A Generalization of the Binary GCD Algorithm. Proc of Intern Symp on Symb and Algebr Comp (ISSAC’93) 111-116. Link: https://bit.ly/2VK2fv4

Ishmukhametov ST (2016) An approximating k-ary GCD Algorithm. Lobachevskii Journal of Mathematics 37: 723-729. Link: https://bit.ly/2ZBEMNJ

Ishmukhametov ST, Mubarakov BG, Al-Anni KM (2017) Calculation of Bezout’s Coefficients for the k-Ary Algorithm of Finding GCD, Russian Mathematics Allerton Press Inc 61: 26-33. Link: https://bit.ly/2O065vD

Al-Khalidi Arkan M (2020) Effective Computations of Inverse by Module Elements with Approximating K-Ary GCD Algorithm by Ishmukhametov. IOP Journal of Physics 1350: 1-7. Link: https://bit.ly/2ZE3YTV

Al-Khalidi Arkan M, Ishmukhametov ST (2020) Effective programming of the GCD procedure for natural numbers, Russian Mathematics 3-8.