なぜ高速フーリエ変換は画像のような単純な式なのにこちらのサイト書いてあるプログラムは長文で複雑なので

なぜ高速フーリエ変換は画像のような単純な式なのにこちらのサイト書いてあるプログラムは長文で複雑なのですか？
画像の式のまま書くのではだめなのでしょうか？

以下が高速フーリエ変換の式のプログラムが書かれたサイトです。

https://same.blog/2021/05/28/c言語高速フーリエ変換の実装周波数間引き型fftコ/

補足としてフーリエ変換や離散フーリエ変換のプログラムを見ても式のまま書いているわけではなく、式らしきものは見当たらず複雑なプログラムに見えました。なぜ式のまま書き込まないのでしょうか？

No.7 ベストアンサー 回答者： kmee 回答日時： 2022/02/27 13:25

○その式( X_k = Σ〜 ) は離散フーリエ変換の式です。

「高速フーリエ変換」とは、特定の条件を満す場合に、離散フーリエ変換を高速に計算する手法(アルゴリズム)です。
なので「基になる計算式」は同じですが、 実際の計算方法が違って見えます。

○「単純」と「計算が効率的」とは別次元の話です。

○「計算量」について調べてみましょう。
実際の計算時間はいろんな要素が関係するので、単純にXX倍早い、といったことは言えません。
そこで、速さの評価に「計算量」がよく使われます。
対象の規模を n としたとき
O(n^2) の方法では、大体 n^2 に比例した時間がかかります。
O(n・log n) の方法では、大体 n・log n に比例した時間がかかります。
nが大きいと、 n^2>n・log n となります。
nが大きくなればなるほど、この差は大きくなります。


似た例では。
数列の総和を求めるΣ ですが
・全ての数列に対応できる計算方法は「全ての要素を順番に足していく」だけです。
1000要素の数列の場合、999回の足し算が必要です。
10000要素の数列の場合、9999回の足し算が必要です。
計算量はO(n) です。
・もし、数列が「階差数列」だとわかっていれば、「階差数列の総和の公式」を使って、数回の四則演算で求めることができます。
1000要素の数列でも10000要素でも同じ回数です。
計算量はO(1) (nに依存しない定数) です。

ただの足し算と比べると、「公式」は複雑に見えます。
ですが、実際の計算の手間は公式の方が少なくなります。

この回答へのお礼

ありがとうございます。

お礼日時：2022/03/06 13:40

No.6 回答者： tknakamuri 回答日時： 2022/02/25 22:34

>補足としてフーリエ変換や離散フーリエ変換のプログラムを

>見ても式のまま書いているわけではなく、
>式らしきものは見当たらず複雑なプログラムに見えました

式通りに計算するとメチャクチャに遅くなるからです。

指数関数や三角関数は四則演算に比べムチャクチャ遅いですが
アルゴリズムを工夫すればN回使うことを避けられます。
ほぼ四則演算だけで演算を済ませることが出来ます。

フーリエ変換は膨大なデータの計算なのですから
効率の良いアルブリズムを選ぶべきなのです。
FFTは更に複雑ですが、処理量は更に激減します。

これはフーリエ変換に限らず、ソ―トとか探索等の
基本的なプログラシングのタスクにも言えることです。

先人の知恵を学びましょう。

No.5 回答者： kmee 回答日時： 2022/02/25 19:55

1.C言語に 該当する機能が無い(無かった)

例えば、Σ そのものは無いので、 forループで実現する、など


2.その式をそのままプログラムにしても「高速」フーリエ変換にならないから。

その式は、 n=0,1,2,...,N-1 のN回 x_n * exp(〜) を計算します。
それが X0,X1,...X(N-1)のN回必要です。
計算量が O(n^2) になります。
高速ではありません。

これを、条件を限定して、フーリエ級数やexp関数の性質を利用して「無駄な計算はしない」というのが、高速フーリエ変換の仕組みです。
結果、 1回あたり logN 回 × X0,X1,...X(N-1)のN回 でO(n・log n)になります。
ただ、この無駄を省くための処理がちょっと複雑になってしまいます。

この回答へのお礼

ありがとうございます。
すなわち、高速フーリエ変換を計算する上で式に代入して計算するより、高速フーリエ変換を計算する過程で省いても良い部分があったため、その部分を省いた結果プログラムが複雑な形になったわけでしょうか？

ちなみに、高速フーリエ変換の式のままのプログラムとアルゴリズムを使ってプログラムではどのくらいの計算速度の差があるのでしょうか？

どうかよろしくお願い致します。

お礼日時：2022/02/26 14:42

No.4 回答者： Tacosan 回答日時： 2022/02/24 20:49

実際には FFT の「式」を (そのまま) 書いただけなんだけどな. ベタな DFT を FFT の式にしたのは人間. あと DFT より FFT の方が誤差も小さくなる, って話もあるな.

以下はおまけ.

「ベタな DFT」を FFT として実装するのを「C言語系の『悪習』」と呼ぶのは, いくらなんでも C (系) への偏見が過ぎる＞#3. 少なくともこの件については「実装上の最適化の話と理屈がゴチャ混ぜにされて語られる」わけではない. 「理屈」の上で「最適化」して, それを実装しただけ. 「実行を高速化する事が狙い」ではあっても「アルゴリズムレベルの本質的な高速化」であって, 間違っても「種々のプログラム上の数学的抽象化より、アセンブリ言語的に『いろいろ内訳を細かく分解して』全部ベタ書き」したわけじゃない.

この回答へのお礼

ありがとうございます！
ちなみにO(n*n)のOは何を表しているのでしょうか？

お礼日時：2022/02/26 14:44

No.3 回答者： cametan_42 回答日時： 2022/02/24 20:21

> 画像の式のまま書くのではだめなのでしょうか？

あくまで理論的な話では。
書いてもいいですよ。別にダメだ、って事はない。
ただ、C言語系の話、記事、書籍に良く見られますが、

「実装上の最適化の話と理屈がゴチャ混ぜにされて語られる」

ケースが多いんで、貴方のように混乱するわけです。
ハッキリ言うと、C言語系の「悪習」と言って良い。
「理論」と「最適化実装」をゴチャ混ぜにして語る人が異様に多いのです。

「高速フーリエ変換」と言う通り、実行を高速化する事が狙いなわけでしょう。
つまり、種々のプログラム上の数学的抽象化より、アセンブリ言語的に「いろいろ内訳を細かく分解して」全部ベタ書きしないと速くならない。
ただそれだけです。
ただ、数学そのものを「プログラミングしたい」のなら、非効率でもそっちを選択しても良い、って事です。
その辺は貴方の目的とかプログラムの使い方による、って事ですね。

No.2 回答者： ASスローバラード 回答日時： 2022/02/24 19:31

数式と比べたらたしかに複雑ですね。

関数を作ったらシンプルにならないでしょうか？

初めて見たので興味深かったです。

No.1 回答者： sandaba 回答日時： 2022/02/24 19:21

命令がないから。