乘法計算時間的比較

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對於正方形是相同的，並且只需要計算一次。