大整数的GCD算法

我正在寻找有关快速GCD计算算法的信息。特别是，我想看看它的实现。大整数的GCD算法

最有趣的对我来说： - 莱默GCD算法， - 加速GCD算法， - K进制算法， - 克努特-Schonhage与FFT。我完全没有关于加速GCD算法的信息，我刚刚看到一些文章，它被提及作为中等输入（〜1000位）上最有效和快速的gcd计算方法

他们看起来很难我从理论的角度来理解。任何人都可以分享代码（最好在C++）与实现列表中的任何算法\部分或共享任何这样做的经验。我也很乐意提供任何信息，意见，建议，地点进行调查。我有一个班级来处理大整数，但我没有办法处理它。除了当然，欧几里德和二进制gcd算法，目前看起来很清楚;它没有问题。我想最终得到的主要内容是：实现lehmer gcd的代码。（这是从列表中更容易）

来源

2012-05-21 Mikhail Kalashnikov

哇，这是一个为第一个问题真的好线。不幸的是，我不认为我们大多数人都知道答案。知道有人看到这件事可能需要一点点时间。抱歉! :( –

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的算法，包括代码的很好的描述。

来源

2012-05-21 23:12:45 user448810

非常感谢您的回答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); 
    }

来源

2013-08-18 11:04:54 Spektre

这是什么语言？ – vy32

@ vy32'C++'和'longnum'类是我的一个固定点，所以任何非标准操作都会被注释掉 – Spektre

大整数的GCD算法

回答

相关问题