FFTはFFTでも

久々に紙の上の(?)勉強をしてます。
ネタはFFT、高速フーリエ変換です。
ファイナルファンタジータクティクスではありません。
codingの話だから紙の上でないと言われればそれまでですが。
まずはCooley-Tukeyのアルゴリズムから。

ポイントは離散フーリエ変換は、奇数番目と偶数番目の離散フーリエ変換の和で書ける事と、サンプル数の少ない離散フーリエ変換の演算が簡単になることの2点。

サンプルをどんどこ分割していき、例えば長さ1の問題にまで帰結する。このときのフーリエ変換は恒等変換となるので話は簡単だ。この分割の過程によって、データ配列data_iはiをbit反転して昇順に並べたものと交換される。

W^kが因数として共通なものを同じループで処理させることによって計算の効率化を図る。