The Fast Fourier Transform Algorithm

Pricing an option via the Carr-Madan method, or de-noising a high-frequency price series, requires computing a discrete Fourier transform — decomposing a sequence of $n$ numbers into a combination of $n$ oscillating frequencies. Computed the obvious way, this costs $O(n^2)$ operations: for $n=1{,}000{,}000$, that's a trillion operations, far too slow for a calibration loop. The Fast Fourier Transform (FFT) computes the mathematically identical result using a clever recursive trick, in only $O(n \log n)$ operations — roughly 20 million for the same million points, a difference of five orders of magnitude.

An analogy: sorting mail by splitting the pile in half, recursively

Imagine having to sort a huge pile of mail by zip code, and instead of comparing every letter to every other letter (which gets slow fast as the pile grows), you split the pile into two smaller piles based on one digit, sort each smaller pile the same way (splitting it again), and merge the sorted results back together. This "divide, solve the smaller pieces, recombine" pattern is dramatically faster than brute-force pairwise comparison once the pile is large, because the work per split is small and the number of splits needed grows only logarithmically. The FFT applies exactly this divide-and-recombine idea to computing a Fourier transform, splitting the problem in half at each level of recursion.

The math, one piece at a time

The discrete Fourier transform of a sequence $x_0, \ldots, x_{n-1}$ produces $n$ output values:

$$X_k = \sum_{j=0}^{n-1} x_j \, e^{-2\pi i jk/n}, \qquad k = 0, \ldots, n-1 .$$

In words: each output $X_k$ is a weighted sum of all $n$ input points, where the weights are complex numbers tracing out a specific oscillation (frequency $k$) — computing it directly for all $k$ costs $n$ multiplications for each of $n$ outputs, giving $O(n^2)$ total. The FFT (assuming $n$ is a power of 2, for the classic version) observes that the sum for $X_k$ can be split into a sum over the even-indexed inputs and a sum over the odd-indexed inputs:

$$X_k = \underbrace{\sum_{j} x_{2j}\, e^{-2\pi i jk/(n/2)}}_{\text{DFT of even-indexed inputs}} + \; e^{-2\pi i k/n} \underbrace{\sum_{j} x_{2j+1}\, e^{-2\pi i jk/(n/2)}}_{\text{DFT of odd-indexed inputs}} .$$

In plain English: computing the size-$n$ transform reduces to computing two size-$n/2$ transforms and combining them with a small amount of extra work — and each of those can, in turn, be split the same way into size-$n/4$ transforms, recursively, down to trivially small pieces. This recursive halving is what turns $O(n^2)$ into $O(n \log n)$: there are $\log_2 n$ levels of splitting, each doing $O(n)$ total combination work.

Worked example 1: counting operations by hand

For $n = 1{,}024$ points: direct DFT costs on the order of $n^2 = 1{,}048{,}576$ operations. FFT costs on the order of $n \log_2 n = 1{,}024 \times 10 = 10{,}240$ operations — about 100x fewer, for the exact same mathematical output. For $n = 1{,}000{,}000$ (rounding to the nearest power of 2, roughly $2^{20}$): direct DFT is on the order of $10^{12}$ operations, FFT is on the order of $10^6 \times 20 = 2 \times 10^7$ — a 50,000x speedup, which is the difference between a calculation finishing in milliseconds versus taking hours.

Worked example 2: a tiny 4-point FFT by hand

Sequence $x = (1, 2, 3, 4)$, $n=4$. Split into evens $(1,3)$ and odds $(2,4)$. The 2-point DFT of $(1,3)$ is $(4,-2)$; of $(2,4)$ is $(6,-2)$. Combining with the twiddle factors for $n=4$ ($1, -i, -1, i$): $X_0 = 4+6=10$, $X_1=-2+2i$, $X_2=-2$, $X_3=-2-2i$. This matches direct computation exactly, but was assembled from two trivial 2-point transforms plus a small combination step — the same pattern that, scaled up recursively, produces the full speedup.

What this means in practice

The FFT is what makes Fourier-based option pricing methods (Carr-Madan and related characteristic-function techniques) fast enough for real calibration workflows, where an entire volatility surface's worth of strikes is priced from one FFT call rather than one integral per strike. It also underlies spectral analysis of price series, fast convolution (used in some volatility and correlation estimation routines), and any signal-processing task applied to market data. Whenever a computation involves a discrete Fourier transform on more than a few hundred points, using an FFT implementation rather than a direct sum is close to mandatory for production speed.