设 a, b 是两个 n 位整数。我想知道a平方的计算时间是否比a * b短。
谢谢您的帮助。
问问题
85 次
3 回答
1
我认为没有办法在 x86 上不使用 IMUL 就可以对 A 进行平方。我可能是错的。
要了解某件事需要多长时间，请对其进行微基准测试！
编辑：哦，等等，我明白了！a b 需要两次内存读取，而 a a 需要一次！所以 a*a 更快:-)。
正确答案：没有理由 a*b 会变慢，除非你有一些外部因素影响事物。
于 2010-07-08T03:29:44.937 回答
1
我假设你的问题是：
*令 a, b 为两个 n 位整数。我想知道计算 a 平方的计算时间是否比计算 a*b.* 的计算时间短
如果 n 足够大以至于您不能只使用单个乘法指令，那么我知道的任何算法都可以利用两个因素相同的事实。对于您在学校学习的算法而言，情况确实如此，因为几乎一半的数字对乘积不需要相乘。在非常大的 n 的极端情况下，使用 FFT 卷积，两个因子的 FFT 对于平方是相同的，并且只需要计算一次。
于 2014-03-30T00:56:53.540 回答
0
看看Bentley 的“Programming Pearls”中的基准，你可以从那里破解一些东西来测量。
于 2013-01-23T00:30:34.643 回答