アルゴリズムの振り分け

これまでで一通りやりたいと思っていたFFT（Fast Fourier Transform）のアルゴリズムのいくつかの整理ができた。それぞれをどのように使い分けるかを考える。

アルゴリズムの振り分け

あと、Raderのアルゴリズム（英語のWikipediaの解説があるけどわかりにくい。こっちの方がまだしもわかったような気になれる）というNが素数の場合に対応する方法があって、こっちはやはり畳み込みを使うけどN-1のFFTに変換されるというものでChirp zよりも効率がいい。ただしNが素数の場合だけにしか使えないのと、Chirp zよりも複雑で難しい（誤り訂正や暗号とよく似た数論の話が出てくる）。ということでRaderのアルゴリズムはとりあえずおいておく。

これで3+1通りのアルゴリズムが手に入った。まとめると

1. Kooley-TukeyのFFT（N=2ⁿ）
2. Chirp z変換（Nは任意）
3. 混合基数（Nは素数以外）
4. 定義式のままのDFT（Nは任意）

である。Chirp z変換は最終的に2の基数の3つのFFTに帰着させるので、Chirp z変換と2の基数のFFTができればとりあえずはすべてのNに対応できる。

Nが小さいとこういう高速化の効果は少ないし、今回の場合Fourier変換を何度も繰り返すわけではないので、小さなNに関しては定義式のままのDFTでやっても差は出ない。

これらをどう使い分けるかは悩ましいけど、例えばこう考えよう。図-3にフローチャートを示す。

フローチャートなんて書いたの何年ぶりだろう、ちょっとへんなところもあるけど。そういえば去年も書いたか。 ようするにまず2のベキかどうかを調べる。この場合一番速く計算できる。そうではない場合には素数かどうかを判定する。NがN₀（実行効率を測定した上で決定する定数）より小さい場合には定義通りに計算する。混合基数の場合にも素因数ごとに、N₀より小さければ定義式のままで、大きければChirp zを使って展開する。

これでは例えば2ⁿ×3のときには2のベキのアルゴリズムは使われないことになる。でもめんどうだからいいよ、これで。

N₀はNが素数の場合に定義通りに計算するのとChirp zを使うのとどちらが速くなるかで決めればいい。定義通りではかけ算回数はN²になって、Chirp zではおおまかには

ぐらい（これ、ほんとかな。桁ぐらいは合ってるだろ）なので、Nが100よりちょっと大きいあたりで逆転する。実際には足し算回数も効くしデータの並び方にもよるので、N₀は実際に実行させてみて実験的に決めよう。