我正在研究快速(次二次)GCD 计算算法并寻找它们的任何细节。我想看看它们的实现，以便有机会更好地理解它们。
Euclid GCD 和 Binary GCD 算法(具有二次运行时间)显然非常简单，我对它们没有任何问题。
我正在寻找的算法是:
• Lehmer GCD 算法，
• 加速GCD算法，
• k元算法，
• 使用 FFT 的 Knuth-Schönhage。
所有这些对我来说都很难理解。任何人都可以与列表中的任何算法的实现共享代码(最好是在 C++ 中)或共享有关如何实现它们的任何提示吗？如果有任何信息、线索或建议，我将不胜感激。
我找不到任何关于加速 GCD 算法的信息。我看到它有时被称为中等输入(~1000 位)上最有效和快速的 gcd 计算方法。
我最感兴趣的是 Lehmer GCD 算法的有效实现(应该是列表中最简单的)。
最佳答案
Knuth 在 The Art of Computer Programming(第 2 卷，第 4.5.2 节)中详细探讨了 GCD。 Knuth给出了算法E作为欧几里德算法的原始方法，算法A作为欧几里得算法的现代版本，算法B作为二进制方法，算法L作为莱默方法，以及算法X中的扩展欧几里得算法。我描述(用代码) original Euclidean algorithm , modern Euclidean algorithm , binary algorithm , 和 extended Euclidean algorithm在我的博客上。
This paper很好地描述了 Schönhage 算法的几个版本，包括代码。
关于algorithm - 大整数的 GCD 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10692994/