Эффективное программирование процедуры вычисления НОД натуральных чисел

Изучается проблема ускорения вычисления наибольшего общего делителя натуральных чисел на основе аппроксимирующего $k$-арного алгоритма. Предложена схема реализации аппроксимирующего алгоритма, обеспечивающая значение коэффициента редукции рассматриваемых чисел $A_i/B_i$ не меньше $k$, где $k=2^s$ — регулируемый параметр вычисления, не превышающий размер машинного слова. Такой подход обеспечивает значительное преимущество нашего алгоритма по отношению к классическому алгоритму Евклида.