3 ms·
Use Fast Fourier Transforms for O(nlogn) multiplication!
by lawrenceyan 7y ago
Use Fast Fourier Transforms for O(nlogn) multiplication!
- klyrs 7y agoActually look at GMP or MPIR for the real dirt. There's a lot of detail hidden in that big-O notation, and IIRC Karatsuba is faster for certain ranges of integers.
- jheriko 7y agoyes, for smaller integers it is necessarily faster... there are higher order versions, the Toom-Cook algorithsm, which fill the gap between them too...
- fdej 7y agoHere's GMP's current tuning (for Skylake CPUs, from https://gmplib.org/devel/thres/ https://gmplib.org/devel/thres/) Basecase: up to 520 digits (27 limbs x 19.26 digits per 64-bit limb = 520) Karatsuba: 520 - 1425 digits Toom3: 1425 - 4045 digits Toom4: 4045 - 6068 digits Toom6: 6068 - 8053 digits Toom8: 8053 - 120835 digits FFT: 120835+ digits
- ranie93 7y agoIt seems to be mentioned in the article: "[...]and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n." https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
- jwilk 7y agoSchönhage–Strassen is O(n · log n · log log n).
- excessive 7y agoThere are subtleties that make this more difficult than it sounds. For small N digits, you don't have to worry about rounding error on your FFTs, but as N gets large, you need to be careful.
- dreamcompiler 7y agoIt's too slow unless n is at least on the order of several thousand. Big-O notation doesn't always tell the whole story.