乘法计算时间的比较

Question

设a，b为n位数的两个整数。 我想知道a的平方的计算时间是否比a * b短。

谢谢你的帮助。

Answer 1

我不认为有一种方法可以在x86上使用IMUL而不使用IMUL。我可能是错的。

要找出需要多长时间，microbenchmark它！

编辑：哦，等等，我明白了！一个b需要两个内存读取和一个 a需要一个！所以a *更快:-)。

正确答案：没有理由a * b会变慢，除非你有一些外界因素影响事物。

Answer 2

看看the benchmarks in Bentley's "Programming Pearls"，你可以从那里篡改一些东西来衡量。

Answer 3

我认为你的问题是：

*让A，B是两个整数用n个数字。我想知道计算a的平方的计算时间是否比计算a * b的计算时间短。*

如果n足够大以至于不能只使用单个乘法指令，那么任何算法知道可以利用这两个因素相同的事实。对于您在学校学到的算法而言，这是事实，因为几乎一半数字的乘积不需要相乘。在非常大的n的极端，使用与FFT的卷积，这两个因子的FFT对于正方形是相同的，并且只需要计算一次。