Hacker News Reader

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.

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

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

There 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.

It 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%93Strasse...

Schönhage–Strassen is O(n · log n · log log n).

It's too slow unless n is at least on the order of several thousand. Big-O notation doesn't always tell the whole story.