On 05/14/2013 01:54 PM, Brian Burkhalter wrote:
> This is the first of an eventual four phases of performance
> improvement of BigInteger for large integers.
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946
>
> Webrev:
>
> http://cr.openjdk.java.net/~bpb/4837946/
>
> This contains Alan Eliasen's implementation of Karatsuba and 3-way
> Toom-Cook multiplication and squaring, and pow() accelerated by power
> of two shifting and accelerated exponentiation by squaring.
>
> 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!
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(). )
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.
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. 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.
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.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
