What you're seeing
Any signal can be written as a sum of sine waves; the Discrete Fourier Transform finds how much of each frequency is present. Done directly that's n output bins each summing over n samples — O(n²). The FFT gets the identical answer in O(n log n) by a divide-and-conquer trick: the DFT of an n-point signal can be assembled from the DFTs of its even-indexed and odd-indexed halves, which share almost all their work. The visualization runs the iterative form: first the samples are shuffled into bit-reversed order (which lines up every recursive even/odd split), then log₂n "butterfly" stages combine ever-larger blocks. The bars begin as your signal and end as its spectrum, peaking at the frequencies it's made of.
The rule
FFT(x): # n a power of 2
if n == 1: return x
E = FFT(even-indexed x); O = FFT(odd-indexed x)
for k in 0 .. n/2−1:
t = e^(−2πi·k/n) · O[k] # the "twiddle" factor
X[k] = E[k] + t # ┐ one butterfly
X[k + n/2] = E[k] − t # ┘
return X
The iterative version does the same butterflies bottom-up over bit-reversed input, in place.
The invariant
The FFT is not an approximation: it computes exactly the DFT, and inverts losslessly — ifft(fft(x)) = x (up to floating-point rounding). The whole speed-up is one algebraic identity. Split the DFT sum by even and odd indices and factor out a twiddle: X[k] = E[k] + W_n^k·O[k] where E, O are the DFTs of the half-length even/odd subsequences and W_n = e^(−2πi/n). Because W_n^{k+n/2} = −W_n^k, the same product W_n^k·O[k] serves two outputs — X[k] and X[k+n/2] — with a plus and a minus. That shared product is the butterfly, and reusing it is exactly what collapses the redundant work. This entry's test confirms it against a brute-force DFT and checks the round-trip and Parseval's theorem (energy is preserved: Σ|x|² = (1/n)Σ|X|²).
The cost
There are log₂n stages, each touching all n elements with n/2 butterflies — hence O(n log n), and the readout shows the dramatic gap in multiplication count even at these tiny sizes. For a million-point transform that's the difference between a billion operations and about twenty million: the reason real-time spectral processing is possible at all. The classic radix-2 form needs a power-of-2 length; mixed-radix and Bluestein's algorithm handle arbitrary n, and production libraries like FFTW auto-tune the decomposition to the hardware.
In the wild
The FFT is one of the most important algorithms ever written — IEEE put it among the top 10 of the 20th century. It is the engine of digital signal processing: audio and image compression (the DCT in JPEG/MP3 is an FFT cousin), spectrograms and noise reduction, radar and sonar, software-defined radio and the OFDM modulation in Wi-Fi, 4G/5G, and DSL. It accelerates large-integer and polynomial multiplication (Schönhage–Strassen), convolutions in signal and deep-learning pipelines, and solving PDEs in physics and seismology. Cooley and Tukey published it in 1965 — though Gauss had the idea in 1805, before Fourier's own work.
Try this
Hit New signal and watch the final spectrum: two bright green peaks (plus their mirror images in the upper half, since the input is real) sit exactly at the two frequencies in the signal — the FFT has decomposed the wiggle into its pure tones. Compare the readout's "complex mults" to n²: even at n=32, the FFT does a fraction of the work, and the gap explodes with size.
References
- Cooley, J. W. & Tukey, J. W. "An Algorithm for the Machine Calculation of Complex Fourier Series." Mathematics of Computation 19(90):297–301, 1965.
- Heideman, M. T., Johnson, D. H. & Burrus, C. S. "Gauss and the History of the Fast Fourier Transform." IEEE ASSP Magazine, 1984.
- Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §30 (Polynomials and the FFT). MIT Press, 2022.