ページ

2015年5月4日月曜日

C++で超シンプルなFFTの実装

Cooley & TukeyによるFFTアルゴリズムの発表から今年でちょうど50年だということに気づいて,久しぶりにFFTを自分で実装してみた.以下は,大浦 先生による有名なFFT (高速フーリエ・コサイン・サイン変換) の概略と設計法1.2 Cooley-Tukey 型 FFTにある最初の分解式(基数2の周波数間引きFFT)を,C++で素直に実装したものだ.できる限りシンプルに記述することだけを考えて,実行速度やメモリ効率はあえて一切気にしていない.

xが入出力の複素数配列.lengthが配列の長さで,2のべき乗数でなければならない.

実装してみて,あまりにもアッサリしたコードになったので驚いた.教科書やWebで見かけるFFTのコードは,配列をインターリーブまたはスプリットして複素数を表現していたり,呼び出し側で与えた有限長の作業領域を使い回したりするために,もう少し複雑になっているものが多い.そういったコードよりは,周波数間引きFFTの本質的な部分をシンプルに表現できているのではないかと思う. 

念のため付記しておくが,パフォーマンスを気にする場合は,こんなウンコードを書いてはいけない.再帰呼び出しによる実装はループによる実装に比べてスタックのpush/popにコストがかかるし,オーバーロード演算 子の利用は一時変数のためのオーバーヘッドの可能性があるし,何より関数内でstd::vectorの領域確保などすべきではない.

0 件のコメント: