高速フーリエ変換(FFT)をおじさんもC++で作ってみたよ - nursの日記マンガでわかるフーリエ解析 作者:渋谷道雄,晴瀬ひろきオーム社Amazon やあ子どもたち。数値配列を日常的に扱っている俺達プログラマーにとって、フーリエ変換がいかに簡単かというイメージを忘れないように以前日記を書きました。その中で、DFT（離散フーリエ変換）計算の実践実装例も見ました。 そして今日はその高速版、FastFourierTransform（高速フーリエ変換）（以下、FFT）の実装及び原理を紹介します。（実際に動くC++のプログラムソースコードは本記事の一番最後の方にあります。） FFTは20世紀の10大アルゴリズムの中にも数えられる、とても有名なアルゴリズムでもあります。とはいえその歴史は古く、FFTやDFTの本当の起源というところまで行くと、あの大数学者ガウス（1777年生まれ）が既に気付いていた？などという噂もあるらしく、それ自体をテーマにした研究論文が出版されたりしてい
