Further BigInteger performance improvements
aph at redhat.com
Fri Jun 5 02:21:27 PDT 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
> 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.
More information about the core-libs-dev