Re:Mathematicians discover a perfect way to multiply (2019)
by photonemitter on Thursday July 23, 2020 @03:32PM
(#23931330)
There’s a theorem known as the Convolution Theorem:
https://en.m.wikipedia.org/wiki/Convolution_theorem
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. )
Re:Mathematicians discover a perfect way to multiply (2019)
by s5ma6n on Thursday July 23, 2020 @07:15AM
(#23926113)
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.