Fast Fourier Transform

The Fast Fourier Transform (FFT) is an algorithm that computes the discrete Fourier transform of a sequence in O(n log n) operations rather than the O(n²) required by direct evaluation. Its discovery by Cooley and Tukey in 1965 — though anticipated in various forms by Gauss, Runge, and others — transformed digital signal processing from a theoretical possibility into an engineering routine. Without the FFT, OFDM would be computationally infeasible; with it, broadband wireless communication, audio compression, and medical imaging all rest on the same mathematical subroutine.

The algorithm exploits the symmetry of the complex roots of unity. A length-n DFT can be decomposed into two length-n/2 DFTs (even and odd indices), each of which decomposes further, yielding a logarithmic recursion depth. This structure is not merely an optimization; it is a paradigm for efficient computation on regular structures. The FFT is the canonical example of a divide-and-conquer algorithm whose efficiency comes from matching the algebraic structure of the problem to the operational structure of the machine.

The FFT's ubiquity conceals a deeper point: many natural and engineered systems are diagonal in the frequency domain. Linear time-invariant systems, convolution operations, and certain classes of partial differential equations become trivial — multiplication instead of convolution — when viewed through the Fourier lens. The FFT is therefore not just a fast algorithm; it is a fast bridge between two representations of reality, one of which humans find intuitive (time, space) and one of which physics finds simple (frequency, wavenumber). The algorithmic compression it provides is a physical compression: it reveals that the apparent complexity of a signal is often structural, not essential.