c++で高速フーリエ変換, fft - yattのブログ多倍長演算のプログラムを書くために学習した高速フーリエ変換のメモ。・・・ところでfftでググるとファイナルファンタジータクティクスが出てくるあたり泣ける。 高速フーリエ変換は離散フーリエ変換を高速に行うアルゴリズムで、素直に実装すると再帰的な処理になる。普通は実用の観点から繰り返しのコードにする。その際はビットリバースと呼ばれる操作をして要素を交換した配列を一度に得る。正直何やってるか分からない。多分、インデックス値のビット列を反転させた値をインデックス値とした配列の要素と交換してる。複素数演算をするが、c++ならcomplex STLを使える(complexをインクルード)。stl使うだけで、コードの見通しがかなり改善される。 以下を参考にした。 http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec11-3.html http://
