高速フーリエ変換
これが次の次数 Q でも繰り返されるため、 p = q 2 Q k − 2 + p 2 {\displaystyle p=q_{2}Q^{k-2}+p_{2}} とすると、次の次数の計算結果 f 2 ( p 2 , q 2 , q ) {\displaystyle f_{2}(p_{2},q_{2},q)} は f ( q Q k − 1 + q 2 Q k − 2 + p 2 ) {\displaystyle f(qQ^{k-1}+q_{2}Q^{k-2}+p_{2})} のあった場所に格納される。繰り返せば、 t = q 1 Q k − 1 + q 2 Q k − 2 + ⋯ + q k {\displaystyle t=q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k}} とすると、計算結果 f k ( p k , q k , q k − 1 , ... , q 2 , q 1 ) {\displaystyle f_{k}(p_{k},q_{k},q_{k-1},\dots ,q_{2},q_{1})} は f ( q 1 Q k − 1 + q 2 Q k − 2 + ⋯ + q k − 1 Q + p k ) {\displaystyle f(q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k-1}Q+p_{k})} のあった場所に格納される。
一方、
F ( s Q + r ) = ∑ p = 0 Q k − 1 − 1 exp  ( − 2 π i s p Q k − 1 ) f 1 ( p , r ) {\displaystyle F(sQ+r)=\sum _{p=0}^{Q^{k-1}-1}\exp \left(-2\pi i{\frac {sp}{Q^{k-1}}}\right)f_{1}(p,r)}
クーリー–テューキー型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。
分割統治法を使ったアルゴリズムで、N = N1 N2 のサイズの変換を、より小さいサイズである N1, N2 のサイズの変換に分割していくことで高速化を図っている。
最もよく知られたクーリー–テューキー型アルゴリズムは、ステップごとに変換のサイズをサイズ N/2 の2つの変換に分割するので、2 の累乗次数に限定される。しかし、一般的には次数は 2 の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。
伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。
クーリー–テューキー型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、N ≤ 8 あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。
を、r を固定し s を変数とした Q 次離散フーリエ変換と見なして、 s = s 2 Q + r 2 {\displaystyle s=s_{2}Q+r_{2}} とすると、
F ( s 2 Q 2 + r 2 Q + r ) = ∑ p 2 = 0 Q k − 2 − 1 exp  ( − 2 π i s 2 p 2 Q k − 2 ) f 2 ( p 2 , r 2 , r ) {\displaystyle F(s_{2}Q^{2}+r_{2}Q+r)=\sum _{p_{2}=0}^{Q^{k-2}-1}\exp \left(-2\pi i{\frac {s_{2}p_{2}}{Q^{k-2}}}\right)f_{2}(p_{2},r_{2},r)}
となる。繰り替えせば、
F ( s k Q k + r k Q k − 1 + ⋯ + r 2 Q + r 1 ) = ∑ p k = 0 Q k − k − 1 exp  ( − 2 π i s k p k Q k − k ) f k ( p k , r k , r k − 1 , ...
かつては実数の入力データに対するフーリエ係数を求めるのには、実数計算だけで行える離散ハートリー変換(英語版) (discrete Hartley transform, DHT)を用いると効率的であろうと思われていた。しかしその後に、最適化された離散フーリエ変換 (discrete Fourier transform, DFT) アルゴリズムの方が、離散ハートリー変換アルゴリズムに比べて必要な演算回数が少ないということが判明した。また当初は、実数入力に対してブルーン (Bruun) FFT アルゴリズムは有利であると云われていたが、その後そうではないことが判った。
また、偶奇の対称性を持つ実入力の場合には、DFTはDCTやDST(英語版)となるので、演算と記憶に関してほぼ2倍の効率化が得られる。よって、そのような場合にはDFTのアルゴリズムをそのまま適用するよりも、DCTやDSTを適用してフーリエ係数を求める方が効率的である。