The fast Fourier transform turns one specific problem into pointwise multiplication. Name that problem, give the full pipeline and its complexity, and state the numerical failure mode when the inputs are large integers along with the standard fix.

The fast Fourier transform turns one specific problem into pointwise multiplication. Name that problem, give the full pipeline and its complexity, and state the numerical failure mode when the inputs are large integers along with the standard fix.

Approach: Write out what the product of two polynomials does to their coefficient sequences, then recall what the transform does to that operation and count the cost of each stage.

Convolution. The coefficients of a product of two polynomials are the convolution of the two coefficient sequences, and the convolution theorem says the transform of a convolution is the pointwise product of the transforms, so multiplying two degree n polynomials costs one forward transform of each at O(n log n), n pointwise multiplications at O(n), and one inverse transform at O(n log n), giving O(n log n) overall against O(n^2) for the schoolbook method. The transform evaluates the polynomial at the n complex roots of unity, and the divide and conquer split into even and odd indexed coefficients produces the same two-way split with linear combining work that gives the n log n bound. With large integer inputs the double precision rounding error grows with the coefficient magnitude and the length, so a coefficient of size around 2^53 divided by n log n is where results stop rounding to the correct integer. The fix is the number theoretic transform, which runs the same butterfly over integers modulo a prime such as 998244353 that has a suitable root of unity, giving exact arithmetic with no rounding at all.

Follow-up: How do you multiply two integers with 10^7 digits when a single modulus is too small to hold the result?

Key concepts: convolution theorem, polynomial multiplication, roots of unity, number theoretic transform.