Mathematics
Fast Fourier Transform (FFT)
Quick fact
The FFT algorithm reduces the number of operations from roughly N² (for a DFT) to N log₂ N. For a signal with 1,024 samples, that means about 10,000 operations instead of 1,000,000—a 100x speedup.
Why this is interesting
You use the Fast Fourier Transform every time you listen to music, speak on a phone, or look at a JPEG image—yet this mathematical trick is so efficient it was once considered a national secret.
Read the full explanation
Understanding Fast Fourier Transform (FFT)
Imagine you have a complex sound wave, like a chord played on a piano. To understand which notes are present, you need to decompose the wave into its individual frequencies—a process called the Fourier Transform. When working with digital signals (discrete samples), we use the Discrete Fourier Transform (DFT). But computing the DFT directly is painfully slow: for N samples, it requires N² multiplications. The Fast Fourier Transform is a clever algorithm that rearranges the calculations, breaking the problem into smaller pieces recursively (a divide-and-conquer strategy). It exploits symmetries in the complex exponentials to reuse intermediate results. The result? A dramatic speedup that makes real-time spectrum analysis possible on everyday devices.
A deeper explanation
The FFT works by decomposing a DFT of size N into two DFTs of size N/2: one for the even-indexed samples and one for the odd-indexed samples. This recursion continues until trivial 1-point DFTs remain. The key is the 'butterfly' operation: a simple pair of additions and multiplications that combine results from the smaller transforms. By reordering the input (bit-reversal) and applying these butterflies in stages, the FFT computes the full DFT with only N log₂ N operations. This efficiency matters because frequency analysis is ubiquitous: it enables MP3 compression (removing inaudible frequencies), MRI image reconstruction, radar signal processing, and fast polynomial multiplication. The algorithm's impact was so profound that it is often considered one of the top ten algorithms of the 20th century.