重複の可能性:
高速畳み込みアルゴリズム
長さ N の 2 つの配列 a と b があります。結果配列を次のように計算したい
res[i+j] += a[i]*b[j]
FFTまたはN ^ 2よりも速い時間で同様のものを使用してこれを計算することは可能ですか? この質問はすでにFFT なしの 1D Fast Convolutionを見ましたが、FFT を使用してそれを行う方法がわかりません。
EG: A=[1,2,3],B[2,4,6]
res[3] = A[1]*B[2]+A[2]*B[1]
前もって感謝します