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 overall sentiment of the Hacker News discussion is negative, specifically regarding the usability and display of the article's website on iOS devices. It does not relate to the technical content of the article itself.