3 ms·
Actually 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 integ
by klyrs 7y ago
Actually 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