How the fast Fourier transform works

What problem does the FFT solve?

Many signals are easier to understand in terms of frequency than in terms of time. A recording of a chord is a single wobbling line when plotted against time, yet the interesting question is which pitches are present and how loud each one is. A Fourier transform answers that question by converting a signal from its original domain, usually time or space, into the frequency domain, and it can convert back again.

On a computer, signals arrive as a finite list of numbers, so the version that matters is the discrete Fourier transform, or DFT. Each output of the DFT measures how strongly one particular frequency shows up across the whole input. The catch is cost. There are n outputs, and each one is a sum over all n inputs, so the direct method takes on the order of n² operations. For a list of a few thousand samples that is tolerable; for millions it becomes impractical.

How does the Cooley–Tukey algorithm make it fast?

The key observation is that the DFT is full of repeated structure. The same complex 'roots of unity', evenly spaced points on a circle, appear again and again in the sums. An FFT exploits this by factoring the DFT matrix into a product of sparse matrices, ones that are mostly zeros, so that far fewer multiplications are needed.

Cooley–Tukey, by far the most widely used FFT, does this by divide and conquer. If the length n can be written as a product of two smaller numbers, the transform can be rewritten as a set of smaller transforms plus some extra multiplications by roots of unity, known as twiddle factors. Each smaller transform can be split again in the same way. In the best-known form, the input is halved at every step, which is why the simplest versions require a length that is a power of two. Other factorizations work too, and practical code usually rearranges the steps so that it does not literally call itself recursively.

Because the method only reorganizes the same terms, the DFT and the FFT are mathematically interchangeable. The inverse transform is nearly identical, differing by a sign and a scaling factor, so the same machinery runs in both directions.

How big is the saving in a real example?

Take a signal of 4,096 samples. Working the DFT out directly, and skipping only trivial steps such as multiplying by one, still takes around 30 million arithmetic operations. The radix-2 Cooley–Tukey version reaches the same result in roughly 70,000 operations, which is more than four hundred times fewer.

The gap widens as the input grows, because n² grows much faster than n log n. Doubling the length of the signal roughly quadruples the direct method's work, while the FFT's work only slightly more than doubles. That difference is what turns a calculation that once had to be rationed into one that can run continuously inside ordinary equipment.

Where did the idea come from, and where is it used?

The modern algorithm is usually credited to James Cooley and John Tukey, who published it in 1965. Tukey's idea arose in discussions about detecting Soviet nuclear tests with sensors placed around the country, a task that needed fast analysis of the sensor output. Richard Garwin saw that the method would help with many other problems as well and passed the idea to Cooley at IBM for implementation. Since Tukey was not at IBM, the patent position was doubtful and the algorithm entered the public domain.

It later emerged that the pair had rediscovered something much older. Carl Friedrich Gauss had used a closely related method in unpublished work from 1805 while interpolating the orbits of the asteroids Pallas and Juno, and partial versions appeared in between, including one by Danielson and Lanczos in 1942 for x-ray crystallography, a field where Fourier calculations had been a severe bottleneck. Today FFTs are standard tools in engineering, music, science and mathematics, and they sit at the heart of digital signal processing.

Where does the FFT fall short?

The FFT is only identical to the DFT if arithmetic were exact. Real computers round numbers, though in practice many FFT algorithms turn out to be more accurate than evaluating the definition directly, because they perform fewer operations along each path. The operation count is also a simplification: on modern machines, speed often depends more on memory caches and processor pipelines than on the raw number of multiplications, so the fastest code on paper is not always the fastest in use.

There are open theoretical questions too. All known FFT algorithms need on the order of n log n operations, but there is no proof that this is the floor. Methods that minimize the number of multiplications exist, yet they require so many extra additions that they are not worth using on hardware with fast multipliers.

What does the FFT teach about thinking?

The FFT is a reminder that a slow method is not always slow because the question is hard. Often it is slow because it ignores structure that is sitting in plain sight. The textbook formula recomputes the same quantities over and over; noticing the repetition, and organizing the work around it, changed the cost of an entire field.

Its history also shows how an idea's reach depends on circumstance. Gauss had the method and moved on. The 1965 version arrived alongside cheap computers and without a patent wall, and that combination is part of why it spread so widely.

Questions people ask

The thinking behind it

• bottleneck
• signal vs noise
• first principles thinking
• path dependence

More algorithms, explained

• How linear regression works
• How LZW compression works
• How the Kalman filter works
• The travelling salesman problem, explained