Explore the most important algorithm in signal processing: how roots of unity enable O(n log n) polynomial multiplication
The Fast Fourier Transform is one of the most important algorithms ever discovered. It transforms signals between time and frequency domains in O(n log n) instead of O(n²), revolutionizing signal processing, image compression, and polynomial arithmetic.
The key insight: evaluating a polynomial at the nth roots of unityhas special structure. Because ωk+n/2 = -ωk, we can split the problem in half at each step — the classic divide-and-conquer pattern.
In this section, you'll explore roots of unity on the complex plane, watch the butterfly diagram unfold, and see how FFT makes convolution efficient.
The nth roots of unity are complex numbers ω where ωn = 1. They sit evenly spaced on the unit circle and satisfy remarkable properties: the cancellation, halving, and summation lemmas that make FFT possible.
ωdndk = ωnk for any positive integer d
This lemma lets us relate roots of different orders, crucial for FFT recursion.
Evaluating a degree-(n-1) polynomial at all n roots of unity takes O(n²) naively. But the roots have special structure: ωk+n/2 = -ωk. This means half the evaluations share work with the other half, giving O(n log n)!
A polynomial can be represented as coefficients [a₀, a₁, ...] or as point-values [(x₀, y₀), (x₁, y₁), ...]. Multiplication is O(n²) in coefficient form but O(n) in point-value form. FFT converts between them in O(n log n)!
The Cooley-Tukey FFT algorithm uses butterfly operations that combine pairs of values using twiddle factors (powers of ω). Step through the iterative FFT and watch how data flows through log₂(n) stages.
First, reorder input by reversing the binary representation of each index.
| Index | Binary | Reversed | New Index | Value |
|---|---|---|---|---|
| 0 | 00 | 00 | 0 | 1.00 |
| 1 | 01 | 10 | 2 | 2.00 |
| 2 | 10 | 01 | 1 | 3.00 |
| 3 | 11 | 11 | 3 | 4.00 |
There are log₂(n) = 2 stages. Each stage performs n/2 = 2 butterfly operations. Total: 2 × 2 = 4 operations = O(n log n).
Convolution in time = multiplication in frequency. Instead of O(n²) direct convolution, we FFT both signals, multiply pointwise, then inverse FFT — all in O(n log n). This powers audio processing, image filters, and neural network layers.
(f * g)[n] = Σk f[k] · g[n - k]Gaussian blur: Smooths the signal by weighted averaging with a bell-shaped kernel.
Convolution in time = multiplication in frequency.
Instead of O(n²) direct convolution, we can: FFT both signals, multiply pointwise, then inverse FFT — all in O(n log n). This is the foundation of modern signal processing.
The NTT is FFT over finite fields — using roots of unity mod a prime instead of complex numbers. No floating-point errors! NTT powers big integer multiplication, cryptography (lattice-based schemes), and competitive programming.
FFT over finite fields instead of complex numbers. NTT avoids floating-point errors entirely, making it perfect for exact integer arithmetic, cryptography, and competitive programming.
p = 998,244,353 has a special form: p = k·2m + 1
This means (p-1) is divisible by large powers of 2, allowing NTT of size up to 223.
g = 3 is a primitive root mod p, meaning g generates the multiplicative group Zp*.
Exact integer multiplication with no floating-point errors!
| Property | FFT | NTT |
|---|---|---|
| Domain | Complex numbers | Integers mod p |
| Roots of unity | e2πi/n | g(p-1)/n mod p |
| Precision | Floating-point errors | Exact (modular) |
| Size constraint | Power of 2 | n | (p-1) |
| Use cases | Signal processing | Cryptography, big integers |
1. Choose prime p = k·2m + 1 where n ≤ 2m
2. Find primitive root g mod p
3. Compute ω = g(p-1)/n mod p (nth root of unity mod p)
4. Apply same Cooley-Tukey algorithm, but all arithmetic is mod p
5. Inverse NTT uses ω-1 = gp-1-(p-1)/n mod p
You now understand one of the most transformative algorithms:
Next: We'll explore advanced tree structures — B-trees for disk optimization, persistent trees for version control, and van Emde Boas trees for O(log log U) integer operations.