2

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

对我来说最有趣的是： - Lehmer GCD 算法， - 加速 GCD 算法， - k-ary 算法， - 带有 FFT 的 Knuth-Schonhage。我完全没有关于加速 GCD 算法的信息，我只看过几篇文章，其中提到它是在中等输入（~1000 位）上最有效和最快速的 gcd 计算方法

从理论的角度来看，它们看起来对我来说很难理解。任何人都可以分享代码（最好在 c++ 上）实现列表中的任何算法\部分或分享任何这样做的经验。我也将不胜感激任何信息、评论、建议和地方调查。我有一个处理大整数的类，但我没有处理它的方法。当然，除了 Euclid 和 Binary gcd 算法，我现在看起来很清楚；没有问题。最后我想得到的主要内容：实现 lehmer gcd 的代码。（从列表中更容易）

4

2 回答 2

6

Knuth 在《计算机编程艺术》第 2 卷第 4.5.2 节中详细探讨了 GCD 。Knuth 给出了算法 E 为欧几里得的原始方法，算法 A 为欧几里得算法的现代版本，算法 B 为二进制方法，算法 L 为 Lehmer 方法，以及算法 X 中的扩展欧几里得算法。我描述（附代码)原始欧几里得算法、现代欧几里得算法、二进制算法和扩展欧几里得算法在我的博客上。

这篇论文很好地描述了 Schönhage 算法的几个版本，包括代码。

于 2012-05-21T23:12:45.177 回答
0

非常感谢您的回答 user448810。那个二进制算法对我来说是完美的，而且速度很快。我将其转换为非递归形式以节省内存和递归调用。这是我的 longnum 库的实现，为与标准运算符/函数不同的行添加了一些 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-18T11:04:54.010 回答