Geodesic
An effective programming of GCD Algorithms for natural numbers
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2020), pp. 3-8 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study the problem of acceleration of GCD algorithms for natural numbers based on the approximating k-ary algorithm. We suggest a new scheme of the algorithm implementation ensuring the value of the reduction coefficient $\rho=A_i/B_i$ at a stage of the procedure equal or exceeding $k$ where $k$ is a regulating parameter of computation not exceeding the size a computer word. This ensures a significant advantage of our algorithm against the classical Euclidean algorithm.
Keywords: greatest common divisor, Euclidian GCD Algorithm, $k$-ary Algorithm, approximating $k$-ary Algorithm. 
@article{IVM_2020_6_a0,
     author = {Al Halidi Arkan Mohammed and Sh. T. Ishmukhametov},
     title = {An effective programming of {GCD} {Algorithms} for natural numbers},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {3--8},
     year = {2020},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2020_6_a0/}
}
TY  - JOUR
AU  - Al Halidi Arkan Mohammed
AU  - Sh. T. Ishmukhametov
TI  - An effective programming of GCD Algorithms for natural numbers
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2020
SP  - 3
EP  - 8
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/IVM_2020_6_a0/
LA  - ru
ID  - IVM_2020_6_a0
ER  - 
%0 Journal Article
%A Al Halidi Arkan Mohammed
%A Sh. T. Ishmukhametov
%T An effective programming of GCD Algorithms for natural numbers
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2020
%P 3-8
%N 6
%U http://geodesic.mathdoc.fr/item/IVM_2020_6_a0/
%G ru
%F IVM_2020_6_a0
Al Halidi Arkan Mohammed; Sh. T. Ishmukhametov. An effective programming of GCD Algorithms for natural numbers. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2020), pp. 3-8. http://geodesic.mathdoc.fr/item/IVM_2020_6_a0/

[1] Latypov R., Stolov E., Ishmukhametov S., Vlasov I., Galiev A., Prokopyev N., “ARCHAIN: A Novel Blockchain Based Archival System”, 2-d World Conf. on Smart Trends in Systems. Security and Sustainability (October 2018, London, UK)

[2] Sorenson J., The k-ary GCD Algorithm, Tecn. Report, Univ. Wisconsin-Madison, 1990, 20 pp.

[3] Sorrenson J., “Two fast GCD Algorithms”, J. Alg., 16:1 (1994), 110–144 | DOI | MR

[4] Weber K., “The accelerated integer GCD algorithm”, ACM Trans. Math. Software, 21:1 (1995), 1–12 | DOI | MR

[5] Jebelean T., “A Generalization of the Binary GCD Algorithm”, Proc. of Intern. Symp. on Symb. and Algebr. Comp., ISSAC'93, 1993, 111–116 | Zbl

[6] Ishmukhametov Sh. T., Mubarakov B. G., Al-Anni Maad Kamal, “Vychislenie koeffitsientov Bezu dlya $k$-arnogo algoritma nakhozhdeniya NOD”, Izv. vuzov. Matem., 2017, no. 11, 30–38 | MR | Zbl

[7] Ishmukhametov S. T., Rubtsova R. G., “A fast algorithm for counting GCD of natural numbers”, Proc. of intern. conf. Algebra, Anal. and Geometry, KFU, Kazan, 2016 | MR

[8] Ishmukhametov S. T., “An approximating k-ary GCD Algorithm”, Lobachevskii J. Math., 37:6 (2016), 722–728 | DOI | MR