Faster large integer multiplication

I added Karatsuba to Python two decades ago, and I’ve said I regret doing so. I would oppose removing it, but it “shouldn’t have been” added to begin with.

There’s basically no end to this, GMP will always run faster in real life, with a group of numeric experts thoroughly dedicated to keeping it at the top of the heap. It’s an enormous amount of difficult code, and just doesn’t belong in core CPython. You can count the number of numeric experts contributing to CPython on a fraction of one hand’s fingers :wink:.

Python users can get the benefit of their extreme efforts merely by installing the gmpy2 extension.

BTW, the decimal module implements multiplication algorithms fancier than Karatsuba, but that’s effectively leveraging an external library too.

3 Likes