典型例：高速フーリエ変換
1. アルゴリズムの勝利：高速フーリエ変換
数多くのアルゴリズムが世の中にある。 初級者用として名高いのが「ユークリッドの互除法」であろう。 ごく優しいが、その中にアルゴリズムの粋がつまっている。 そして、上級者用として範囲を広げた時、 何よりもアルゴリズムとしての体裁がふさわしいと私が思っているのが、 高速フーリエ変換 ( Fast Fourier Transformation, FFT ) である。
その体裁にふさわしいという理由は、次の観点による。
1-1. 美しい
「分割して統治せよ」というのがアルゴリズムの方法論であり、王道である。 高速フーリエ変換はまさにその分割統治法を適用してうまくいった例である。 しかし、分割と統治の仕方が難しい。 その分割と統治の関連図から、バタフライ演算という名前がついているほどだ。
1-2. 速い
アルゴリズムというからには、 ソフトウェアの品質の観点でいう 「効率性」が他の素朴な方法より優れていなければならない。 FFT も当然、時間効率性、すなわち速度が速い。データ数が N のとき、 素朴な方法では、O ( N ) かかるのに対して、FFT では O ( log N ) ですむ。 これは大きな長所である。もちろん、この場合の定数はさほど変わりない。
1-3. 応用範囲が広い
実はこれこそが、 FFT をアルゴリズムの王様たらしめている理由ではないかと思う。 信号処理においてはかかすことのできない処理であり、 ハードウェア化もされている。
ここまで述べておいて、「では FFT とはいかなるアルゴリズムか」といわれて、 どのように説明しようかと迷った。 結局、説明はあきらめた。成書にも優れた記述があり、 またインターネットでも優れた解説がたくさんあるからだ。 もしわかりやすい説明を期待された方は、あきらめてください。 なお、インターネットで単に FFT と入れると、 Final Fantasy Tactics の意味のページがわんさかヒットするので、 注意のこと。
2. 落ち穂拾い
以下、FFT に対する落ち穂拾いです。興味がある方がいればどうぞ。
計算精度
FFT は素朴な方法より計算精度の面でも優れているということだ。 どこにこの根拠が書いてあったかは忘れた。
オリジナル
このアルゴリズムを発明したのはクーリー(J. W. Cooley) とテューキー(J.W. Tukey)であることは よく知られている。他にもヴィノグラードの高速フーリエ変換もあるが、通常 FFT といえば クーリー・テューキーのものを指す。このクーリー・テューキーの原論文はわかりやすく 書かれている。私も今は手許にないが、実際読んでみて非常にわかりやすかった。
パワースペクトル
FFT はその生い立ちからいって、信号のピリオドグラム解析に使うことができる、 と思われがちである。ところが、連続スペクトルをもつ定常確率過程の時系列の解析に、 FFT は、否、FFT を含めたフーリエ変換は役に立たない、という主張がある。 私にはその主張の是非を判断する能力がないのでわからない。 興味をもった方は、尾崎統「時系列解析の基礎」（朝倉書店）を御覧ください。
MARUYAMA Satosi
