Fast Fourier Transform

A divide-and-conquer algorithm that computes the discrete Fourier transform in O(n log n), enabling fast convolution.

What it computes

The discrete Fourier transform (DFT) converts a length-n sequence into its frequency components by evaluating a polynomial at the n complex roots of unity. Done directly this costs O(n^2). The fast Fourier transform (FFT) computes the same result in O(n log n) by exploiting symmetry in the roots of unity.

The Cooley-Tukey recursion

Kronos motion — classical

The radix-2 FFT splits a sequence into its even- and odd-indexed halves, transforms each recursively, and combines them with twiddle factors (powers of the primitive root). Because the roots of unity satisfy w^(k+n/2) = -w^k, each combine step reuses one product for two outputs, the butterfly operation. The recursion depth is log n and each level does O(n) work.

Recursive form

python

import cmath

def fft(a):
    n = len(a)
    if n == 1:
        return a
    even = fft(a[0::2]); odd = fft(a[1::2])
    out = [0]*n
    for k in range(n//2):
        t = cmath.exp(-2j*cmath.pi*k/n) * odd[k]
        out[k]        = even[k] + t
        out[k + n//2] = even[k] - t
    return out

Fast convolution

The convolution theorem says convolution in the time domain is pointwise multiplication in the frequency domain. So to multiply two large polynomials or big integers, transform both, multiply componentwise, and invert. This turns an O(n^2) convolution into O(n log n) and is the basis of big-number multiplication and signal filtering.

Practical notes

Iterative bit-reversal FFT avoids recursion overhead and is cache-friendlier.
The number-theoretic transform replaces complex roots with modular roots for exact integer results.
Real-input FFTs and mixed-radix variants handle non-power-of-two sizes.
Numerical rounding matters; the NTT sidesteps it when exactness is required.