二进制GCD算法对欧几里德的算法在现代计算机

http://en.wikipedia.org/wiki/Binary_GCD_algorithm 二进制GCD算法对欧几里德的算法在现代计算机

此维基百科条目有一个非常不满意的含义：二进制GCD算法是在同一时间高达60％，比标准的Euclid算法更高效，但作为迟到1998年，Knuth得出结论，他的现代计算机的效率只有15％的提高。

那又过了15年......这两种算法今天如何在硬件方面取得进步？

是否二进制GCD继续优于欧氏算法低级语言但憔悴的背后原因是它在高级语言如Java的复杂性？或者在现代计算中有什么不同？

为什么我关心你可能会问？我恰好需要今天处理1000亿个这样的东西:)这是一个生活在计算时代（可怜的欧几里得）的干杯。

来源

2011-11-19 jkschneider

你可以有一个规范标准测试他们，就像在一个for循环（对于1000例如大小）创建随机数的列表，然后对所有对数的计算二进制，而在另一个循环计算欧几里得最大公约数，什么是问题？国际海事组织，仍然在现代计算机二进制应该是更快的数字更大。 –

我可以，而且这对于特定OS上的特定处理器上的特定语言来说是相当有代表性的。这是一种常见的数字操作，我更加普遍地好奇今天在高性能应用中首选的解决方案。 – jkschneider

如果你今天做100十亿，任何时间花在辩论最有效的解决办法是要花费你更多的时间损失比简单地执行一个或另一个会一直。 –

答案当然是“看情况”。这取决于硬件，编译器，具体实现，不管我忘了。在划分较慢的机器上，二进制GCD的性能优于欧几里得算法。我在基准几年前基准它在C，Java和其他一些语言的Pentium4，总体而言，有256元的查找表二进制GCD 1.6和近3之间的欧几里德的因素击败欧几里德算法靠近而不是立即分开时，首先进行了几轮减法。我不记得数字，但二进制仍然快得多。

如果机器有快速除法，事情可能会有所不同，因为欧几里德算法需要更少的操作。如果划分和减法/移位之间的成本差异足够小，二进制将会变慢。在你的情况下哪一个更好，你必须通过标杆来找出自己。

来源

2011-11-19 13:02:23

二进制GCD算法对欧几里德的算法在现代计算机

回答

相关问题