RFR: 4837946 - Faster multiplication and exponentiation of large integers

[Brian Burkhalter]

This is the first of an eventual four phases of performance improvement of BigInteger for large integers.

Issue:

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.

The only changes I've made with respect to the version of the code provided by Alan were to update the latest copyright year to 2013, and to change the javadoc comments of the TOOM_COOK_THRESHOLD constant in BigInteger to the verbiage I suggested to this mailing list yesterday.

I still need to exercise due diligence in terms of testing the code, but I thought it would be good to post the webrev anyway so that interested parties can double check it should they so desire.

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();

Of course square() could be made public, but this approach has the advantage of less process overhead.

Thanks,

Brian