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.
SOLVE IT YOURSELF
Solve it: multiply polynomials with the FFT
Multiplying two n-term polynomials the obvious way is n² multiplications. But in value form — the polynomial sampled at enough points — you just multiply the samples pointwise, n of them. The FFT is the O(n log n) round trip between the two forms. Python or TypeScript.
YOUR TASK
Implement fft(a, invert) and multiply(a, b), where the inputs are integer coefficient lists (lowest degree first). Return exact integer coefficients.
HINTS — 8 IDEAS
A degree-<n polynomial is pinned down by its values at n distinct points. Multiplying in that form is pointwise — one multiplication per point instead of n².
The points that make the transform fast are the n-th roots of unity. Their symmetry is what lets one transform of size n be built from two of size n/2.
Split the coefficients into even and odd indices, transform each half, then recombine: out[k] = E[k] + wk·O[k] and out[k+n/2] = E[k] − wk·O[k].
Those two lines share one multiplication because wk+n/2 = −wk. That cancellation is the entire speedup.
The split only works when n is a power of two, so pad first — to at least len(a) + len(b), or the result wraps around and corrupts the low coefficients.
The inverse transform is the same routine with the angle negated, then everything divided by n.
Round at the end. The answer is integral, but floating-point roots of unity will hand you 5.999999999999998.
Wrap-around is the classic bug and it is silent: pad to len(a)+len(b)-1 exactly and the top coefficient quietly folds onto the bottom one.