3 ms·
In libgmp I think the numbers have to be around 100,000 bits or 30,000 digits for FFT to be faster. https://gmplib.org/manual/Multiplication-Algorithms https:/
by nickcw 2y ago
In libgmp I think the numbers have to be around 100,000 bits or 30,000 digits for FFT to be faster.
https://gmplib.org/manual/Multiplication-Algorithms https://gmplib.org/manual/Multiplication-Algorithms
GMP has lots of other methods in between schoolbook multiplication and FFT multiplication. A nice one is Karatsuba multiplication which is very easy to understand and delivers O(n^1.58) rather than O(n^2) performance. Python uses this method for multiplying large numbers together
https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
- pfdietz 2y agoThe Karatsuba algorithm idea can also be used for multiplication of polynomials.
- kurlberg 2y agoThere is a nice picture of the "best" for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png http://gmplib.org/devel/log.i7.1024.png More context and explanation can be found at: http://gmplib.org/devel/ http://gmplib.org/devel/ BTW, I like Bernstein's survey of different multiplication algorithms at https://cr.yp.to/papers/m3.pdf https://cr.yp.to/papers/m3.pdf (there is a unifying theme about using ring isomorphisms to explain many of the "standard" routines.)
- kurlberg 2y agoPS: if you're interested in multiplying "ludicrously large numbers", Harvey and van der Hoeven had a nice breakthrough and got multiplication down to "FFT speed" (n*log(n)), see https://hal.science/hal-02070778v2/document https://hal.science/hal-02070778v2/document A pop-sci description can be found at https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...