RFR: 4837946 - Faster multiplication and exponentiation of large integers

[Brian Burkhalter]

On May 16, 2013, at 7:21 PM, Alan Eliasen wrote:

>> I have reviewed this code including verifying all algorithms against
>> the references suggested in the code as well as other sources in the
>> literature. It all looks to be entirely correct and very clean and
>> clear.
> 
>   Thanks very much for looking this over, Brian!

You're welcome. I really did not expect find any problems but I feel better understanding the algorithms and the implementation insofar as possible.

>   One minor revision to this revision that I must have missed is that
> the added import for java.util.ArrayList is not actually used until
> Phase 2, which is improving toString().  (ArrayList is used in the cache
> for improving toString radix conversion.  I didn't use it anywhere in
> multiply() or pow(). )

I have cleaned up the imports.

>   More below.
> 
>> One change which I have *not* made and which seems appropriate to add
>> to this patch is to modify multiply() to use square() if the
>> parameter is the BigInteger instance on which the method is invoked,
>> i.e., to change this snippet
>> 
>> public BigInteger multiply(BigInteger val) { if (val.signum == 0 ||
>> signum == 0) return ZERO;
>> 
>> to this
>> 
>> public BigInteger multiply(BigInteger val) { if (val.signum == 0 ||
>> signum == 0) return ZERO;
>> 
>> if (val == this) return square();
> 
>   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 was initially concerned that it might create an infinite loop if
> any of the square() functions called multiply() to do the dirty work but
> none of them seem to at the moment.

I don't see that anywhere in the code either.

> The identity comparison is be
> reasonably fast and lightweight and constant time.  This optimization
> wouldn't catch the case where two identical numbers are passed in but
> don't point to the same place in memory.  It would be more general to
> call .equals(Object) but that would have more overhead (in the worst
> case, it's O(n) where n is the number of ints in the BigInteger.)  I
> would probably avoid the latter.

I concur.

>   If you perform .pow(2) it will automatically square the numbers
> efficiently and rapidly, but the users won't know that without looking
> at the implementation, and there is some slight overhead to using pow()
> compared to a public square() method.  In the future, the various
> squaring routines could benefit from some of the tricks that pow() uses
> (that is, detecting powers of two in the number and handling those via
> left-shifts.)  This behavior would probably want to be factored out into
> separate private functions, as it would be useful in pow(), square(),
> and potentially in division, as I was recently discussing with Tim Buktu.

Sounds like a good idea I would be inclined to leave these changes to some later stage, perhaps a "phase 3.5" or some such.

Brian