java - 现代计算机上的二进制 GCD 算法与欧几里德算法

Question

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

这个 Wikipedia 条目有一个非常不令人满意的含义：二进制 GCD 算法曾经比标准 Euclid 算法效率高出 60%，但直到 1998 年，Knuth 得出结论，他的同时代算法的效率只有 15%。电脑。

又过了 15 年……今天这两种算法如何与硬件的进步相叠加？

二进制 GCD 是否继续在低级语言中优于欧几里得算法，但由于其在 Java 等高级语言中的复杂性而落后？还是现代计算中的差异没有实际意义？

我为什么在乎你可能会问？我今天碰巧不得不处理其中的 1000 亿个 :) 这是为生活在计算时代干杯（可怜的欧几里德）。

Answer 1

答案当然是“视情况而定”。这取决于硬件、编译器、具体实现，无论我忘记了什么。在除法较慢的机器上，二进制 GCD 往往优于欧几里得算法。几年前，我在 Pentium4 上用 C、Java 和其他几种语言对其进行了基准测试，总体而言，在该基准测试中，具有 256 个元素查找表的二进制 gcd 以 1.6 到近 3 倍的倍数击败了欧几里得算法。欧几里得当执行前几轮减法而不是立即除法时，距离更近了。我不记得这些数字，但二进制仍然要快得多。

如果机器具有快速除法，情况可能会有所不同，因为欧几里得算法需要更少的操作。如果除法和减法/移位之间的成本差异足够小，二进制会更慢。在您的情况下哪个更好，您必须通过对自己进行基准测试来找出。