高速フーリエ変換を使う
FFT は離散フーリエ変換を O(n^2) ではなく O(n log n) で計算します。信号処理、多項式乗算、音声解析に使われます。
- 1
FFT は信号を時間領域から周波数領域へ変換し、信号を周波数成分に分解します。DFT の計算量は O(n^2) ですが、FFT (Cooley-Tukey) は偶数番目と奇数番目のインデックスを再帰的に分割することで O(n log n) に抑えます。前提条件：入力長は 2 のべき乗である必要があります (そうでない場合はゼロ詰めしてください)。応用例：音声処理、画像圧縮 (JPEG)、多項式の乗算、畳み込みです。
- 2 複素数乗算 →
FFT は複素数演算を用います。回転因子 (twiddle factor) は 1 の複素数根 e^(-2πi k/n) です。このツールは複素数の乗算を実行します。複素数乗算は FFT のバタフライ演算の中核となる操作で、各バタフライは 2 つの複素数値を回転因子と組み合わせます。
- 3 多項式評価ツール →
FFT を使うと、多項式の乗算を O(n^2) ではなく O(n log n) で行えます。両方の多項式を 1 の n 乗根で評価し (FFT)、各点で掛け合わせた後、補間します (逆 FFT)。大きな多項式では、係数同士を直接掛けるよりも高速です。
よくある質問
- DFT と FFT の違いは何ですか？
- DFT (離散フーリエ変換) は数学的な定義であり、計算量は O(n^2) です。FFT (高速フーリエ変換) は、対称性と再帰を活用して DFT を O(n log n) で計算するアルゴリズムです。結果は同一で、FFT は単に大幅に高速です。n=1024 の場合、FFT は DFT の約 100 倍高速になります。
- 入力長が 2 のべき乗でなければならないのはなぜですか？
- Cooley-Tukey の FFT アルゴリズムは、入力を偶数番目と奇数番目の半分に再帰的に分割します。このため、長さは 2 のべき乗である必要があります。それ以外の長さの場合は、次の 2 のべき乗になるまでゼロ詰めするか、混合基数 FFT (小さな素数の積である長さをサポート) を使います。大半の FFT ライブラリは 2 のべき乗でない長さも自動的に処理します。