設要求c=a·b，其中a的第i位為，b、c類似。

從系數序列的角度看，將a表示為系數序列，b、c類似，則根據乘法計算法則，c=a*b（a與b的卷積）。卷積可以通過fft來計算，即C = fft(a*b)=A·B，c=ifft(C)。由于fft的時間復雜度為o(nlog n)，故兩個n位數乘法的時間復雜度為o(nlog n)。

求fft(a)實際上是在求多項式在x=1,,,...,處的值，其中，故也可以從多項式的角度看。

從多項式的角度看，a用多項式表示為。如果能高效地求出a和b對應的多項式x在某n個點處的取值，就能將這幾個點分別對應相乘，求出c對應的多項式在n個點出的取值，再用某種插值算法求出c多項式的系數，即可求出c。通過從系數序列角度啟發，我們知道確實有這樣的n個點，即x=1,,,...,，能夠高效地求出這些點的取值。求出c對應的多項式在這n個點處的取值后，我們又發現當已知?x=1,,,...,?處點的取值時，確實存在高效的插值算法，能求出c多項式的系數。

由多項式求n個特定點取值的算法和由n個特定點取值求多項式系數的算法，利用了復數的性質，本質上跟fft和ifft差不多，所以上面是從兩個角度理解了快速計算大數乘法的原理。

總結

以上是生活随笔為你收集整理的用fft求大数乘法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。