計算RES [I + J] = A [1] * B在NLG（N）[D]

Question

可能重複：
Fast convolution algorithm

我有兩個數組a和b的N長度。我想計算的結果數組

res[i+j] += a[i]*b[j] 

是否有可能比N^2更快地計算這個時間使用FFT或類似的東西。我看到這個問題已經1D Fast Convolution without FFT，但我不知道如何使用FFT做到這一點。

EG: A=[1,2,3],B[2,4,6] 
res[3] = A[1]*B[2]+A[2]*B[1] 

在此先感謝

Answer 1

從我瞭解你想要的FFT算法。 here你有這個算法的實現，也是如何實現FFT算法的一個很好的解釋。