fast multiplication via the FFT
/ F-F-T /
Multiplying two big numbers (or two polynomials) the schoolbook way costs O(n^2) — every digit of one times every digit of the other. When the numbers have millions of digits, that is far too slow. Fast multiplication via the fast Fourier transform (FFT) does the same job in O(n log n) by a beautiful detour: instead of multiplying coefficient by coefficient, it converts each input to a different representation in which multiplication becomes trivial, multiplies there cheaply, and converts back.
The key idea is two ways to describe a polynomial. A degree-(n-1) polynomial can be given by its n coefficients, OR by its values at n chosen points (its samples). Multiplying in coefficient form is the expensive O(n^2) convolution; but multiplying in value form is trivial — to get the product's value at a point, you just multiply the two inputs' values there, one multiplication per point, total O(n). So the plan is: (1) evaluate both polynomials at a clever set of 2n points, (2) multiply the value lists pointwise in O(n), (3) interpolate back to recover the product's coefficients. The magic is that the FFT performs the evaluation at specially chosen points (complex roots of unity) in O(n log n) instead of O(n^2), and its inverse does the interpolation just as fast. Big integers are handled by treating their digit-blocks as polynomial coefficients and multiplying the polynomials. A common, exact variant called the NTT (number-theoretic transform) does all of this in modular arithmetic instead of with complex numbers, avoiding floating-point rounding entirely.
This brings multiplication down to O(n log n), a dramatic improvement that powers big-integer libraries, polynomial arithmetic, signal processing, and string algorithms that reduce to convolution. The honest caveats matter in practice. First, the constant factor is large, so for small inputs schoolbook O(n^2) or Karatsuba's O(n^1.585) is actually faster — FFT wins only once n is big enough. Second, the complex-number FFT accumulates floating-point error, so for exact integer results you either use enough precision or switch to the NTT. (This entry focuses on FFT as a multiplication tool; the divide-and-conquer derivation of the FFT itself is covered separately in the divide-and-conquer field.)
Multiply (1 + 2x) by (3 + 4x). Coefficient way: 3 + 4x + 6x + 8x^2 = 3 + 10x + 8x^2, O(n^2). FFT way: sample both at enough points, multiply the sample values pointwise (O(n)), interpolate back to get coefficients 3, 10, 8 — the same answer, but the evaluate/interpolate steps run in O(n log n) for large degree.
Evaluate, multiply pointwise, interpolate: O(n log n) replaces the O(n^2) schoolbook convolution.
FFT multiplication wins only for large n: its constant factor is big, so schoolbook or Karatsuba beats it on small inputs, and the complex-FFT version needs care (or the NTT) for exact integer results.