A study of Euclidean K-Ary Gcd Algorithm

• Antonov, Nikolai Andreevich ^[1] ; Ishmukhametov, Shamil Talgatovich ^[1] ; Arkan, Al Halidi ^[1] ; Maiorova, Mariia Evgenevna ^[2]
  1. [1] Kazan Federal University

     Kazan Federal University

     Rusia

     
  2. [2] KNRTU-KAI, FSBEI
• Localización: Revista Publicando, ISSN-e 1390-9304, Vol. 4, Nº. 13, 2, 2017, págs. 1108-1125
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • The problem of computing the greatest common divisor GCD of natural numbers is one of the most common problems that is solved in modern computational mathematics and its applications. At the moment, many algorithms are known to solve this problem, but every day the requirements for the effectiveness of such algorithms become more stringent. As a result, there is a need to create new algorithms that are more efficient in time and number of the operations performed. Besides, they must allow the possibility of their transformation into modern programming languages while maintaining the efficiency of the algorithm.This article presents an analysis of the realization features and the results of testing the speed of three GCD computation algorithms: the classical Euclidean algorithm, the Sorenson k-ary algorithm, and the approximating k-ary algorithm developed by the second of the authors in MicrosoftVisualStudio in C #. Qualitative and quantitative data on the effectiveness of these algorithms in terms of time and number of the steps within the main cycle are have been obtained.The concluding part of the article contains the analysis of the results obtained, their representation in the diagrams, and gives the recommendations on the choice of the parameters of the methods.

• Referencias bibliográficas
  • DixonJ. ThenumberofstepsintheEuclidean algorithm // Journal of Number Theory. vol. 2, pp. 414–422, 1970.
  • Hardy G. H., Wright E. M. An introduction to the theory of numbers, 4th ed. (Oxford, Calrendon Press), 1959.
  • Ishmukhametov S.T. An approximating k-ary GCD Algorithm, Lobachevskii Journal of Mathematics, vol. 37, Issue 6, pp. 723-728, 2016.
  • Ishmukhametov S.T. Factorization methods of natural numbers // Kazan Federal University, Kazan (rus), 2011.
  • Ishmukhametov S., Mubarakov B., Mochalov A. Euclidian algorithm for recurrent sequences, Applied Discrete Mathematics and Heuristic Algorithms...
  • Sorenson J. An analysis of the generalized binary GCD algorithm / J. Sorenson, A. van derPoorten, A. Stein (Eds.), High Primes and Misdemeanors//...
  • Sorenson J. The k-ary GCD algorithm //Computer Sciences Technical Report. – 1990.
  • Sorenson J. Two fast GCD Algorithms // Journal of Algorithms, vol. 16(1), pp 110–144, 1994.
  • Weber K. The accelerated integer GCD algorithm, ACM Trans.Math.Software, 21, №1, pp. 1–12, 1995.
  • Jebelean T. A Generalization of the Binary GCD Algorithm, Proc. OfIntern.Symp.onSymb.and Algebra, Comp.(ISSAC’93), pp. 111-116, 1993.
  • Wang X., Pan V. Acceleration of Euclidian Algorithm and rational number reconstruction. Siam J. Comp,vol.32,№2, pp. 548-556, 2003.