FFTのお気持ち理解

DFTを速くやってくれるやつ。繰り返しになる部分を良い感じに処理してくれるのでO(n²)の計算がO(nlogn)が出来てしまう。多倍長乗算に応用されている。

• 離散フーリエ変換の計算法(pdf): 周期間引きというのは周期領域で行の入れ替えをすること
• 離散フーリエ変換を用いた多倍長乗算の話: 多倍長乗算への応用。FFT→内積要素ごとの積→IFFTの順に計算する。
• 任意要素数の高速フーリエ変換 - Qiita: 実装