FFTの速度
普通のPCでいろいろなFFTルーチンの速度比較をしているサイト。
FFTで掛け算の回数が最小になるのは基数２だけのときで、３や５が混ざると掛け算の回数が増えて効率が悪くなる。なので普通FFTするときは基数２だけにしようとするわけだが、なんと上のサイトの結果をみると普通のPCの場合基数３が混ざった方が速い場合がある！ことがわかる。
どの比較を見ても、ある程度データサイズが小さいときは基数２のみの場合の方が高速だけど、ある程度以上大きなデータになると基数３が混ざってる方に逆転されてしまっている。これは多分、普通のPCではメインメモリはCPUキャッシュメモリに比べて遙かに遅い速度でしか動いてないので、データ転送するより掛け算する方が速いという事態が発生していることによるのだろう。
つまり、基数２だけだと確かに掛け算の回数は少なくてすむけど、その分データ転送が増えている（掛け算の組み合わせを変える回数が増える）わけで、そのデータ転送よりも基数３のために余計な掛け算を計算する方が速いために、全てのデータがキャッシュメモリに収まりきらないサイズになると、メインメモリとのデータ転送コストが無視できなくなって逆転が発生しているのだと考えられる。
うーん、今までこんな事全然気にしてなかったぞ。
もしこれが本当だとすると、CPUキャッシュメモリサイズとメインメモリバンド幅によって最適な基数の組み合わせが変わってくるので、自分の使ってるシステムでどういう基数が最適か一度チェックしておく必要がありそうだ。
FFTをばしばし使うプログラムの場合、実行時間のほとんどはFFTに食われているだろうから、FFTの効率を上げることができれば全体の高速化にかなり貢献することになるだろう。
追記
上に書いたことは勉強不足だったので追記。
基数に2以外のものが混ざった方が速いというのは単にメモリサイズだけの話ではなくて、足し算も含めて演算回数をちゃんと見積もってやると実際にアルゴリズム的に速くなる場合がある。（最近の計算機は掛け算も足し算も同じくらいのコストだからちゃんと足し算のことも考慮する必要がある。）
Cooly-Tukey型FFTの場合の計算量については、次のサイトが参考になる。
でもこの説明だと基数に３や５が入ったときは遅くなっているので、もしかすると基数３を入れる方が速くなるような何か別のアルゴリズムがあるのかもしれない。
でもCPUキャッシュの影響は相当大きいようなので、最も効率の良い基数を探すにはやはり試行錯誤する必要がありそうだ。
また、基数２だけの変換のときでも奇数部だけは基数４で扱うなんていうアルゴリズムもあるようだ。
今までFFTのアルゴリズムなんてCooly-Tukeyの一番基本的なもの以上のことはほとんど意識してなかったけど、奥が深いね…。
