|
An effective programming of GCD Algorithms for natural numbers
Al Halidi Arkan Mohammed, Sh. T. Ishmukhametov Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Abstract:
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.
Received: 09.07.2019 Revised: 20.09.2019 Accepted: 25.09.2019
Citation:
Al Halidi Arkan Mohammed, Sh. T. Ishmukhametov, “An effective programming of GCD Algorithms for natural numbers”, Izv. Vyssh. Uchebn. Zaved. Mat., 2020, no. 6, 3–8; Russian Math. (Iz. VUZ), 64:6 (2020), 1–5
Linking options:
https://www.mathnet.ru/eng/ivm9576 https://www.mathnet.ru/eng/ivm/y2020/i6/p3
|
Statistics & downloads: |
Abstract page: | 211 | Full-text PDF : | 101 | References: | 18 | First page: | 5 |
|