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

rev 8880 : 8029501: BigInteger division algorithm selection heuristic is incorrect
Summary: Change Burnikel-Ziegler division heuristic to require that the dividend int-length exceed that of the divisor by a minimum amount.
Reviewed-by: TBD

@@ -242,17 +242,25 @@
      */
     private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;
 
     /**
      * 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.
+     * of ints in the divisor are larger than this value, Burnikel-Ziegler
+     * division may be used.  This value is found experimentally to work well.
      */
     static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;
 
     /**
+     * The offset value for using Burnikel-Ziegler division.  If the number
+     * of ints in the divisor exceeds the Burnikel-Ziegler threshold, and the
+     * number of ints in the dividend is greater than the number of ints in the
+     * divisor plus this value, Burnikel-Ziegler division will be used.  This
+     * value is found experimentally to work well.
+     */
+    static final int BURNIKEL_ZIEGLER_OFFSET = 40;
+
+    /**
      * 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

@@ -2015,12 +2023,12 @@
      * @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) {
+        if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
+                mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
             return divideKnuth(val);
         } else {
             return divideBurnikelZiegler(val);
         }
     }

@@ -2052,12 +2060,12 @@
      *         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) {
+        if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
+                mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
             return divideAndRemainderKnuth(val);
         } else {
             return divideAndRemainderBurnikelZiegler(val);
         }
     }

@@ -2081,12 +2089,12 @@
      *         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) {
+        if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
+                mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
             return remainderKnuth(val);
         } else {
             return remainderBurnikelZiegler(val);
         }
     }