2019年10月30日

FFTというものがありまして

それはDFTを高速化するアルゴリズムであり日本語で高速フーリエ変換と言うのだが、字句通りにフーリエ変換を高速で処理するのではない。フーリエ変換は連続世界での話だ。FFTは離散フーリエ変換という離散世界での話なのである。
だがFFTを高速フーリエ変換と言う。分かっている人はそれでいいのである。

というわけで本の例題。CAIディジタル信号処理・コロナ社 にBASICでのプログラムがあったのでC言語に書き換えて試した。 N = 16 で入力信号をインパルスにしたりsin波形にしたりして結果をExcelのフーリエ解析と比較したり・・・・で正しいとする。
N = 65536 とかにしてですね、時間計測した次第である。
さらに同じ処理をPythonでも書いて見た。時間計測した次第である。
そして、PythonのScipyモジュールにあるfft()も使ってみた次第である。時間計測した次第である。
一番速いの   Python + Scipy fft()
二番目 C言語によるFFT
三番目 Pythonによる記述のfft

教科書の例題は高速化を狙ったものではなくてFFTアルゴリズムの解説が主眼だ。これは工夫すればさらに高速化が可能である・・・・かもね。
Python + Scipy のfftは、そもそもモジュールはCかFortranで作られているらしいので高速だわ。単純な教科書例題とは異なり工夫が凝らされているのであろう。基数2のアルゴリズムかどうかも知らないのだが。
Pythonによる記述が遅いのはしゃーない。コンパイラとの違いは出る。

まー学習用にCで書いたりPythonで書いたりしたわけです。移植だけど。

Pythonによる記述のFFTを1とすると、C言語の場合は数100倍ぐらい速い、Scipy fft()はC言語より数10倍速いって感じだった。テキトー

他にC言語によるFFTプログラムは、奥村のアルゴリズム辞典1990年後半かな、というのがあって動かしたら動いたが時間計測はしていない。Codeは眺めたが理解はしていないよん。だいたい人が書いたCode見てコメントも少ないのにどうやって理解しろって。
ずらずらと数字が画面に出たのであるが、これはファイル化してwgnuplotでグラフ出した。

まあしかし、ライブラリを使いましょう、うむうむ。

posted by toinohni at 08:07| 東京 ☀| Comment(0) | ソフト系雑学 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
コチラをクリックしてください