任意要素数の高速フーリエ変換 - Qiita目的・方法 よく紹介されているFFT(高速フーリエ変換)のアルゴリズムでは、要素数が2の冪乗のCooley-Tukey法が使われている。これを使って要素数が2の冪乗でないデータをフーリエ変換しようと思うと、要素数より大きい最小の2の冪乗を求め、配列を生成し、データを移し、ゼロ埋めしてFFTしなければならない。また、ゼロ埋による副作用も考えなくてはならない。任意の要素数の配列をそのまま扱えたほうが、FFTを使う側としては楽である。 Cooley-Tukey法は、要素数が合成数ならば使える。サンプル数が素数のときは、レーダーのアルゴリズムがある。これを組み合わせて、任意要素数のFFTのプログラムを書く。 DFT(離散フーリエ変換)とは サンプル数nのデータ列 $x[i]$ から以下の演算をして、$y[i]$を得る。 ここで $\omega_n = e^{2 \pi i/n}$ である。 この計
