The fast Fourier transform, how and why it works

Our lives today revolve around digital communications, and the fast Fourier transform, or FFT, is the algorithm that quietly makes them possible.

The FFT is a mathematical shortcut that takes a complex, messy wave — like a sound, a radio signal, or a heartbeat — and breaks it down into its individual frequencies. It’s like taking the flavor of a finished soup and separating it back into its original ingredients. Because the FFT can do this calculation incredibly fast, it allows computers to process things like wifi signals, MP3 files, and MRI scans in real time.

In our data-rich world, signal processing tasks are everywhere. So, too, is the FFT.

What is the fast Fourier transform?

The FFT is an algorithm for efficiently computing the discrete Fourier transform (DFT). The DFT takes a list of sampled values — often measurements of a signal over time — and rewrites that same information in terms of frequencies. In other words, instead of asking how the signal changes moment by moment, it disentangles which pure tones or repeating patterns are mixed together to make the signal. Think of it like a prism separating white light into its component colors.

The FFT takes a shorter route to the same destination. It produces the same DFT coefficients, but it reorganizes the work so it takes a fraction of the time.

Fourier methods have historically been important in seismology, too. The FFT was originally developed during the Cold War to distinguish underground nuclear tests from ordinary earthquakes. The first practical demonstration of the FFT occurred at IBM Research in 1964 by James Cooley and John Tukey, and they published the paper describing it in 1965.

To see what the DFT looks like in practice, imagine recording a sound wave. At regular time intervals, you write down its height: $X_0, X_1, X_2, ..., X_{N-1}$. The DFT turns those $N$ samples into $N$ new numbers, often written as $A_0, A_1, A_2, ..., A_{N-1}$ where each $A_r$ tells you how strongly a particular frequency is present. The DFT is defined with the following equation:

This equation is a compact way to represent sine and cosine waves. Each output measures how well the original data matches one of those waves.

This matters because once a signal is expressed as frequencies, it becomes easier to identify patterns, remove noise, or simulate how a filter would change the signal.

What makes the FFT “fast”?

Prior to the FFT, directly calculating the DFT was computationally expensive. For each of the $N$ outputs, you must combine all $N$ inputs, so the work grows roughly like $N^2$. An example posed in the 1967 paper that outlined the FFT: For $N = 8,192$ samples, an FFT could compute all DFT coefficients in about five seconds on a then-cutting-edge IBM 7094 computer, whereas conventional procedures took around half an hour. A single core on a modern smartphone, for comparison, can process billions more instructions per second than the 7094 could.

The way the FFT does the work so quickly is by splitting data into even- and odd-indexed samples, computing smaller DFTs on those pieces before combining them. By repeating that process again and again, a single large transform is turned into many smaller ones.

If $N$ is a power of $2$, you can write the original DFT as two smaller DFTs of length $N/2$: one built from $X_0, X_2, X_4, ...$, and one from $X_1, X_3, X_5, ...$. Instead of solving one huge problem, you solve and combine two half-size problems. Then you do the same thing again, splitting and solving until you end up with very short transforms. Because each stage handles all $N$ data points once, and there are only $log_2N$ stages, the total work grows like $Nlog_2N$, not $N^2$, a significant reduction.

Representing information in a new way

The FFT doesn’t represent the discovery of a new physical law. Rather, it is a better representation and smarter computation strategy. By changing how information is organized, the problem is made easier.

When understanding the FFT, a few details and requirements are worth keeping in mind. First, for samples to faithfully capture a continuous waveform, the source must be band-limited within a given range of frequencies and sampled at a rate at least twice the highest frequency present. This is known as Nyquist sampling. Second, the DFT is reversible: An inverse DFT can reconstruct the original sample sequence from the frequency coefficients. Third, multiplication in frequency corresponds to convolution in time, which is why FFTs are so powerful for filtering and signal processing. These criteria are the mathematical reasons FFTs are useful rather than merely fast.

Historically, this speed and usefulness changed computing. Since its introduction 60 years ago, FFT-based methods have become foundational for digital signal processing that powers our lives, as well as many other forms of modern computation, including the quantum Fourier transform (QFT) used by Shor’s algorithm to efficiently factor integers.

Crucially, the FFT does not change the data itself. It reorganizes a signal into frequencies and exploits that structure recursively, turning a once-slow mathematical transform into one of the most important algorithms in scientific and everyday computing.