はじめに
フーリエ変換は自然科学や信号処理など、広い分野で用いられています。競技プログラミングでも畳み込みの計算を高速に実行するツールとしてよく利用されます。この記事は離散フーリエ変換を高速で実行する高速フーリエ変換(FFT)のコアとなるアイデア部分の備忘録です。
設定
長さNの配列 A = [A[0],...,A[N-1]]の離散フーリエ変換
\mathcal{F}_N(A)[k] = \sum_{j=0}^{N-1} A[j] e^{2\pi i\frac{jk}{N}} \qquad (k=0,...,N-1)
を計算する。簡単のためNは2のべき乗であるとする。配列のインデックスは[]で表す。
計算
和を偶奇に分けることで
\mathcal{F}_N(A)[k] = \sum_{j=0}^{N/2-1} A[2j] e^{2\pi i\frac{2jk}{N}}
+ \sum_{j=0}^{N/2-1} A[2j+1] e^{2\pi i\frac{(2j+1)k}{N}}
と書ける。Nは偶数であることに注意。変形すると
\begin{align}
\mathcal{F}_N(A)[k] &= \sum_{j=0}^{N/2-1} A[2j] e^{2\pi i\frac{jk}{N/2}}+ e^{2\pi i\frac{k}{N}}\sum_{j=0}^{N/2-1} A[2j+1] e^{2\pi i\frac{jk}{N/2}} \\
&=\mathcal{F}_{\frac{N}{2}}(A_\text{even})[k] + e^{2\pi i\frac{k}{N}}\mathcal{F}_{\frac{N}{2}}(A_\text{odd})[k]
\end{align}
となる。$A_\text{even}$はAの偶数番目を取り出した配列(python風にはA[::2])、$A_\text{odd}$はAの奇数番目を取り出した配列(python風にはA[1::2])である。
この表式より、再帰的に半分の大きさの配列でのFFTに帰着できるため、一つのkに対して$O(\log N)$の計算量で離散フーリエ変換値を得られる。定義に従って愚直に和を取った場合は$O(N)$なのでかなり高速。
その他
- 配列の長さが2ベキじゃないときは0埋めで次数調整。(と書いてあるところが多いけどだめだよね？)
- 配列の長さがmの倍数の時は和をmod mで分ければ同じことができる。
- その他モダンな高速化が多々開発・実装されているので、素直にライブラリを使うべし。