RFR: 4837946 - Faster multiplication and exponentiation of large integers (original) (raw)

Alan Eliasen eliasen at mindspring.com
Fri May 17 02:21:06 UTC 2013

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/viewbug.do?bugid=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 eliasen at mindspring.com http://futureboy.us/

More information about the core-libs-dev mailing list