Basis Lab

Answers · The mathematics underneath

How does the FFT get the same answer without doing all the multiplications?

In shortThe FFT gets the same spectrum by splitting the readings into even and odd positions and reusing the two half-length results for every rate, so shared partial sums are computed once instead of once per rate.

The fast transform gives the same answers because it regroups the original sum by even and odd positions and then reuses the two half-length results for every rate. Nothing is approximated: the regrouping is exact, and the only new arithmetic is one turn per rate that joins the halves.

Xk=∑n=0N−1xne−2πikn/N=∑r=0N/2−1x2re−2πik(2r)/N+e−2πik/N∑r=0N/2−1x2r+1e−2πik(2r)/N=Ek+e−2πik/NOkX_k=\sum_{n=0}^{N-1}x_n e^{-2\pi i k n/N}=\sum_{r=0}^{N/2-1}x_{2r}e^{-2\pi i k(2r)/N}+e^{-2\pi i k/N}\sum_{r=0}^{N/2-1}x_{2r+1}e^{-2\pi i k(2r)/N}=E_k+e^{-2\pi i k/N}O_k
Xk+N/2=Ek−e−2πik/NOk,k=0,1,…,N/2−1X_{k+N/2}=E_k-e^{-2\pi i k/N}O_k,\qquad k=0,1,\dots,N/2-1

Read the identity as an instruction rather than a formula. The list is divided into the readings at even positions, whose transform is EkE_k, and the readings at odd positions, whose transform is OkO_k. Each of those is a transform of half the length, so each is cheaper than the whole. The two halves are then joined by multiplying OkO_k by one turn, e−2πik/Ne^{-2\pi i k/N}, and adding EkE_k. The same EkE_k and OkO_k serve two rates of the whole list: rate kk uses the turn as written, and rate k+N/2k+N/2 uses the same turn with a minus sign. That reuse is the saving. The half transforms are computed once and read twice.

For eight readings the direct sum has eight rates and each rate looks at eight readings, so it costs 8×8=648\times8=64 products. Splitting takes the length down as 8→4→2→18\to4\to2\to1, which is three halvings. At each level, joining the pieces costs one pass over the eight readings, so one pass costs 8 products, and three passes cost 3×8=243\times8=24 products. The two counts answer the same eight rates exactly, because every line of the split is the same sum with its terms grouped differently. The saving at this size is 64/24=2.666…64/24=2.666\ldots, about 2.7 times, which is real but not dramatic.

The natural guess is that the saving comes from a table of sine and cosine values, or from a clever way to compute the turn angles once. That removes the trigonometry and leaves the multiplications untouched. The direct transform still multiplies every reading by a turn for every rate, so it still does N2N^2 products. The repeated work is the partial sum, not the angle: the transform of the even positions appears in several output rates, and the same happens at every smaller level. Caching a turn saves a lookup. Caching EkE_k or OkO_k saves a whole block of multiplications and additions.

What the count buys

Once the split is repeated, the cost is one pass per halving. A length that halves cleanly to one has log⁡2N\log_2 N halvings, so the cost is Nlog⁡2NN\log_2 N products instead of N2N^2.

FIG 1
readings Ndirect N^2halvingssplit N log2 Ntimes fewer
8643242.7
10241,048,5761010,240102.4
1,000,0001,000,000,000,0002020,000,00050,000

The table is the argument in three lines. For 1024 readings, 1024=2101024=2^{10}, so ten halvings cost 1024×10=10,2401024\times10=10,240 products; the direct count is 10242=1,048,5761024^2=1,048,576; dividing gives 1,048,576/10,240=102.41,048,576/10,240=102.4 times fewer products. For a million readings, twenty halvings cost 1,000,000×20=20,000,0001,000,000\times20=20,000,000 products against 1,000,0002=1,000,000,000,0001,000,000^2=1,000,000,000,000; dividing gives 1,000,000,000,000/20,000,000=50,0001,000,000,000,000/20,000,000=50,000 times fewer. The ratio is N/log⁡2NN/\log_2 N, so it grows with the problem rather than shrinking.

Where the splitting has to stop

The clean version needs a length that can be halved all the way to single readings: a power of two. A real record is often not that length. Padding with zeros up to the next power of two makes the arithmetic convenient but changes the record, so it changes the spectrum in the way any window or truncation does. Mixed-radix versions split by other factors, and prime lengths need a different route again. The exact identity is not what fails; what fails is the simple repeated halving. In floating point the answers also differ in the last digits because the additions happen in a different order, not because the algorithm is approximate.

Worth keeping

  • The FFT is exact because it is a regrouping of the same sum, not an approximation of it.
  • A table of turn angles saves trigonometry but not the N2N^2 multiplications; the saving comes from reusing whole half-length transforms.
  • The split cost is NN times the number of halvings, so its advantage grows as N/log⁡2NN/\log_2 N.

Where this goes next

This question is one step of The Fourier Transform, a course that works through its subject from the beginning. The page that teaches this part of it is The Algorithm That Made It Practical, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that pageThe whole course

Other questions people ask about this

  1. Why does multiplying by a sine and summing pick out only that frequency?Multiplying by a sine and adding over whole cycles cancels every other frequency exactly and leaves a positive total for the matching one.
  2. How can a finite list of samples be turned into frequencies and back with nothing lost?A finite list can be converted into frequencies and back exactly, because the transform is a reversible change of description, not a lossy summary.
  3. Why does a fast wiggle look like a slow one when I sample too slowly?Because readings taken at regular instants cannot tell a rhythm from the same rhythm sped up by a whole number of cycles per reading, so the fast one is reported at a folded, slower rate.
  4. Why does sliding a filter along a signal become simple multiplication after a Fourier transform?Because a filter scales every steady rhythm without changing its rate, so the whole sliding sum collapses into one multiplication for each rhythm.
  5. What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
  6. How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.

Read alongside