高速フーリエ変換(FFT)をやっておく

いろいろ調べた中でこのページの大浦さんのFFTがわかりやすかった。
http://momonga.t.u-tokyo.ac.jp/%7Eooura/index-j.html

で、物は試しと基数2の周波数間引きFFTをSSE2で実装。
でも、遅くてとても使い物になりそうもないｗ
大浦さんの基数4複素FFTで大体58秒かかる素数判定プログラムが自前だと88秒かかる。

自分の理想としては周波数間引きと時間間引きでbit反転処理をなくして
多倍長整数の乗算高速化！とか考えているだけに
なんとかしなくちゃってことで基数を4にあげてみることに。

結局、基数4の周波数間引きと時間間引きのbit反転なしのやつを作ってみる。
基数4は難しそうなのでSSE2は使わないで普通にC++で作る。
結果自前プログラムはビット反転処理を抜いた状態で66秒
コンパイルオプションでSSE2を有効にしてやると56秒となかなかの成績。
ちなみに大浦氏のFFTをSSE2オプションでコンパイルすると51秒とめちゃはやっ！
ただ、learningバージョンということで自作FFTはあんまり最適化してない状態だから
もしかしてSSE2だけでとかうまくしたらもっと早くなるかな・・
まっ無理かなｗ

><