Алгоритмы GCD для больших целых чисел

Question

Я ищу информацию о быстрых алгоритмах вычисления GCD. В частности, я хотел бы взглянуть на реализацию этого.

Самый интересный для меня: - Лехмер НОД алгоритма, - Ускоренный алгоритм НОДА, - к-кратного алгоритма, - Кнут-Шёнхаг с FFT. У меня нет НИКАКОЙ информации об ускоренном алгоритме GCD, я только что видел несколько статей, где он упоминался как самый эффективный и быстрый метод вычисления gcd на входах среды (~ 1000 бит)

Они выглядят очень трудно меня понять из теории. Может ли кто-нибудь поделиться кодом (желательно на C++) с реализацией любого алгоритма \ частей из списка или поделиться опытом. Я также буду признателен за любую информацию, комментарии, советы, места для изучения. У меня есть класс для работы с большими целыми числами, но у меня нет методов для работы с ним. За исключением, конечно, алгоритмов Euclid и Binary gcd, которые сейчас мне кажутся ясными; с этим нет никаких проблем. Главное, что я хотел бы получить в конце: код реализации lehmer gcd. (это проще в списке)

Answer 1

Кнут исследует GCD по-прежнему в Искусство компьютерного программирования, том 2, раздел 4.5.2. Кнут дает алгоритм Е как исходный метод Евклида, Алгоритм А как современную версию алгоритма Евклида, Алгоритм В как двоичный метод и Алгоритм L как метод Леммера, а также расширенный евклидово алгоритм в Алгоритме X. Я описываю (с кодом) original Euclidean algorithm, modern Euclidean algorithm, binary algorithm и extended Euclidean algorithm в моем блоге.

This paper дает хорошее описание нескольких версий алгоритмов Nhage Sch ö, включая код.

Answer 2

благодарит за ваш ответ user448810. Этот бинарный алгоритм идеально подходит для меня и быстро распространяется. Я конвертирую его в нерекурсивную форму для сохранения вызовов памяти и рекурсии. Вот моя реализация для моего longnum Lib, добавил некоторые бэр для линий, которые отличаются от стандартных операторов/функций

longnum gcd(longnum x,longnum y) 
    { 
    x.sig=+1; x.integer(); // x=abs(int(x)) 
    y.sig=+1; y.integer(); // y=abs(int(y)) 
    longnum z; int x0,y0,sh=0; 
    for (;;) 
     { 
     if (x.iszero()) { z=y; break; } // if (!x) ... 
     if (y.iszero()) { z=x; break; } // if (!y) ... 
     x0=x.a[_longnum_a1]&1; // x0=x&1 
     y0=y.a[_longnum_a1]&1; // y0=y&1 
     if ((!x0)&&(!y0)) { x>>=1; y>>=1; sh++; continue; } 
     if (!x0) { x>>=1; continue; } 
     if (!y0) { y>>=1; continue; } 
     if (x<y) y-=x; 
     else  x-=y; 
     } 
    return (z<<sh); 
    }