Further BigInteger performance improvements (original) (raw)

Andrew Haley aph at redhat.com
Fri Jun 5 09:21:27 UTC 2009

Alan Eliasen wrote:

Andrew Haley wrote:

You give examples of the speedup for very large bignums, but you don't say the size of numbers at which your approach becomes faster than the current code. Of course any asymptotic improvement helps with numbers that are half a million decimal digits long, but where's the crossover? Good question. Like most Karatsuba and Toom-Cook implementations, the optimal crossover point is vague, as it can depend on the size of both operands, and the curves don't separate fast at that point. If you look at the updated file (again, at http://futureboy.us/temp/BigInteger.java ) you'll see the crossover points: Thus, the first crossover for Karatsuba multiplication is at 50*32 bits (1600 bits), or about 482 decimal digits. Toom-Cook at 2400 bits.

OK, that's a little more encouraging. The measures you posted before were for nubers about half a million decimal digits long, which is well into FFT multiplication territory. That we can see some improvement for ~ 500-digit numbers is good to see.

These crossovers are determined experimentally, of course, and constants are chosen that work well for a variety of number forms and operand combinations. These numbers were found to work well after a lot of timing runs with a lot of different number sizes and forms. Of course, it's possible that different thresholds can work better on different architectures and VM settings. I'm not proposing we tune for each architecture, but rather choose conservative crossover thresholds which work well, which I believe these are.

It generally isn't damaging if you're just "in the ballpark" when setting your thresholds; the algorithms will still work fine, and performance will still be very similar for most operands.

Sure, that makes sense.

Andrew.

More information about the core-libs-dev mailing list