jks*_*der 12 java algorithm math numerical-analysis number-theory
http://en.wikipedia.org/wiki/Binary_GCD_algorithm
此维基百科条目有一个非常不满意的含义:二进制GCD算法是在同一时间高达60%,比标准的Euclid算法更有效,但迟至1998年克努特的结论是,只有在效率15%的涨幅对他的当代电脑.
还有15年过去了......今天这两种算法如何与硬件的进步相结合？
二进制GCD在低级语言中是否继续优于欧几里得算法,但由于其在Java等高级语言中的复杂性而萎缩？或者是现代计算的差异？
我为什么关心你可能会问？我今天碰巧需要像今天的1000亿这样处理:)这是一个生活在计算时代(糟糕的欧几里德)的干杯.
答案当然是"它取决于".这取决于硬件,编译器,具体实现,无论我忘记了什么.在具有慢速划分的机器上,二进制GCD倾向于优于欧几里德算法.几年前我用C,Java和其他一些语言对Pentium4进行了基准测试,总体而言,在该基准测试中,带有256个元素查找表的二进制gcd比欧几里德算法高出1.6到3之间的欧几里德.欧几里德当不是立即分开时,更接近,首先进行几轮减法.我不记得这些数字,但二进制仍然相当快.
如果机器具有快速划分,则事情可能不同,因为欧几里得算法需要较少的操作.如果除法/减法/移位之间的成本差异足够小,则二进制将更慢.在你的情况下哪一个更好,你必须通过自己的基准测试找出答案.
| 归档时间： |
|
| 查看次数： |
1776 次 |
| 最近记录： |