1.2 Cooley-Tukey 型 FFT FFT が一般に知られるようになったのは,1965 年の J.W.Cooley と J.W.Tukey による短い論文からです [参考文献].それ以前にも, 一部の人たちは FFT の算法について気づいていたようですが,広く 知られることはありませんでした.FFT があまり知られていなかったころは, 長さ N の離散 Fourier 変換を計算するためには N^2 回の計算が必要であると 信じられていました.しかし,FFT を用いると N*log(N) に比例する計算で 済みます.この違いは具体的には,一秒間に 10^9 回の演算ができる コンピュータで N=2^30 の離散 Fourier 変換を実行した場合に,30 年と 3 分の違いになります.この FFT の基本原理はコロンブスの卵的な発想で, 一言でいえば大きな問題を計算が楽な小さな問