polynomial multiplication by FFT

Multiplying two polynomials by hand means convolving their coefficient lists: every coefficient of one times every coefficient of the other, summed into the right output slots — about n^2 multiplications for degree-n polynomials. The FFT gives a faster route by switching representations: it is much cheaper to multiply polynomials when they are given as values rather than coefficients.

The strategy has three moves and rests on one fact: in value form, multiplication is trivial — if P and Q have values p_i and q_i at the same points, then their product P*Q has value p_i * q_i at each point, just pointwise multiplication. So: (1) use the FFT to evaluate both polynomials at 2n roots of unity, turning coefficients into values in O(n log n); (2) multiply the two value lists pointwise in O(n); (3) use the inverse FFT to interpolate the product values back into coefficients in O(n log n). Total time O(n log n), a dramatic win over the O(n^2) schoolbook convolution. You evaluate at 2n points, not n, because the product has degree up to 2n-2 and needs that many values to be pinned down uniquely.

This is the standard fast way to compute convolutions, which appear everywhere: multiplying big integers (write the digits as polynomial coefficients), signal filtering, counting with generating functions, and string-matching with wildcards. It is the concrete reason the FFT belongs in an algorithms course. The same caveats apply: pad the coefficient arrays so the working length is a power of two, and remember the complex-arithmetic rounding — for exact big-integer products one rounds the final coefficients to the nearest integer or uses a number-theoretic transform to stay exact.