GCD算法大整数(GCD algorithms for a large integers)

我在寻找有关快速GCD计算算法的信息。 特别是，我想看看的，该变现。

最有趣的对我来说： - 莱默GCD算法 - 加速GCD算法， - K进制算法， - 克努特-Schonhage与FFT。 我已经完全对加速GCD算法没有信息，我只看到其中提及的最有效和快速的GCD计算方法在介质输入（〜1000位）的几篇文章

他们看起来更困难，我从理论观点理解。 有谁请与实现列表中的任何算法\零件的共享代码（基于C ++最好）或共享这样做的任何经验。 我也将感激的任何信息，意见，建议，地方看看。 我有一类具有大整数工作，但我没有方法与它合作。 除此之外，可以肯定，欧几里得和二进制GCD算法，这是看起来很清楚，我现在; 有与它没有任何问题。 最主要的我想最终获得：实现莱默GCD的代码。 （这是比较容易从名单）

Answer 1:

克努特探索在长度计算机程序设计 ，第2卷，第4.5.2节的艺术的GCD。 克努特给出算法E为欧几里得的原始方法，算法A作为现代版欧几里德的算法，算法B作为二进制方法和算法L，以莱默方法，以及在算法X的扩展欧几里德算法我介绍（附代码）的原欧几里德算法 ，在现代欧几里德算法中， 二进制算法和扩展欧几里德算法在我的博客。

本文给出了几种版本的Schönhage的算法，包括代码的一个很好的说明。

Answer 2:

非常感谢您的回答user448810。 二进制算法非常适合我，再用快。 我把它转换成非递归形式，以节省内存和递归调用。 这是我实现我的longnum lib中，增加了一些REMS的是有关标准的运营商/功能不同线路

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);
    }

文章来源: GCD algorithms for a large integers