src/share/classes/java/math/BigInteger.java

rev 7721 : 8014319: Faster division of large integers
Summary: Implement Burnickel-Ziegler division algorithm in BigInteger
Reviewed-by: bpb, martin
Contributed-by: Tim Buktu <tbuktu@hotmail.com>

@@ -31,11 +31,10 @@
 
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.ObjectStreamField;
-import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Random;
 import sun.misc.DoubleConsts;
 import sun.misc.FloatConsts;
 

@@ -99,10 +98,11 @@
  *
  * @see     BigDecimal
  * @author  Josh Bloch
  * @author  Michael McCloskey
  * @author  Alan Eliasen
+ * @author  Timothy Buktu
  * @since JDK1.1
  */
 
 public class BigInteger extends Number implements Comparable<BigInteger> {
     /**

@@ -213,10 +213,18 @@
      * experimentally to work well.
      */
     private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
 
     /**
+     * The threshold value for using Burnikel-Ziegler division.  If the number
+     * of ints in the number are larger than this value,
+     * Burnikel-Ziegler division will be used.   This value is found
+     * experimentally to work well.
+     */
+    static final int BURNIKEL_ZIEGLER_THRESHOLD = 50;
+
+    /**
      * The threshold value for using Schoenhage recursive base conversion. If
      * the number of ints in the number are larger than this value,
      * the Schoenhage algorithm will be used.  In practice, it appears that the
      * Schoenhage routine is faster for any threshold down to 2, and is
      * relatively flat for thresholds between 2-25, so this choice may be

@@ -1934,15 +1942,30 @@
      * @param  val value by which this BigInteger is to be divided.
      * @return {@code this / val}
      * @throws ArithmeticException if {@code val} is zero.
      */
     public BigInteger divide(BigInteger val) {
+        if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+            return divideKnuth(val);
+        else
+            return divideBurnikelZiegler(val);
+    }
+
+    /**
+     * Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
+     *
+     * @param  val value by which this BigInteger is to be divided.
+     * @return {@code this / val}
+     * @throws ArithmeticException if {@code val} is zero.
+     * @see MutableBigInteger#divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
+     */
+    private BigInteger divideKnuth(BigInteger val) {
         MutableBigInteger q = new MutableBigInteger(),
                           a = new MutableBigInteger(this.mag),
                           b = new MutableBigInteger(val.mag);
 
-        a.divide(b, q, false);
+        a.divideKnuth(b, q, false);
         return q.toBigInteger(this.signum * val.signum);
     }
 
     /**
      * Returns an array of two BigIntegers containing {@code (this / val)}

@@ -1954,15 +1977,23 @@
      *         is the initial element, and the remainder {@code (this % val)}
      *         is the final element.
      * @throws ArithmeticException if {@code val} is zero.
      */
     public BigInteger[] divideAndRemainder(BigInteger val) {
+        if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+            return divideAndRemainderKnuth(val);
+        else
+            return divideAndRemainderBurnikelZiegler(val);
+    }
+
+    /** Long division */
+    private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
         BigInteger[] result = new BigInteger[2];
         MutableBigInteger q = new MutableBigInteger(),
                           a = new MutableBigInteger(this.mag),
                           b = new MutableBigInteger(val.mag);
-        MutableBigInteger r = a.divide(b, q);
+        MutableBigInteger r = a.divideKnuth(b, q);
         result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
         result[1] = r.toBigInteger(this.signum);
         return result;
     }
 

@@ -1973,15 +2004,55 @@
      *         remainder computed.
      * @return {@code this % val}
      * @throws ArithmeticException if {@code val} is zero.
      */
     public BigInteger remainder(BigInteger val) {
+        if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+            return remainderKnuth(val);
+        else
+            return remainderBurnikelZiegler(val);
+    }
+
+    /** Long division */
+    private BigInteger remainderKnuth(BigInteger val) {
         MutableBigInteger q = new MutableBigInteger(),
                           a = new MutableBigInteger(this.mag),
                           b = new MutableBigInteger(val.mag);
 
-        return a.divide(b, q).toBigInteger(this.signum);
+        return a.divideKnuth(b, q).toBigInteger(this.signum);
+    }
+
+    /**
+     * Calculates {@code this / val} using the Burnikel-Ziegler algorithm.
+     * @param  val the divisor
+     * @return {@code this / val}
+     */
+    private BigInteger divideBurnikelZiegler(BigInteger val) {
+        return divideAndRemainderBurnikelZiegler(val)[0];
+    }
+
+    /**
+     * Calculates {@code this % val} using the Burnikel-Ziegler algorithm.
+     * @param val the divisor
+     * @return {@code this % val}
+     */
+    private BigInteger remainderBurnikelZiegler(BigInteger val) {
+        return divideAndRemainderBurnikelZiegler(val)[1];
+    }
+
+    /**
+     * Computes {@code this / val} and {@code this % val} using the
+     * Burnikel-Ziegler algorithm.
+     * @param val the divisor
+     * @return an array containing the quotient and remainder
+     */
+    private BigInteger[] divideAndRemainderBurnikelZiegler(BigInteger val) {
+        MutableBigInteger q = new MutableBigInteger();
+        MutableBigInteger r = new MutableBigInteger(this).divideAndRemainderBurnikelZiegler(new MutableBigInteger(val), q);
+        BigInteger qBigInt = q.isZero() ? ZERO : q.toBigInteger(signum*val.signum);
+        BigInteger rBigInt = r.isZero() ? ZERO : r.toBigInteger(signum);
+        return new BigInteger[] {qBigInt, rBigInt};
     }
 
     /**
      * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
      * Note that {@code exponent} is an integer rather than a BigInteger.

@@ -3397,11 +3468,11 @@
         return buf.toString();
     }
 
     /**
      * Converts the specified BigInteger to a string and appends to
-     * <code>sb</code>.  This implements the recursive Schoenhage algorithm
+     * {@code sb}.  This implements the recursive Schoenhage algorithm
      * for base conversions.
      * <p/>
      * See Knuth, Donald,  _The Art of Computer Programming_, Vol. 2,
      * Answers to Exercises (4.4) Question 14.
      *

@@ -3448,11 +3519,11 @@
     /**
      * Returns the value radix^(2^exponent) from the cache.
      * If this value doesn't already exist in the cache, it is added.
      * <p/>
      * This could be changed to a more complicated caching method using
-     * <code>Future</code>.
+     * {@code Future}.
      */
     private static BigInteger getRadixConversionCache(int radix, int exponent) {
         BigInteger[] cacheLine = powerCache[radix]; // volatile read
         if (exponent < cacheLine.length) {
             return cacheLine[exponent];