Review Request: BigInteger patch for efficient multiplication and division (#4837946) (original) (raw)

Weijun Wang weijun.wang at oracle.com
Thu May 9 09:45:03 UTC 2013

Out of curiosity (my major was math back in university), I take a look at BigInteger.java.phase1:

First you have:

 /**
  * The threshold value for using 3-way Toom-Cook multiplication.
  * If the number of ints in both mag arrays are greater than this

number, * then Toom-Cook multiplication will be used. This value is found * experimentally to work well. */ private static final int TOOM_COOK_THRESHOLD = 75;

but then:

 public BigInteger multiply(BigInteger val) {
     if (val.signum == 0 || signum == 0)
         return ZERO;

     int xlen = mag.length;
     int ylen = val.mag.length;

     if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
     {
         ....
     }
     else
         if ((xlen < TOOM_COOK_THRESHOLD) && (ylen <

TOOM_COOK_THRESHOLD)) return multiplyKaratsuba(this, val); else return multiplyToomCook3(this, val); }

So, is it both numbers or any of them great than the constant that the Toom-Cook algotithm will be used?

Thanks Max

On 5/9/13 3:11 PM, Alan Eliasen wrote:

On 05/07/2013 12:53 PM, Brian Burkhalter wrote:

To recapitulate in one place, I think we agree on the following sequence:

Phase 1: Faster multiplication and exponentiation of large integers * Karatsuba and Toom-Cook multiplication and squaring; revised pow() function. * http://bugs.sun.com/bugdatabase/viewbug.do?bugid=4837946 (update synopsis/description) * http://bugs.sun.com/bugdatabase/viewbug.do?bugid=4646474 Phase 2: Faster string conversion of large integers * Recursive Schoenhage toString() routines. * http://bugs.sun.com/bugdatabase/viewbug.do?bugid=4641897 Phase 3: Faster division of large integers * Burnickel-Ziegler division routines. * Issue to be filed. Phase 4: Faster multiplication and division of very large integers * Barrett division and Schoenhage-Strassen multiplication. * Issue to be filed. Okay, I've created a set of patches that implement these 4 phases. (They're not actually patches, but the entire source file for each phase, as Brian requested.) These are available at: http://futureboy.us/temp/BigIntegerPatch.zip In this zipfile, the file(s) to use for each phase are marked with the ".phaseX" suffix. If there is no change in a file for a given phase, there is no file included for that phase, but you should make sure that you are still using the BigDecimal and MutableBigInteger file(s) applied in the previous phases. So, to be very clear, the files that make up each phase are: Phase 1: BigInteger.java.phase1 BigDecimal.java.phase1 (since BigInteger.pow is accelerated, the workaround in BigDecimal is removed.) Phase 2: BigInteger.java.phase2 Phase 3: BigInteger.java.phase3 MutableBigInteger.java.phase3 (to use Burnikel-Ziegler divide) Phase 4: BigInteger.java.phase4 For your reference, the final versions of each file are contained with the ".final" suffix. These will be identical to previous phases applied, and you don't have to apply them, but if someone wants to quickly drop in the best improvements to their own JDK, just use the 3 files with the ".final" suffix. Let me know if you have any issues with these. Tim and Brian, you might decide amongst yourselves who wants to file the issues for phases 3 and 4. I don't know if Brian has any magical powers to make the issues skip the QA process.

More information about the core-libs-dev mailing list