高速フーリエ変換
fast fourier transform, FFT
離散フーリエ変換を計算機上で高速に計算するアルゴリズム
解析対象が周期的であることを仮定してる
解析対象は例えば、時間信号
論文
Mathematics of COmputation, 1965
ジェイムズクーリー
ジョンテューキー
入力には、周期的な波形を周期の句切れで入れないといけない
$ \sin{x}という関数に関して$ -\pi \sim \frac{99999}{100000}\piとかじゃ🙅
いくつか種類がある
O(N^2)→O(N log N)まで減らせる
AtCoderスライド
データのサンプル数が$ 2^n個のときしか使えない
プログラムを実行しながら学ぶサイト
周期を確認できるのはデータの半分まで
標本化定理
このデータの半分の値のことをナイキスト定数と呼ぶ
回転子$ Wの性質を利用する
複素平面の単位円をN分割した点
$ W \equiv e^{-j \frac{2 \pi}{N}}=\cos \left(\frac{2 \pi}{N}\right)-j \sin \left(\frac{2 \pi}{N}\right)と置く
周期性
.$ W_{N}^{k n}=W^{k n \pm m N}
指数性
.$ W_{N}^{k n}=W_{N}^{l} W_{N}^{k-l}
https://gyazo.com/4ee171542e794b6c279c382c67f5a6c9
FFTの乗算回数がN・log2N /2 と書いてるとこもある ref 再帰的なアルゴリズム
1. if e = 0 then return a;
入力された多項式が定数の時は定数そのものを返す
2. b(x) ← (a0, a2, ... , a_{n-2});
3. c(x) ← (a1, a3, ... , a_{n-1});
4. y ← FFT(e-1, ω_{n/2}, b(x));
5. z ← FFT(e-1, ω_{n/2}, c(x));
6. u ← 1;
7.
code:7
for i={0..(n/2)-1} do
8. return (x0, x1, ..., x_{n-1});
Cooly-Tukey
RaderのFFT
参考