The FFT, explained by building the slow one first

The FFT is one of the most important algorithms ever written: it is inside every audio app, every image compressor, every radio. People reach for it as a black box. But "fast" only makes sense against "slow," and the slow version, the plain DFT, is where the whole idea lives. Build that first and the FFT becomes an optimization, not a mystery.

The one idea

Any signal in time can be rewritten as a sum of pure sine waves at different frequencies. The Discrete Fourier Transform answers, for each candidate frequency, how much of that frequency is present. It does this by correlating the signal against a rotating complex wave: if the signal contains that frequency, the products line up and sum to something large; if not, they cancel to near zero. The DFT is "compare the signal against every frequency and see what sticks."

Build the slow DFT

The formula for bin k is a sum over the samples of the signal times a complex exponential. That is one line in Python with cmath.

import cmath

def dft(x):
    N = len(x)
    X = []
    for k in range(N):
        s = sum(x[n] * cmath.exp(-2j * cmath.pi * k * n / N) for n in range(N))
        X.append(s)
    return X

Each X[k] is a complex number; its magnitude is how strongly frequency k is present.

Recover the frequencies in a signal

Build a signal that is exactly a 3 Hz wave plus a weaker 7 Hz wave, sampled over one second, and ask the DFT what is in it.

import math

N = 64
signal = [math.sin(2 * math.pi * 3 * n / N) +
          0.5 * math.sin(2 * math.pi * 7 * n / N) for n in range(N)]

spectrum = dft(signal)
mags = [abs(v) for v in spectrum]
peaks = [(k, round(mags[k], 1)) for k in range(N // 2) if mags[k] > 1]
print(peaks)

[(3, 32.0), (7, 16.0)]

The DFT found exactly the two frequencies we put in, 3 and 7, and their relative strengths (32 vs 16, a 2-to-1 ratio, matching the amplitudes 1.0 and 0.5). We never told it what to look for; correlation against every frequency made the real ones stand out and the rest cancel. That is a spectrum analyzer, from scratch.

Where the "fast" comes from

Look at the cost. The DFT has an outer loop over N frequencies and an inner sum over N samples: N * N operations. For a 3-minute song at 44,100 samples per second, N is millions, and N * N is astronomical. The naive DFT is correct but unusable at scale.

The FFT gets the identical answer in N log N operations by noticing structure the naive version ignores: split the signal into its even-indexed and odd-indexed samples, transform each half, and combine. The two halves share almost all their work, because the complex exponentials repeat. Recursing this halving turns N * N into N log N. For a million samples that is the difference between a trillion operations and about twenty million, roughly the gap between "never finishes" and "instant."

The FFT is not a different transform. It is the DFT, computed cleverly. That is why building the slow one first matters: once you have watched the DFT recover 3 Hz and 7 Hz by brute-force correlation, the FFT is just the same result without the wasted arithmetic.

Where it shows up

Every equalizer, every noise filter, every MP3 and JPEG, every "what note is this" tuner runs a Fourier transform, almost always the FFT, to move between time and frequency. Understanding the DFT underneath means the black box becomes a tool you can reason about: you know what a bin is, why magnitude means "how much," and why the fast version exists. That from-scratch grounding is exactly how the audio and DSP track approaches signal processing.