RFR: 4837946 - Faster multiplication and exponentiation of large integers

[Brian Burkhalter]

On May 17, 2013, at 3:47 PM, Brian Burkhalter wrote:

>>   That seems like a lightweight but acceptable change to me.  I have
>> discussed this optimization before, and thought it might improve a small
>> number of cases, but could make the base case of very small non-equal
>> numbers slightly slower.  I haven't benchmarked it; I'd doubt that the
>> change would even be detectable in most programs, and if it were
>> triggered, would somewhat improve the performance of certain programs.
> 
> A quick and dirty benchmark gave these results in operations per millisecond (larger value is faster):
> 
> Before
> 
> o.s.m.g.t.MyBenchmark.multiplyLarge     1445.571 
> o.s.m.g.t.MyBenchmark.multiplySmall     8919.505 
> o.s.m.g.t.MyBenchmark.squareLarge      1462.645
> o.s.m.g.t.MyBenchmark.squareSmall      9018.123
> 
> After: multiply(this) returns square()
> 
> o.s.m.g.t.MyBenchmark.multiplyLarge    1460.300
> o.s.m.g.t.MyBenchmark.multiplySmall    8814.362
> o.s.m.g.t.MyBenchmark.squareLarge     1518.695
> o.s.m.g.t.MyBenchmark.squareSmall      8287.958
> 
> The base code was the current JDK 8 tip (sans phase 1 changes) and the only change was to call square() if the parameter to multiply == this. In the above, "small" indicates that everything will fit in a long and "large" that it will not.

I sent the above prematurely.

The "large" values are sub-Karatsuba level so there is no testing of the new algorithms here.

These results imply that values which cannot be dealt with entirely within a long will be sped up or unaffected but the "==" test. The values which can be dealt with within a long are slowed down in these results by approximately 1%. These results do not to my mind militate against making this small change.

Brian