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,258 ****
       */
      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.
       */
      static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;
  
      /**
       * 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
--- 242,266 ----
       */
      private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;
  
      /**
       * The threshold value for using Burnikel-Ziegler division.  If the number
!      * 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,2026 ****
       * @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);
          }
      }
--- 2023,2034 ----
       * @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 (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
!                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
              return divideKnuth(val);
          } else {
              return divideBurnikelZiegler(val);
          }
      }
*** 2052,2063 ****
       *         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);
          }
      }
--- 2060,2071 ----
       *         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 (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
!                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
              return divideAndRemainderKnuth(val);
          } else {
              return divideAndRemainderBurnikelZiegler(val);
          }
      }
*** 2081,2092 ****
       *         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);
          }
      }
--- 2089,2100 ----
       *         remainder computed.
       * @return {@code this % val}
       * @throws ArithmeticException if {@code val} is zero.
       */
      public BigInteger remainder(BigInteger val) {
!         if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
!                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
              return remainderKnuth(val);
          } else {
              return remainderBurnikelZiegler(val);
          }
      }