Cooley–Tukey: Turning the DFT into O(N log N) (and Why FFT ≠ DFT)

The article derives the Cooley–Tukey FFT by factoring N and reindexing the DFT so it decomposes into smaller DFTs plus twiddle-weighted recombination. This leads to O(N log N) complexity for highly composite N (notably powers of two) and extends to the inverse DFT. The author stresses that FFTs are algorithms for computing the DFT, not a distinct transform, and notes limitations at prime sizes where other methods like Bluestein’s are needed.

Key Points

Cooley–Tukey rewrites the DFT by factoring N = r·d and reindexing k, enabling smaller DFTs on residue-class subsequences followed by a weighted recombination.
A single radix split costs O(N·(d + r)); recursively applying splits to highly composite N yields O(N log N) complexity (e.g., radix-2 for N=2^n).
The same decomposition works for the inverse DFT with minor modifications.
Cooley–Tukey gives little or no benefit for prime-length N and may require complementary methods (e.g., Bluestein) for efficiency.
“FFT” denotes algorithms to compute the DFT; the output is the DFT itself, not an “FFT,” and FFTs are not approximations of the DFT.

Sentiment

The community is broadly positive about the article. Technical discussions are constructive and extend the article's ideas into related areas like coding theory and generalized distributive laws. The main criticism targets the blog's iOS rendering, not its content. There is mild disagreement about historical attribution but no hostility toward the author, who engages actively and responsively.

In Agreement

The FFT-versus-DFT terminology distinction is important and the article's rant about it resonated with readers
FFT's efficiency connects to the distributive property, which extends to other domains like LDPC codes and the generalized distributive law
The recursive application of factorization enabled by the transform's inherent symmetry is key to achieving O(N log N) complexity

Opposed

The distributive property alone is just a constant-factor optimization; the real algorithmic insight is that it can be applied recursively due to the transform's symmetry
Cooley and Tukey should not receive sole credit for inventing FFT since Gauss used essentially the same technique much earlier for computing trigonometric interpolation of orbits
For small or moderate FFT sizes, brute-force SIMD approaches can be practical alternatives that bypass the algorithmic complexity of Cooley-Tukey entirely