大整数的GCD算法
我寻找关于快速GCD计算算法的信息。特别是，我想看看这一点的实现。
我最感兴趣的是：- Lehmer GCD算法，-加速GCD算法，- k-ary算法，- Knuth-Schonhage和FFT。我完全没有关于加速GCD算法的信息，我只看过一些文章，其中提到它是在介质输入(~1000位)上最有效和最快速的gcd计算方法。
从理论上看，它们对我来说很难理解。任何人可以分享代码(最好是在c++上)和实现列表中的任何算法\部分或分享任何这样做的经验。我也将感谢任何信息，评论，建议，地方看。我有一个处理大整数的类，但我没有处理它的方法。除了Euclid和二进制gcd算法之外，这对我来说现在看起来很清楚；它没有问题。我最终想要得到的主要内容是:实现lehmer gcd的代码。(从列表中选择更容易的)
回答 2
Stack Overflow用户
发布于 2012-05-22 07:12:45
Knuth在计算机编程艺术中详细探讨了GCD，第2卷，第4.5.2节。Knuth给出了算法E作为欧几里得的原始方法，算法A作为欧几里得算法的现代版本，算法B作为二进制方法，算法L作为莱默方法，以及算法X中的扩展欧几里德算法。我在我的博客中描述(用代码) original Euclidean algorithm，modern Euclidean algorithm，binary algorithm和extended Euclidean algorithm。
This paper很好地描述了Schönhage算法的几个版本，包括代码。
Stack Overflow用户
发布于 2013-08-18 19:04:54
非常感谢你的回答，user448810。这个二进制算法对我来说是完美的，而且速度非常快。我将其转换为非递归形式，以节省内存和递归调用。这是我对longnum lib的实现，为与标准运算符/函数不同的行添加了一些rem
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);
}https://stackoverflow.com/questions/10692994
复制相似问题
腾讯云开发者
