BTW you may have noticed that the paper multiplication method we all learned in third grade is digit-by-digit convolution, which is an O[n^2] operation. But what does convolution in the time domain become when we switch to the frequency domain? It becomes digit-by-digit multiplication, which is O[n]. So now you see why the FFT is essential here. The extra factors of logn and log(logn) are about taking the FFT itself in both the forward and reverse directions.
So fast multiplication is about looking at numbers as signals and doing signal processing on them.
Much used in simplifying kernel operations and convolutions (and some other nifty tricks.)
Another useful idea is also that in the domain of the fourier transformation we have exponentials (Fourier series are some series of $ c_n e^inx$), and when multiplying exponentials we get $ e^ix * e^iy = e^i(x + y) $
Moreover this is usually coupled with the case where we integrate on some periodic signal (so it’s integrated from 0 to 2pi, and unless the product of e^i(x+y) = e^0 = 1, then the integral becomes 0 as well. )
Thank you for the nice explanation. Clears up the important point that article was not quite able to do so. Even though it feels unintuitive to apply a Fourier transform to numbers for multiplication purposes, it works nicely. Fascinating.
So fast multiplication is about looking at numbers as signals and doing signal processing on them.