(1)高速フーリエ変換 E.PRAN 今井・宮川訳 科学技術出版 1978年 Fortranプログラムが合ったのでC言語に書き換え
(2)CAIディジタル信号処理コロナ社 2000年頃 BASICプログラムがあったのでC言語に書き換え
(3)C言語による科学技術計算 小池・CQ出版 1990年頃 C言語によるプログラムがあったので写経
(4) アルゴリズム辞典・奥村 技評 第18版 1998年頃、サイトからC言語FFTをダウンロード
と、いくつか動かしてみたので写経がうまくなったりして(笑)
データ数 65536で比較して(2),(3),(4)は同等で(1)が一番遅い。5倍ぐらい違う。これの原因はFFTのアルゴリズムにある・・・・はずだが、今の所、違いはShufflingの処理だなあ。一括して実行するか、毎回実行するか。
2のべき乗計算でpow(2,4)っての使うよりはShift Leftが速いと体験したである。他にCの配列を使うのかポインターでやるのか・・・違いが出るかどうか知らんです。
奥村アルゴリズム辞典では三角関数もテーブル作ってたな。それで高速になるのかどうか知らないが。
まー上の本は40年昔の、30年ぐらい昔の・・・・なんでして。当時のパソコンの性能と今のパソコンの性能は雲泥の差ですからね。
こんなに高速になったらFFT使わなくてもいいんじゃ? DFTを単純に計算しても相当に速いのだぜ。。。つーか、データ数が128とかだったらDFTもFFTも大差はなかろうよ。うむうむ。
で、実はFFTは大事なのであるね。それ素晴らしいあるよ。現在の電子機器、特に通信・放送は符号理論とデジタル信号処理のカタマリなのである。デジタル信号処理の根幹はFFTである。これは実は単純に時間軸と周波数軸の行き来をするという用途だけではないのである。
OFDMではIFFTのアルゴリズムが使えるのである。高速計算は大事なのである。なんちて。
さてと、20年から40年ぐらい昔の本を読んだので次は10年ぐらい昔から現在までの本を探す。ディジタル信号処理技術を知るとね、ド素人相手に知ったか出来てたのしー・・・といいのにぃ。
蛇足だが、65536ぐらいのデータになると数字がずらずらと出ても見る気もしない。グラフ化が大事だ。というか、必須だ。そしてグラフと言えば・・・C言語にグラフィクスライブラリって有名なのは何よおぉーって考えることもなく。gnuplotを使えば良いである。
データはファイルに落とし、そのファイルをgnuplotに食わせる。これ、簡単で便利。
ちなみにPython の Scipy のfft()は上のC言語のFFTよりも高速である。まー上のFFTのブログラムはアルゴリズム理解のためであって高速化を意図してはいないらしいが。
ScipyのfftはCかFortranか、どっちかで書かれたろ。最適化されてモジュールになったんだろねのね、と想像する。
まー言いたいことはPythonは遅いという一般論があるがモジュールは高速なのだぜ。。てへてへ。もちろん、Pythonの四則演算でFFTのプログラムを書いたら遅いの。
Pythonではグラフ化はmatplotlibを使うと大変便利ですね。
こういうのがタダで使えるって現在は・・・・しあわせすぎてこわい (笑)