Further BigInteger performance improvements

[Andrew Haley]

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.