The convolution problem
Multiplying two polynomials, or two long numbers, by combining every pair of terms is slow. The fast Fourier transform speeds this up by switching from coefficients to values at cleverly chosen points where the work collapses.
Three step plan
- Evaluate. Sample each polynomial at the complex roots of unity, special points spread evenly around a circle.
- Multiply. In value form, the product is just the pointwise product of the two value lists.
- Interpolate. Convert the resulting values back to coefficients with the inverse transform.
The magic is the evaluation step. Roots of unity let a polynomial be split into even and odd parts that share computation, so a divide and conquer halving makes evaluation fast.
Why roots of unity
Squaring a root of unity gives another root of unity from a smaller set, so the even and odd subproblems reuse the same points. This self similarity is what turns a heavy evaluation into a recursive halving.
Key idea
The fast Fourier transform turns polynomial multiplication into pointwise products by evaluating at roots of unity, whose self similar structure allows a recursive halving that interpolates back to the answer.