Understanding the FFT Algorithm

signal-processingalgorithmspythonnumpy

Abstraction: Cooley-Tukey FFT algorithm mechanics explained with Python implementations

Key points:

DFT is O(N^2); the Cooley-Tukey FFT reduces this to O(N log N) by recursively splitting the transform into even- and odd-indexed sub-problems (divide-and-conquer).
Key symmetry exploited: X_{N+k} = X_k, allowing half of sub-problem computations to be reused at each recursion level.
Recursive Python implementation requires input size to be a power of 2 (radix-2 FFT); falls back to direct DFT when sub-array size ≤ 32.
Vectorized NumPy version avoids Python recursion overhead, achieving within ~10x of numpy's FFTPACK (Fortran) benchmark.
For N=10^6, FFT completes in ~50 ms vs. ~20 hours for naive O(N^2) DFT.
Extensions beyond radix-2 (Bluestein's, Rader's algorithms) enable FFTs on arrays whose size is not a power of two.

Connections: Jake Vanderplas · Numpy · Fast Fourier Transform · Signal Processing · Divide And Conquer