Splitting a signal into its even and odd numbered samples and transforming each half costs half as much as transforming the whole — and recombining them costs only about N operations rather than N². So one split is already a large win. Recurse until you reach single points, whose transform is themselves, and you have log N levels each costing N.
Why the FFT changed what was possible
Figure
Both axes are logarithmic. Cyan is direct computation at N²; amber is the FFT at N log N. At 1,024 points the gap is a factor of a hundred. At a million points it is roughly fifty thousand — about fourteen hours of arithmetic against one second. And the gap never closes: doubling N makes the direct method four times more expensive and the FFT only slightly more than twice. Note also that the FFT is more accurate, since far fewer operations accumulate far less rounding error.
Interlaced decomposition, bit reversal, and the butterfly
Figure
Splitting an 8-point signal into even and odd samples, twice, leaves it in the order 0, 4, 2, 6, 1, 5, 3, 7 — which is bit reversal: write each index in binary, reverse the bits, and that is where it lands. 1 (001) goes to 4 (100); 3 (011) goes to 6 (110); 0 and 7 are their own reversals and stay put. Three splits for eight points, which is log₂8. Rebuilding then takes three stages of four butterflies each — the operation below, which takes two values, multiplies one by a twiddle factor, and forms their sum and difference. Twelve butterflies against 64 operations for the direct method, and the gap widens without limit.
The whole 8-point transform, drawn once
Figure
The canonical picture. Inputs enter on the left in bit-reversed order — 0, 4, 2, 6, 1, 5, 3, 7 — and outputs leave on the right in natural frequency order. Between them sit three stages, because log₂8 = 3, each containing four butterflies, because every stage pairs up all eight values. Twelve butterflies in total.
Notice how the pairing span doubles each stage: neighbours first, then two apart, then four apart. That is the recursion made flat — the same divide-and-conquer that split the signal into evens and odds, run in reverse to put the spectrum back together. Nothing here is approximate; this computes exactly what the direct method computes, in 12 butterflies instead of 64 multiply-accumulates.
The recombination is cheap because of a symmetry: on the half-rate grid, frequency k and frequency k + N/2 are indistinguishable. One computation therefore serves two output frequencies, needing only a sign and a phase correction — the twiddle factor. The operation that applies it is a butterfly, and an N-point transform is nothing but N/2 · log N butterflies.
All of which is easier to believe with numbers in it. Below is the whole thing carried out on eight actual samples — every intermediate value, every twiddle, and the spectrum that falls out at the end.
An 8-point transform, worked end to end
Figure
slot
in (bit-reversed)
after stage 1
after stage 2
X[k]
|X[k]|
0
x[0] = 1
1
2
4
4
1
x[4] = 0
1
1 − j
1 − 2.414j
2.613
2
x[2] = 1
1
0
0
0
3
x[6] = 0
1
1 + j
1 − 0.414j
1.082
4
x[1] = 1
1
2
0
0
5
x[5] = 0
1
1 − j
1 + 0.414j
1.082
6
x[3] = 1
1
0
0
0
7
x[7] = 0
1
1 + j
1 + 2.414j
2.613
The same twelve butterflies as the flow graph, run on an actual signal: x = 1, 1, 1, 1, 0, 0, 0, 0, a four-sample pulse. Read left to right and every number is one butterfly away from the last. The slot is an array position, not a frequency, until the final column — outputs leave in natural order, so there the slot is k.
Follow the k = 1 row. Stage 2 leaves 1 − j in slots 1 and 5. Stage 3 pairs them with twiddle W¹ = 0.707 − 0.707j, and (0.707 − 0.707j)(1 − j) works out to exactly −1.414j — the real parts cancel. Add it to get X[1] = 1 − 2.414j; subtract it to get X[5] = 1 + 0.414j. One multiply served two output frequencies, which is the entire trick.
Three things worth checking, because each is a property rather than a coincidence. X[0] = 4 is just the sum of the samples, since the zero-frequency basis function is all ones. X[5], X[6], X[7] are the conjugates of X[3], X[2], X[1] — the negative-frequency half a real input always produces, and the reason you only ever plot the first half. And X[2], X[4], X[6] are exactly zero: a pulse of length 4 in a window of length 8 falls precisely on the nulls of its own sinc envelope. Nothing above is an approximation — the direct N² sum gives the same eight numbers using 64 multiply-accumulates instead of 12 butterflies.
Bit reversal, and why N is a power of two
Repeated even-odd splitting leaves the samples in a scrambled order with a beautifully simple description: write the index in binary, reverse the bits, and that is where it goes. For eight points, index 1 (001) becomes 4 (100); index 3 (011) becomes 6 (110).
That halving is also why N is normally a power of two. Lengths factoring into small primes run nearly as fast; a large prime length falls back to Bluestein’s algorithm and is much slower. Transforming 10,001 points instead of 10,024 can be an order of magnitude slower for no benefit — if a transform is mysteriously slow, check whether its length is prime before looking anywhere else.
Why 10,001 points can be slower than 10,024
Figure
Every transform length from 1000 to 1040, plotted by its largest prime factor on a log scale. Low bars factor entirely into small primes, so a mixed-radix FFT handles them efficiently. Tall bars have a large prime factor and fall back to Bluestein’s algorithm, which works for any length but costs substantially more and uses more memory.
1024 is cyan — a power of two, the best case. But 1000 = 2³·5³ and 1024 are both perfectly fine, while 1009 and 1013 are prime and are the worst thing you can ask for. This is a real trap: if a transform is mysteriously slow, check whether its length is prime before looking anywhere else. And since you usually have some freedom over block size, rounding to a power of two costs nothing.
Periodicity and discreteness are the same coin
There are four Fourier transforms, chosen by whether the signal is continuous or discrete and periodic or aperiodic. Read them side by side and one rule emerges: whichever domain is periodic, the other is discrete.
A periodic signal has a spectrum of harmonics only. A discrete signal has a periodic spectrum. The DFT is discrete in both domains and therefore periodic in both — which is precisely the assumption behind leakage and circular convolution. One sentence explains the structure of the whole family.
Key points
The FFT computes exactly the same result as the direct DFT — not an approximation — using about N times the base two logarithm of N operations instead of N squared.
For one thousand and twenty four points that is a factor of a hundred. For a million points it is a factor of roughly fifty thousand, turning fourteen hours into about a second. The advantage grows without limit as N grows.
The core idea is divide and conquer. Splitting a signal into its even and odd numbered samples and transforming each half costs half as much as transforming the whole, and recombining the two halves costs only about N operations.
Recursing that split all the way down to single points gives log two of N levels, each costing about N, which is where N log N comes from. The transform of a single point is that point.
The recombination is cheap because of a symmetry: on the half-rate grid, frequency k and frequency k plus N over two are indistinguishable. One computation therefore serves two output frequencies, needing only a sign and a phase correction.
That phase correction is the twiddle factor, and the two-input two-output operation that applies it is a butterfly. An N point transform is N over two times log two of N butterflies and nothing else.
Cooley and Tukey published in nineteen sixty five, but Gauss had the same algorithm around eighteen zero five — before Fourier published the transform. Nobody recognized its importance until computers made large transforms attempted at all, because before that the difference between N squared and N log N was academic.
An eight point transform splits three times into groups of one, then rebuilds in three stages of four butterflies each — twelve butterflies against sixty four operations direct. Every stage has the same shape, which is why the algorithm vectorizes and maps onto hardware so well.
Repeated even-odd splitting leaves the samples in bit reversed order — write the index in binary, reverse the bits, and that is where the sample goes. Index one of eight becomes index four; index three becomes index six.
Decimation in time splits the input samples and wants scrambled input with ordered output. Decimation in frequency splits the output bins and does the reverse. Using one forward and the other backward in FFT convolution makes the two scramblings cancel, so nothing is ever reordered.
You do not need a separate inverse routine. Conjugate the spectrum, run the forward transform, conjugate the result, divide by N. That matters where code size or silicon area is limited.
To transform two real signals, put one in the real part and one in the imaginary part of a single complex input and transform once. The spectra separate afterward using the symmetry properties. One transform instead of two — standard for stereo audio.
Bit reversal is why N is normally a power of two. Mixed radix and Bluestein algorithms handle other lengths, but powers of two are fastest, which is why two hundred and fifty six, one thousand and twenty four, and four thousand and ninety six appear everywhere.
Lengths factoring into small primes run nearly as fast as powers of two; large prime lengths fall back to Bluestein and are much slower. Ten thousand and one points can be an order of magnitude slower than ten thousand and twenty four for no benefit. Check whether a slow transform's length is prime before looking anywhere else.
The FFT is more accurate than direct computation, not less, because it performs far fewer operations and therefore accumulates far less round-off error. There is no accuracy-for-speed trade here at all.
Use a library rather than writing your own. If your input is real, use a dedicated real transform — it is about twice as fast, because a general complex transform wastes half its effort on zero imaginary parts.
Twiddle factors do not depend on the data, so they are precomputed into tables and reused. That is why some libraries want you to create a reusable plan before transforming.
Check your library's scaling convention once and write it down. Dividing by N on the forward, on the inverse, or splitting it as one over the root of N are all in use, and this is the most common cause of a transform-modify-inverse pipeline coming out at the wrong amplitude.
Two dimensional transforms are computed by transforming every row then every column, because the transform is separable. That gives N squared log N for an N by N image rather than N to the fourth.
Transforming overlapping windows of a continuous stream is the short time Fourier transform, and it produces a spectrogram. Fifty percent overlap with a Hann window is the usual default, and it has the property that the overlapping windows sum to a constant so the signal can be reconstructed exactly.
The continuous Dirac delta has zero width, infinite height, and unit area. It is a distribution rather than a function, and its defining behavior is the sifting property: integrating a function against a delta returns that function's value at the delta's position.
Translating between discrete and continuous mathematics is essentially a matter of replacing sums with integrals. Convolution, the transform, and everything built on them carry across unchanged in structure.
Periodicity in one domain produces discreteness in the other. A periodic signal has a spectrum consisting only of harmonics; a discrete signal has a periodic spectrum. The DFT is discrete in both domains and therefore periodic in both, which is the assumption behind leakage and circular convolution.