fast convolution

Fast convolution is the convolution theorem put to work: it is the practical, everyday technique of computing a convolution by routing it through the FFT instead of grinding through the slide-and-sum definition. It is how a reverb plugin can convolve a guitar track with a ten-second recording of a cathedral in real time, and how a big-integer library multiplies thousand-digit numbers in the blink of an eye.

The procedure is the three-step recipe of the convolution theorem made concrete. To convolve signal x (length M) with filter h (length L): choose a transform length N at least M + L - 1 (typically rounded up to a convenient FFT size like a power of two); zero-pad both x and h out to length N; compute their FFTs, multiply the two spectra point by point, and take the inverse FFT. The result is the exact linear convolution, computed in O(N log N) time instead of O(M * L). The padding to M + L - 1 is what prevents the FFT's circular wrap-around from polluting the answer. When one input is a continuous stream and the other a short fixed filter, you process the stream in overlapping blocks and stitch the pieces together — the overlap-add and overlap-save methods — so a long recording is filtered with a steady, bounded amount of work per block.

Fast convolution is not always the winner, and saying so honestly matters. The FFT route carries fixed overhead, so for a SHORT filter (a handful of taps) the direct sum is actually faster and simpler; the FFT method pays off once the filter is long, roughly tens of taps or more. It also assumes you can buffer enough samples, which adds latency unfit for some real-time loops. And because everything runs in floating point, the answer carries normal round-off; for exact integer results (as in big-integer multiplication) one uses number-theoretic transforms or careful scaling so the rounding can be removed exactly.