以下是引用beyondyf在2012-10-3 16:47:59的发言:
本来是串门的,结果到处见这小哥的文章(之前刚去了趟数据结构与算法版块)。
大整数的分治法运算倒不是什么新鲜东西,而且我决定回贴也主要是因为Z版说对了它的时间复杂度。
直接按你想的去计算并不比小学式计算来的快。
给你一点提示,要想改进算法的效率,还需要优化一下计算步骤。目前我能做到的是将时间复杂度降到O(N^log(3))
提个问题,不必回答给我。目前主流芯片的乘法、加法、移位指令的指令周期是多少?(多少个机器周期)
目前主流芯片的乘法、加法、移位指令的指令周期是多少?(多少个机器周期)
具体的不好说 而且对于目前的CPU一条指令到底用多少时间跟很多东西有关 没法一概而论 简单的讲 对于我们用的X86等不是专门用来计算的芯片来说 加减 移位最快 可以认为就是1个指令周期 乘法的话 貌似在比较新的CPU上面 也就是得是core以上了 貌似也是1个周期 不过延迟大 也就是说 实际可能还是慢 延迟 如果能用一些东西消除的话可以没影响 不过一般还是有影响的罢。。
除法是大问题 老的CPU 除法大约要100个周期 现在的CPU也得大约50个 具体跟精度有关 但最快好像也得十来个 二十来个时钟周期 是比较慢的