http://en.wikipedia.org/wiki/Binary_GCD_algorithm
Wikipedia上的条目有一个非常令人不满意的含义：Binary GCD算法一次比标准Euclid算法效率高60％，但是直到1998年Knuth得出结论，他的当代算法的效率仅提高了15％电脑。
再过15年……随着硬件的发展，今天这两种算法又如何堆叠？
二进制GCD在低级语言中是否会继续胜过欧几里得算法，但由于在Java之类的高级语言中的复杂性而使它陷入困境吗？还是现代计算的不同之处？
我为什么在乎你可能会问？我恰好今天必须处理其中的1000亿个：)这是生活在计算时代（可怜的Euclid）的敬酒。
答案当然是“取决于”。取决于我忘记的硬件，编译器，特定的实现。在具有慢除法的机器上，二进制GCD往往胜过欧几里得算法。几年前，我在C，Java和其他几种语言的Pentium4上对它进行了基准测试，总体而言，在该基准测试中，带有256个元素的查找表的二进制gcd比Euclidean算法高1.6到3倍。而不是立即进行除法，而是先进行几轮减法，然后再接近。我不记得这些数字，但是二进制文件仍然要快得多。
如果机器具有快速除法，则情况可能会有所不同，因为欧几里得算法需要较少的运算。如果除法和减法/移位之间的成本差异足够小，则二进制将变慢。在您的情况下哪个更好，您必须通过基准测试来找出答案。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句