Faster large integer multiplication

No, it’s that there’s no end of ways multiplication could be made ever-faster by implementing algorithms more advanced than Karatsuba. Indeed, that’s what the OP here wants to do.

At the start, it required a long series of checkins before Karatsuba was ready for general use. You could only get at it then by setting the envar KARAT. The writeups you can find about “how to do it” are thoroughly inadequate except for its best case: multiplying two ints with exactly the same number of bits. What if it’s a million bits by 20 thousand? The naive approach in that case ends up being slower than grade school multiplication.

I had to stumble into a better approach. Which has, apparently, been rediscovered many times by now: view that as a 50x1 digit grade school multiplication instead, using Karatsuba to multiply 20000-bit “digits”.

So while Karatsuba is as simple an “advanced” method as there is, there are still subtleties, and they all require more & more code to resolve. It doesn’t “just work” (well, not always efficiently), and someone without serious domain knowledge will thrash at random trying to get it to work well in all cases.

Karatsuba is not “a no-brainer” unless someone who implemented it didn’t stick around long enough to deal with the bad cases bound to pop up :wink:.

2 Likes