メモ

yukicoderでゆるふわgolf

FFT

何回見ても非再帰FFTの話が覚えられないのでメモ

1のN乗根をgとする。
f(x)=\sum_{i=0}^{N-1}a_i x^iFFTしたい。
その結果は
\hat{f}(x)=\sum_{i=0}^{N-1}f(g^i) x^i
になる。ということで、全てのiについての f(g^i)が求められればよい。
f(g^i)=\sum_{k=0}^{N-1}a_k g^{ik}
これを頑張って計算する。
ところで、再帰FFTの気持ちには2種類あることをご存じでしたか?ぼくは今知りました。

kの偶奇で分ける

\begin{eqnarray*}
f(g^i)&=&\sum_{k:even}a_k g^{ik}&+&\sum_{k:odd}a_k g^{ik}\\
&=& \sum_{k'=0}^{N/2-1} a_{2k'} g^{i2k'}&+&\sum_{k'=0}^{N/2-1} a_{2k'+1} g^{i(2k'+1)}\\
&=& \sum_{k'=0}^{N/2-1} a_{2k'} (g^{2i})^{k'}&+&g^i \sum_{k'=0}^{N/2-1} a_{2k'+1} (g^{2i})^{k'}\\
&=& f_e(g^{2i})&+&g^i f_o(g^{2i})
\end{eqnarray*}
ということで、fの偶数次の項、奇数次の項のみからなるN/2次の多項式FFTできればよいので再帰的にやればできる

iの偶奇で分ける

\begin{eqnarray*}
f(g^{2i})&=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=N/2}^{N-1} a_k g^{2ik}\\
&=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=0}^{N/2-1} a_{k+N/2} g^{2i(k+N/2)}\\
&=&\sum_{k=0}^{N/2-1}a_k g^{2ik}&+&\sum_{k=0}^{N/2-1} a_{k+N/2} g^{2ik}\\
&=&\sum_{k=0}^{N/2-1}(a_k+a_{k+N/2}) g^{2ik}& &
\end{eqnarray*}
\begin{eqnarray*}
f(g^{2i+1})&=&\sum_{k=0}^{N/2-1}a_k g^{(2i+1)k}&+&\sum_{k=N/2}^{N-1} a_k g^{(2i+1)k}\\
&=&\sum_{k=0}^{N/2-1}(a_k g^k)g^{2ik}&+&\sum_{k=N/2}^{N-1} (a_k g^k) g^{2ik}\\
&=&\sum_{k=0}^{N/2-1}(a_k g^k) g^{2ik}&+&\sum_{k=0}^{N/2-1} (a_{k+N/2} g^{k+N/2}) g^{2i(k+N/2)}\\
&=&\sum_{k=0}^{N/2-1}(a_k g^k) g^{2ik}&+&\sum_{k=0}^{N/2-1}(- a_{k+N/2} g^k) g^{2i(k+N/2)}\\
&=&\sum_{k=0}^{N/2-1}(a_k-a_{k+N/2}) g^k g^{2ik}& &
\end{eqnarray*}
ということで、iが偶数のときは\sum_{k=0}^{N/2-1}(a_k+a_{k+N/2})x^k、奇数のときは\sum_{k=0}^{N/2-1}(a_k-a_{k+N/2})g^k x^kという多項式がそれぞれFFTできればよいので再帰的にやればできる


再帰FFT

iの偶奇で分けるFFTを非再帰にするのは簡単。a_k+a_{k+N/2}(a_k-a_{k+N/2}) g^kを作っていけばいいだけなので。
欲張りにinplaceでやりましょう。適当に、前半にa_k+a_{k+N/2}を、後半に(a_k-a_{k+N/2}) g^kをまとめていくことにする。
とりあえず1回
f:id:sugarknri:20200805112454p:plain
これで前半と後半が別の問題になったので、後半のことは忘れて前半だけに注目してもう1回
f:id:sugarknri:20200805112507p:plain
ところでこうやってやっていくと、前半には「下のbitが0のもの」が、後半には「下のbitが1のもの」が集まっていくことになる。
要するにbit reverseされているので、最後にその辺をうまく並び替えればOK

kの偶奇で分けるFFTも、実は頑張ると非再帰にできる。
解説は省略、原理はこう(再帰でやっていたものをボトムアップにやっていく気持ち)
f:id:sugarknri:20200805162917p:plain


参考にしました
tomorinao.blogspot.com