Divide and Conquer
The Cooley-Tukey algorithm, published in 1965 by James Cooley and John Tukey, is the most widely used Fast Fourier Transform (FFT) algorithm. Its central idea is elegantly simple: a large DFT can be split into smaller DFTs, and those smaller DFTs can themselves be split, recursively, until only trivially small transforms remain. This divide-and-conquer strategy reduces the total operation count from O(N²) to O(N log₂ N) — a transformation that turned a theoretical tool into a practical one.
The key observation is that for a signal of length N (where N is a power of 2), the N-point DFT can be expressed as a combination of two N/2-point DFTs — one computed on the even-indexed samples, and one on the odd-indexed samples. This is the Decimation-In-Time (DIT) decomposition, also known as the radix-2 algorithm.
The Butterfly Operation
The combination step — joining X_even[k] and X_odd[k] to form X[k] — follows a pattern called a butterfly. At each stage of the FFT, pairs of values are combined using one complex multiplication (the twiddle factor) and two additions. The name comes from the shape of the signal-flow diagram: two lines cross in the pattern of a butterfly's wings.
Notice that both outputs share the same twiddle-factor product W_N^k · X_odd[k]. Computing this product once and adding it to get X[k], then subtracting it to get X[k + N/2], means each butterfly performs one complex multiplication and two complex additions — not two multiplications. This is the fundamental efficiency gain.
Because W_N^{k+N/2} = −W_N^k (proven in Lesson 6.1), X[k] and X[k+N/2] can be computed from the same pair of sub-transform outputs. Each butterfly produces two output bins for the cost of one twiddle multiplication. Across all N/2 butterflies at one stage, this halves the multiplication count relative to a naive combination.
1 complex multiply + 2 complex adds → 2 output bins. Efficiency: 2× vs. computing each bin separately.Recursive Decomposition — The Full Picture
The power of Cooley-Tukey comes from applying the decomposition recursively. After splitting an N-point DFT into two N/2-point DFTs, each N/2-point DFT is split into two N/4-point DFTs, and so on. The recursion continues until reaching 2-point DFTs (a trivial butterfly: no twiddle multiplication needed since W_2^0 = 1).
For N = 8 (a simple illustrative case), the recursion tree has log₂ 8 = 3 stages. At each stage, N/2 = 4 butterflies are computed. Total butterfly operations: 3 stages × 4 butterflies = 12 complex multiplications. The direct DFT would require 64. For N = 1,024, the comparison becomes dramatic:
| Signal Length N | Direct DFT (N²) | Cooley-Tukey FFT (N/2 · log₂N) | Speedup |
|---|---|---|---|
| 8 | 64 | 12 | 5× |
| 64 | 4,096 | 192 | 21× |
| 256 | 65,536 | 1,024 | 64× |
| 1,024 | 1,048,576 | 5,120 | 205× |
| 4,096 | 16,777,216 | 24,576 | 683× |
| 1,048,576 | ~1.1 × 10¹² | ~10,485,760 | ~100,000× |
The speedup grows with N — making the FFT increasingly superior as signals get longer. For N = 2²⁰ ≈ 1 million, the FFT is roughly 100,000 times faster than the direct DFT.
Bit-Reversal Permutation
The recursive even-odd splitting reorders the input samples in a specific pattern. After log₂ N stages of splitting, the input samples end up in bit-reversed order: the index of each sample in the reordered array is the binary reverse of its original index. For example, in an 8-point FFT: sample at index 3 (binary 011) ends up at index 6 (binary 110).
In practice, the FFT is implemented in-place by first applying this bit-reversal permutation to the input array, then computing the butterfly stages iteratively from smallest to largest. This avoids the memory overhead of recursion and is the basis for all high-performance FFT libraries.
The Cooley-Tukey FFT can be computed entirely in the original input array — no auxiliary buffer needed. After bit-reversal, each butterfly stage overwrites its two input values with the two output values. With log₂ N stages of N/2 butterflies each, the total memory footprint remains N complex values throughout the computation.
Memory: O(N) — same size as the input. No extra allocation needed.Complexity Analysis: Why O(N log N)?
The operation count is straightforward to derive. At each of the log₂ N recursive stages, N/2 butterfly operations are performed. Each butterfly costs one complex multiplication and two complex additions. Therefore:
A complex multiplication is four real multiplications and two real additions — six real operations. A complex addition is two real additions. So each butterfly costs 6 + 2 + 2 = 10 real operations, and with (N/2)·log₂ N butterflies the FFT requires roughly 5·N·log₂ N real operations — compared to 6N² for the direct DFT. For all practical signal lengths, the FFT is faster by orders of magnitude.
Beyond Radix-2: Radix-4 and Split-Radix
The radix-2 algorithm splits each DFT into two halves. Radix-4 splits into four quarters, reducing the number of twiddle-factor multiplications further (since some twiddle factors at multiples of N/4 are ±1 or ±j, requiring no actual multiplication). The radix-4 FFT achieves roughly 25% fewer real multiplications than radix-2 for the same N.
In practice, the split-radix algorithm achieves the theoretical minimum number of real multiplications for power-of-2 lengths. It is the algorithm underlying many professional FFT libraries, including portions of FFTW (Fastest Fourier Transform in the West), which automatically selects the best decomposition for the hardware.
The Cooley-Tukey algorithm was actually known to Carl Friedrich Gauss around 1805 — predating Fourier's work on transforms. Gauss used it to interpolate asteroid orbits. It was independently rediscovered and popularized in 1965, transforming fields from audio processing to medical imaging. The algorithm has been described as one of the most important numerical algorithms of the 20th century.
- The Cooley-Tukey algorithm splits an N-point DFT into two N/2-point DFTs (even and odd samples), recursively, until reaching trivial 2-point transforms.
- Each combination step is a butterfly: one complex multiplication and two complex additions, producing two output bins — exploiting the W^{k+N/2} = −W^k symmetry.
- The recursion has log₂ N stages, each requiring N/2 butterflies. Total: (N/2)·log₂ N complex multiplications — O(N log N) overall.
- For N = 1,024, the FFT requires 5,120 complex multiplications vs. 1,048,576 for the direct DFT — a 205× speedup.
- In-place computation reorders input samples via bit-reversal permutation, then applies butterfly stages iteratively — no extra memory allocation required.
- Radix-4 and split-radix variants reduce twiddle-factor multiplications further, with split-radix achieving the theoretical minimum for power-of-2 lengths.
- Modern FFT libraries (FFTW, Intel IPP, ARM Ne10) automatically select the optimal algorithm for the hardware, achieving near-theoretical peak performance.