5 ms·
This Guy Just Found a Faster Way to Multiply
- acqq 7y agoThe paper: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
- dwrodri 7y agoFrom my understanding, this won't have any implications on the way ALUs are designed, correct? I was taught that Russian Peasant multiplication[1] was the most straightforward method for implementing multiplication efficiently on hardware. I would have to imagine that performing a Fast Fourier Transform (FFT from the paper) would add significant overhead. Can anyone more familiar with ALU design confirm or deny this? [1] = http://mathforum.org/dr.math/faq/faq.peasant.html http://mathforum.org/dr.math/faq/faq.peasant.html
- acqq 7y agoFFT is already integrated in the libraries, e.g.: "GNU multiple precision arithmetic library" https://gmplib.org/manual/Multiplication-Algorithms.html#Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms.html#Mul... "NxN limb multiplications and squares are done using one of seven algorithms, as the size N increases. Algorithm Threshold ... FFT MUL_FFT_THRESHOLD"
- hinkley 7y agoIs my math off or is RP already nlogn? Edit: I see my error. N is number of digits, not size of number. By our usual definition of n, table multiplication is log10(n)², which is much smaller.
- rurban 7y agoNo he didn't, he just proved the wellknown and widely implemented Schoenhage–Strassen conjecture from 1971 to be correct. Which was O(n log log n), now implemented for O(n log n). Schoenhage–Strassen is used for multiplying large numbers with >30.000 digits. Below Karatsuba is used, and for >trillion digits Fuerer could be used. What he did was to improve Fuerer's method from 2007, nobody is using yet. https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm