FFTの大雑把な説明

競プロer向けにFFTの大雑把な説明をします

まちがってるかもしれないけど多目に見てね（見つけたら知らせてくれると助かります）

正確でわかりやすい説明はこの記事を読んで

もっと良い記事→【競プロer向け】FFT を習得しよう！

FFT（高速フーリエ変換）とは、DFT（離散フーリエ変換）を$ O(N \log N)で行うアルゴリズム

まずDFTについて説明する

DFT

数列$ a = (a_0, a_1, \ldots, a_{N - 1})があるとき、これをある数列$ b = (b_0, b_1, \ldots, b_{N - 1})に特殊な重みを付けて重ね合わせたものの平均として表現できる

$ a_i = \frac{1}{N} \sum_{j = 0}^{N - 1} b_j w^{ij}

ここで、$ wは$ N乗して初めて$ 1になるような数（$ 1の原始$ N乗根）

複素数で計算するときは、$ w = e^{\boldsymbol{i}\frac{2\pi}{N}}（$ \boldsymbol{i}は虚数単位）

$ \bmod pで計算するときは$ pの原始根$ gを使って$ w = g^{\frac{p - 1}{N}}（ただし、以下のような制約がある）

$ Nは$ p - 1の約数

$ p = a \times 2^b + 1という形で表せないと計算量が落ちない（要出典）

NTT（数論変換）やFMT（高速剰余変換）と呼ばれる

数列$ bは次のように求められる

$ b_i = \sum_{j = 0}^{N - 1} a_j w^{-ij}

普通に計算すると$ O(N^2)になる

DFTのうれしさ

周波数がわかる！（$ aが時間変化する信号とみた時、$ bは周波数になっている）

畳込みが点積になる！（競プロでは主にこちら）

畳込み定理

数列$ A = (A_0, A_1, \ldots, A_{N - 1})と$ B = (B_0, B_1, \ldots, B_{M - 1})の畳込みとは、長さ$ N + M - 1の数列$ C = (C_0, C_1, \ldots, C_{N + M - 2})であって

$ C_i = \sum_{j = 0}^{i} A_j B_{i - j}

素直に計算すると$ O(N^2)

ここで$ A, B, Cをそれぞれ長さ$ N + M - 1になるように$ 0埋めしてDFTした数列$ \hat{A} = (\hat{A}_0, \hat{A}_1, \ldots, \hat{A}_{N + M - 2}), \hat{B} = (\hat{B}_0, \hat{B}_1, \ldots, \hat{B}_{N + M - 2}), \hat{C} = (\hat{C}_0, \hat{C}_1, \ldots, \hat{C}_{N + M - 2})を考えると

$ \hat{C}_i = \hat{A}_i \hat{B}_i

となるため、$ O(N)で計算できる（実際にはFFTして逆FFTで戻すという操作をするため$ O(N \log N)になる）

FFT

DFTを$ O(N \log N)で計算する、分割統治法っぽいアルゴリズム

競プロ的には、しくみを理解してもあまり旨味はなさそう…

一応説明→FFT (Cooley-Tukey) の式変形

ところで

DFTはフーリエ変換の離散版です

フーリエ変換は

$ f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{\boldsymbol{i} 2\pi \omega t} d\omega

$ F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-\boldsymbol{i} 2 \pi \omega t} dt

というやつ