Imagine you need to multiply two polynomials with a million terms each. The naive approach would require a trillion operations — roughly a thousand seconds on a modern CPU. With the Fast Fourier Transform (FFT), you can do it in under a second. This is the kind of dramatic speedup that makes FFT one of the most important algorithms of the 20th century.
The Problem: Polynomial Multiplication
Given two polynomials:
- $A(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1}$
- $B(x) = b_0 + b_1 x + b_2 x^2 + \dots + b_{n-1} x^{n-1}$
We want to compute $C(x) = A(x) \times B(x)$.
The Naive Approach: O(n²)
The straightforward method multiplies each term of A with each term of B:
def multiply_polynomials_naive(A, B):
n = len(A)
m = len(B)
C = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
C[i + j] += A[i] * B[j]
return C
# Example: (2 + 3x) * (1 + 4x) = 2 + 11x + 12x²
A = [2, 3]
B = [1, 4]
print(multiply_polynomials_naive(A, B)) # [2, 11, 12]
Time Complexity: O(n²)
Why it’s slow: Every coefficient in the result requires summing multiple products
The Insight: Point-Value Representation
Here’s the key insight that unlocks fast multiplication:
Theorem: A polynomial of degree n-1 is uniquely determined by its values at n distinct points.
Instead of representing polynomials by coefficients, we can represent them by their values at specific points:
- Coefficient form: $[a_0, a_1, a_2, \dots]$
- Point-value form: $[(x_0, y_0), (x_1, y_1), (x_2, y_2), \dots]$
The magic: Multiplying polynomials in point-value form is trivial — just multiply the y-values!
If $A(x_0) = y_0$ and $B(x_0) = z_0$, then $C(x_0) = y_0 \times z_0$
The challenge becomes:
- Evaluate: Convert coefficients → point-values (fast!)
- Multiply: Multiply point-values (O(n))
- Interpolate: Convert point-values → coefficients (fast!)
Enter the FFT: Choosing the Right Points
The FFT works by choosing a very special set of evaluation points: the complex roots of unity.
Roots of Unity
The n-th roots of unity are the complex numbers that satisfy $\omega^n = 1$:
$\omega = e^{2\pi i / n} = \cos(2\pi / n) + i \cdot \sin(2\pi / n)$
The n roots are: $1, \omega, \omega^2, \omega^3, \dots, \omega^{n-1}$
Why these points? They have beautiful symmetry properties that enable divide-and-conquer:
- $\omega^{n/2} = -1$ (opposite points)
- $(\omega^k)^2 = \omega^{2k}$ in the $n/2$-th roots
- Efficient recursive evaluation
The FFT Algorithm
import numpy as np
def fft(a):
"""
Fast Fourier Transform
Input: coefficient vector a of length n (n = power of 2)
Output: values of polynomial at n-th roots of unity
"""
n = len(a)
# Base case
if n == 1:
return a
# Divide: split into even and odd coefficients
a_even = a[0::2]
a_odd = a[1::2]
# Conquer: recursively compute FFT of half-size problems
y_even = fft(a_even)
y_odd = fft(a_odd)
# Combine: use roots of unity symmetry
y = [0] * n
omega = np.exp(2j * np.pi / n)
omega_power = 1
for k in range(n // 2):
t = omega_power * y_odd[k]
y[k] = y_even[k] + t
y[k + n//2] = y_even[k] - t
omega_power *= omega
return y
def ifft(y):
"""
Inverse FFT - converts point-values back to coefficients
"""
n = len(y)
# Conjugate input
y_conj = [complex(val).conjugate() for val in y]
# Apply FFT
a_conj = fft(y_conj)
# Conjugate output and scale
a = [complex(val).conjugate() / n for val in a_conj]
return a
Fast Polynomial Multiplication with FFT
def multiply_polynomials_fft(A, B):
"""
Multiply polynomials using FFT
Time complexity: O(n log n)
"""
# Result degree is deg(A) + deg(B)
result_size = len(A) + len(B) - 1
# Pad to next power of 2
n = 1
while n < result_size:
n *= 2
A_padded = A + [0] * (n - len(A))
B_padded = B + [0] * (n - len(B))
# Evaluate: coefficient → point-value (FFT)
A_values = fft(A_padded)
B_values = fft(B_padded)
# Multiply in point-value form
C_values = [A_values[i] * B_values[i] for i in range(n)]
# Interpolate: point-value → coefficient (inverse FFT)
C_coeffs = ifft(C_values)
# Extract real parts and trim to actual result size
C = [round(val.real) for val in C_coeffs[:result_size]]
return C
# Example
A = [2, 3, 1] # 2 + 3x + x²
B = [1, 4, 2] # 1 + 4x + 2x²
print(multiply_polynomials_fft(A, B)) # [2, 11, 16, 11, 2]
Complexity Analysis
| Operation | Naive | FFT |
|---|---|---|
| Evaluation | O(n²) | O(n log n) |
| Multiplication | O(n) | O(n) |
| Interpolation | O(n²) | O(n log n) |
| Total | O(n²) | O(n log n) |
For n = 1,000,000:
- Naive: ~10¹² operations
- FFT: ~20,000,000 operations (~50,000× faster!)
Real-World Applications
1. Signal Processing
FFT converts time-domain signals to frequency domain in O(n log n), enabling:
- Audio compression (MP3, AAC)
- Image compression (JPEG uses DCT, a variant of FFT)
- Noise filtering
- Spectrum analysis
2. Large Integer Multiplication
Multiplying two n-digit numbers can be done in O(n log n) by treating digits as polynomial coefficients.
def multiply_large_integers(num1, num2):
# Convert to digit arrays
A = [int(d) for d in str(num1)][::-1]
B = [int(d) for d in str(num2)][::-1]
# Multiply as polynomials
C = multiply_polynomials_fft(A, B)
# Handle carries
carry = 0
for i in range(len(C)):
C[i] += carry
carry = C[i] // 10
C[i] %= 10
# Convert back to integer
result = int(''.join(map(str, C[::-1])))
return result
3. Convolution
FFT computes convolution (used in machine learning, image processing) in O(n log n) instead of O(n²).
4. Solving PDEs
Numerical methods for partial differential equations often use FFT for fast transforms.
5. String Matching
Pattern matching algorithms can use FFT for fast correlation computation.
Practical Considerations
When to Use FFT
✅ Polynomial degree > 100
✅ Need to multiply many times
✅ Working with signals or frequencies
✅ Large integer arithmetic (cryptography, computational number theory)
When NOT to Use FFT
❌ Small polynomials (overhead dominates)
❌ Sparse polynomials (better sparse algorithms exist)
❌ Integer coefficients where precision matters (floating-point errors)
Implementation Tips
- Use library implementations: NumPy’s
np.fft, FFTW (fastest), or language built-ins - Pad to power of 2: FFT is most efficient when n = 2^k
- Handle precision: Use sufficient floating-point precision for integer results
- Number-theoretic FFT: For exact integer arithmetic, use modular arithmetic with NTT (Number-Theoretic Transform)
Python with NumPy (Production-Ready)
import numpy as np
def multiply_polynomials_numpy(A, B):
# numpy.fft is highly optimized
n = len(A) + len(B) - 1
size = 1 << (n - 1).bit_length() # next power of 2
A_fft = np.fft.fft(A, size)
B_fft = np.fft.fft(B, size)
C_fft = A_fft * B_fft
C = np.fft.ifft(C_fft).real[:n]
return np.round(C).astype(int).tolist()
The Math Behind the Magic
Why does FFT work?
The Discrete Fourier Transform (DFT) evaluates a polynomial at roots of unity:
$$ y_k = \sum_{j=0}^{n-1} a_j \cdot \omega^{jk} $$
The FFT computes this in O(n log n) by exploiting:
- Even-odd decomposition: Split polynomial into even and odd powers
- Symmetry: $\omega^{n/2} = -1$, so points come in pairs
- Recursion: Problem size halves at each level
Recurrence relation:
$$ T(n) = 2T(n/2) + O(n) $$ $$ T(n) = O(n \log n) \quad [\text{by Master Theorem}] $$
Inverse FFT
The inverse transform recovers coefficients from values:
$$ a_j = \frac{1}{n} \sum_{k=0}^{n-1} y_k \cdot \omega^{-jk} $$
Notice: IFFT is just FFT with $\omega$ replaced by $\omega^{-1}$ and scaled by $1/n$.
Conclusion
The Fast Fourier Transform is a masterpiece of algorithmic design. By choosing the right representation (point-values at roots of unity) and exploiting symmetry through divide-and-conquer, it transforms an O(n²) problem into O(n log n) — one of the most dramatic speedups in computer science.
Whether you’re processing audio, compressing images, multiplying huge numbers, or solving differential equations, FFT is likely working behind the scenes, making the impossible computationally feasible.
Further Learning
- Books: “The Scientist and Engineer’s Guide to Digital Signal Processing” (free online)
- Interactive: 3Blue1Brown’s FFT visualization on YouTube
- Practice: Implement FFT from scratch, then solve problems on Codeforces/AtCoder
- Advanced: Study Number-Theoretic Transform (NTT) for exact integer arithmetic
- Applications: Explore convolution neural networks and audio synthesis