RFR: 4837946 - Faster multiplication and exponentiation of large integers

Brian Burkhalter brian.burkhalter at oracle.com
Tue May 14 19:54:50 UTC 2013

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





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.



More information about the core-libs-dev mailing list