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

[Weijun Wang]

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/view_bug.do?bug_id=4837946 (update synopsis/description)
>> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
>>
>> Phase 2: Faster string conversion of large integers
>> * Recursive Schoenhage toString() routines.
>> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=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.
>