An effective programming of GCD Algorithms for natural numbers

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.