An Effective Programming of GCD Algorithms for Natural Numbers
Arkan Mohammed Al Halidi, Sh. T. Ishmukhametov · Russian Mathematics · 2020
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 approximating algorithm implementation ensuring the value of the reduction coefficient ρ = A i / B i equal or exceeding k where k is a regulated parameter of computation not exceeding the size of a computer word. This approach ensures a significant advantage of our algorithm against the classical Euclidean algorithm.