show/hide this revision's text 2 Added explanation.

Problem: You need to multiply large numbers, with $10^9$ digits (or take products of power series). Your computer doesn't have the ability to do $10^{18}$ calculations.

Solution: Recognize multiplication of a power series as a convolution. Take a discrete Fourier transform of the digit sequences, multiply, and apply the inverse Fourier transform. Then perform the carries. This should take under $10^{12}$ calculations. The Fast Fourier Transform takes about $n \log n$ calculations.

The point is not that this is a fast algorithm or a clever trick. It's that you start out with a basic question about integers you can explain to someone comfortable with grade school math, and you end up dealing with complex or at least real numbers, characters of $\mathbb Z/n$, and properties of convolutions.

show/hide this revision's text 1 [made Community Wiki]

Problem: You need to multiply large numbers, with $10^9$ digits (or take products of power series). Your computer doesn't have the ability to do $10^{18}$ calculations.

Solution: Take a discrete Fourier transform of the digit sequences, multiply, and apply the inverse Fourier transform. Then perform the carries. This should take under $10^{12}$ calculations. The Fast Fourier Transform takes about $n \log n$ calculations.