Mathematics
Fast Fourier Transform (FFT)
Quick fact
The FFT reduces the work of computing N frequency components from about N² operations to N log N operations—for a 1-second audio clip with 44,100 samples, that's roughly 600,000 times fewer multiplications.
Why this is interesting
You use the Fast Fourier Transform dozens of times a day—every time you stream a song, take a photo, or make a phone call. But how does your device separate a jumble of noise into beautiful individual frequencies so quickly?
Read the full explanation
Understanding Fast Fourier Transform (FFT)
Imagine you have a recorded sound wave: a long list of sample values. You want to know what notes are hidden inside it. The Discrete Fourier Transform (DFT) does this by comparing the signal to every possible frequency wave and measuring how much each frequency matches. If you try this directly, each of the N samples must be compared with each of the N frequencies—that's N × N operations, which quickly becomes impossibly slow for real-world signals. The Fast Fourier Transform takes a different path. It uses a divide-and-conquer strategy: split the samples into the even-numbered ones and the odd-numbered ones, compute the Fourier transform of each half separately, and then cleverly combine the two sets of results. By repeating this splitting, the problem becomes much smaller at each step, like folding a paper in half over and over instead of measuring every tiny piece one by one.
A deeper explanation
The FFT works because the complex exponentials used in the DFT have beautiful symmetries—the so-called roots of unity. When you rotate around the unit circle, these values repeat in predictable patterns. The algorithm, most famously the Cooley–Tukey FFT, exploits these symmetries. For a signal of length N = 2^m, the DFT matrix is broken down into two DFTs of size N/2, then recombined using precomputed 'twiddle factors.' This gives a recurrence of T(N) = 2T(N/2) + O(N), which solves to O(N log N). The recombination step is often drawn as a 'butterfly' diagram, showing how pairs of values are combined in a wave-like pattern. The impact is hard to overstate. The FFT powers modern audio compression (MP3), image encoding (JPEG), wireless communication (OFDM), radar, medical imaging, and even scientific simulations. Without it, many real-time processing tasks would take minutes instead of milliseconds—or simply be impossible.