大整數的GCD算法

Question

我正在尋找有關快速GCD計算算法的信息。 特別是，我想看看它的實現。

最有趣的對我來說： - 萊默GCD算法， - 加速GCD算法， - K進制算法， - 克努特-Schonhage與FFT。 我完全沒有關於加速GCD算法的信息，我剛剛看到一些文章，它被提及作爲中等輸入（〜1000位）上最有效和快速的gcd計算方法

他們看起來很難我從理論的角度來理解。 任何人都可以分享代碼（最好在C++）與實現列表中的任何算法\部分或共享任何這樣做的經驗。我也很樂意提供任何信息，意見，建議，地點進行調查。我有一個班級來處理大整數，但我沒有辦法處理它。除了當然，歐幾里德和二進制gcd算法，目前看起來很清楚;它沒有問題。 我想最終得到的主要內容是：實現lehmer gcd的代碼。 （這是從列表中更容易）

Answer 1

Knuth探索長度在計算機編程藝術，第2卷，4.5.2節的長度。 Knuth給出算法E作爲Euclid的原始方法，算法A作爲歐幾里德算法的現代版本，算法B作爲二進制方法，算法L作爲萊默方法，以及算法X中的擴展歐幾里德算法。我描述了（用代碼）original Euclidean algorithm,modern Euclidean algorithm,binary algorithm和extended Euclidean algorithm在我的博客。

This paper給出了幾種版本的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); 
    }