On: Karatsuba Algorithm

[klyrs]

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.

[fdej → klyrs]

Here's GMP's current tuning (for Skylake CPUs, from 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

[jheriko → klyrs]

yes, for smaller integers it is necessarily faster... there are higher order versions, the Toom-Cook algorithsm, which fill the gap between them too...