4 ms·
A very interesting look at large integer multiplication, including the FFT method, that finds some interesting underlying connections mathematically between the
by tzs 8y ago
A very interesting look at large integer multiplication, including the FFT method, that finds some interesting underlying connections mathematically between them all is given in the paper "Multidigit Multiplication for Mathematicians" by Daniel J. Bernstein [1].
He ties them all to exploiting certain ring homomorphisms, either to compute r s with the help of f(s) f(s) or to compute f(r) f(s) with the help of r s. Karatsuba, Toom, FFT, Schönhage–Strassen...all are using ring homomorphisms to go between what you want to be doing and something that is easier.
Also see his later "Fast multiplication and its applications" [2].
[1] https://cr.yp.to/papers/m3.pdf https://cr.yp.to/papers/m3.pdf
[2] https://cr.yp.to/lineartime/multapps-20080515.pdf https://cr.yp.to/lineartime/multapps-20080515.pdf