Multiplying two polynomials from their coefficients is the familiar O(n²) convolution — every coefficient times every coefficient. But there’s a second way to describe a polynomial: by its values at enough points. In that value form, multiplying two polynomials is trivially O(n) — just multiply the values pointwise. The catch is converting between the two forms. The Fast Fourier Transform does exactly that conversion in O(n log n), by evaluating at cleverly chosen points — the complex roots of unity — using divide-and-conquer. So the whole multiply becomes: FFT both, multiply pointwise, inverse-FFT back — and convolution drops from O(n²) to O(n log n). Run the pipeline.
O(n log n) polynomial multiply & convolution · coeff ⇄ value form via roots of unity
coefficient form
A polynomial as its list of coefficients [a₀, a₁, …]. Multiply = O(n²) convolution.
value form
A polynomial as its values at n points. Multiply = O(n) pointwise.
roots of unity
The special evaluation points that make the transform recursive and fast.
FFT / inverse FFT
Convert coefficients → values (FFT) and back (inverse FFT), each O(n log n).
fft.js — evaluate, multiply, interpolate
Ready
Multiplying two polynomials A and B. The slow way is O(n²) convolution. FFT’s way: convert both to value form, multiply pointwise (O(n)), then convert back. Step through the pipeline.
1/4
stage
8
FFT size
O(n log n)
vs O(n²)
How it works
Two facts combine. First, a polynomial of degree < n is uniquely determined by its values at any n distinct points — so you can represent it either by coefficients or by a value table, and multiplying in value form is just multiplying the tables entry by entry. Second, if you choose the evaluation points to be the n-th roots of unity (evenly spaced complex numbers on the unit circle), the evaluation has a beautiful recursive structure: a size-n transform splits into two size-n/2 transforms on the even-indexed and odd-indexed coefficients, combined with a “butterfly” step. That divide-and-conquer gives O(n log n). The inverse transform is almost identical (conjugate roots and divide by n), so you convert back just as fast. Net: pad to a power of two, FFT both polynomials, multiply the value tables pointwise, inverse-FFT, and read off the product coefficients.
1
Pad to a power of two
To hold the product of degrees d₁ and d₂, use size n ≥ d₁+d₂+1 rounded up to a power of two. Pad both coefficient arrays with zeros to length n.
2
FFT both — go to value form
Evaluate each polynomial at the n roots of unity via the FFT’s divide-and-conquer. Each is now a table of n complex values, computed in O(n log n).
3
Multiply pointwise
Multiply the two value tables entry by entry — O(n). This is the value-form product of the two polynomials.
✓
Inverse FFT — back to coefficients
Run the inverse FFT on the product table (conjugate roots, divide by n) to recover the product’s coefficients — again O(n log n). Round to integers for integer inputs.
Multiply
O(n log n)
Naive
O(n²)
Value-form mult
O(n)
Points
roots of unity
The code
# multiply two polynomials via FFT, O(n log n)def multiply(A, B):
n = next_pow2(len(A) + len(B) - 1)
fa = fft(pad(A, n)) # coefficients -> values, O(n log n)
fb = fft(pad(B, n))
fc = [fa[i] * fb[i] for i in range(n)] # pointwise multiply, O(n)
c = ifft(fc) # values -> coefficients, O(n log n)return [round(x.real) for x in c[:len(A)+len(B)-1]]
# fft splits even/odd coefficients and recurses on the roots of unity
Quick check
1. Why is multiplying polynomials in value form fast?
If both polynomials are sampled at the same points, their product’s value at each point is just the product of their two values there. So value-form multiplication is O(n) pointwise, versus O(n²) to convolve coefficients.
2. What does the FFT actually compute?
The FFT evaluates a polynomial at the n roots of unity — converting coefficients to values — in O(n log n) via divide-and-conquer. The inverse FFT converts back. The multiply itself happens pointwise in between.
3. Why choose the roots of unity as the evaluation points?
The n-th roots of unity have a recursive relationship (the even and odd index subproblems reuse the (n/2)-th roots), which is exactly what enables the divide-and-conquer split and the O(n log n) running time.
FAQ
What is the Fast Fourier Transform?
An O(n log n) algorithm to compute the Discrete Fourier Transform (evaluating a polynomial/signal at the n roots of unity) and its inverse. The naive DFT is O(n²); the FFT splits a size-n transform into two size-n/2 transforms on even/odd inputs to reach O(n log n).
How does the FFT speed up polynomial multiplication?
Coefficient multiplication is O(n²) convolution, but value-form multiplication is O(n) pointwise. The FFT converts between the forms in O(n log n), so the multiply becomes: FFT both, multiply pointwise, inverse FFT — making convolution and big-number multiplication O(n log n).
What is the FFT used for beyond polynomials?
A huge range: audio/image processing (spectral analysis, filtering, JPEG/MP3 compression), communications (OFDM in Wi-Fi/cellular), fast big-integer and polynomial multiplication, solving PDEs, and convolution/correlation in ML — the standard tool for moving between the time/space and frequency domains quickly.
What is the number-theoretic transform (NTT)?
A variant of the FFT over a finite field (integers mod a prime) using a primitive root of unity there, instead of complex numbers. It gives exact integer convolutions with no floating-point error, so competitive programming and cryptography often use the NTT for polynomial multiplication modulo a prime.