2019年11月20日

FFTというものがありましてね。。。。そればっかーーー

FFTの解説ではデータ数が2のべき乗であると書いてあるが、実はFFTのアルゴリズムはたくさんあって2のべき乗に限定されない手法もある。詳しくは知らないけど(笑)

「高速フーリエ変換」 E.ORAN 今井・宮川 訳 科学技術出版社 1978年

40年前の本に詳細がある。基数2,4,8のFFTアルゴリズムもあれば任意のNに対するFFTアルゴリズムもあるとさ。ちゅーりー・くーきー、サンデ・クーキーらが考えたアルゴリズムがベースではあるが派生がたくさん出てきたって事だろう。

そうなると性能が一番いいFFTアルゴリズムってどーーれだ?  って思うね。そういうのがライブラリに入っていたらワタクシは使うだけですし。うむうむ。
ワタクシの経験では上の本のFFTプログラム、Fortranで書かれていたものをC言語に書き換えた。
C言語による科学技術計算 小池CQ出版 1987年 CによるFFTプログラムが載っていたので写経して試した。
奥村C言語によるアルゴリズム辞典のFFTプログラムをDLして試した。

この3つで一番遅いのはE.ORANの元がFortranのプログラムである。小池・奥村のFFTプログラムは同等であった。
では、この遅さは何が原因か?  E.ORANは高速化を狙ったものではなく読者がFFTアルゴリズムを理解する手助けのためのプログラムであると書いている。
違いの一つはシャフリングだ。E.ORANは都度都度やっている。他の2つは一気にシャフリングしている。
まーしかし、これ以上はワタクシのIQ88では追ってもわからぬであろう。

そしていい忘れたがPython + Scipy のFFT。実はこれが一番高速であった!!  Pythonはインタープリターであり遅い・・・・というのはPythonの四則演算でやれば遅い。だがモジュールは結構はやいである。小池・奥村のFFTプログラムは最適化を狙ったものではあるまい。それらをチューンアップしたらscipy モジュールのFFT並になるかもなあ。どうやってTune Upするか知らんけど。
  ん、C言語用の数値計算ライブラリがあってFFTもあればいいわけだ、タダで使えるのが。

まーオレが何かやるにしても速度はきにしないわん。高級なことできるわけないし。教科書レベルで四苦八苦しているのが現状でありまんねん。

さてと、近所にオープンしたらしい焼き肉ライクでも見に行くか。オープン記念に安いかも知れないからなあ。

posted by toinohni at 10:33
"FFTというものがありましてね。。。。そればっかーーー"へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: