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

Print this page
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


 227     private static final int TOOM_COOK_THRESHOLD = 240;
 228 
 229     /**
 230      * The threshold value for using Karatsuba squaring.  If the number
 231      * of ints in the number are larger than this value,
 232      * Karatsuba squaring will be used.   This value is found
 233      * experimentally to work well.
 234      */
 235     private static final int KARATSUBA_SQUARE_THRESHOLD = 128;
 236 
 237     /**
 238      * The threshold value for using Toom-Cook squaring.  If the number
 239      * of ints in the number are larger than this value,
 240      * Toom-Cook squaring will be used.   This value is found
 241      * experimentally to work well.
 242      */
 243     private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;
 244 
 245     /**
 246      * The threshold value for using Burnikel-Ziegler division.  If the number
 247      * of ints in the number are larger than this value,
 248      * Burnikel-Ziegler division will be used.   This value is found
 249      * experimentally to work well.
 250      */
 251     static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;
 252 
 253     /**









 254      * The threshold value for using Schoenhage recursive base conversion. If
 255      * the number of ints in the number are larger than this value,
 256      * the Schoenhage algorithm will be used.  In practice, it appears that the
 257      * Schoenhage routine is faster for any threshold down to 2, and is
 258      * relatively flat for thresholds between 2-25, so this choice may be
 259      * varied within this range for very small effect.
 260      */
 261     private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
 262 
 263     //Constructors
 264 
 265     /**
 266      * Translates a byte array containing the two's-complement binary
 267      * representation of a BigInteger into a BigInteger.  The input array is
 268      * assumed to be in <i>big-endian</i> byte-order: the most significant
 269      * byte is in the zeroth element.
 270      *
 271      * @param  val big-endian two's-complement binary representation of
 272      *         BigInteger.
 273      * @throws NumberFormatException {@code val} is zero bytes long.


2000         t1 = t1.subtract(tm1).subtract(vinf);
2001         t2 = t2.subtract(vinf.shiftLeft(1));
2002         tm1 = tm1.subtract(t2);
2003 
2004         // Number of bits to shift left.
2005         int ss = k*32;
2006 
2007         return vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
2008     }
2009 
2010     // Division
2011 
2012     /**
2013      * Returns a BigInteger whose value is {@code (this / val)}.
2014      *
2015      * @param  val value by which this BigInteger is to be divided.
2016      * @return {@code this / val}
2017      * @throws ArithmeticException if {@code val} is zero.
2018      */
2019     public BigInteger divide(BigInteger val) {
2020         if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2021                 val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
2022             return divideKnuth(val);
2023         } else {
2024             return divideBurnikelZiegler(val);
2025         }
2026     }
2027 
2028     /**
2029      * Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
2030      *
2031      * @param  val value by which this BigInteger is to be divided.
2032      * @return {@code this / val}
2033      * @throws ArithmeticException if {@code val} is zero.
2034      * @see MutableBigInteger#divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
2035      */
2036     private BigInteger divideKnuth(BigInteger val) {
2037         MutableBigInteger q = new MutableBigInteger(),
2038                           a = new MutableBigInteger(this.mag),
2039                           b = new MutableBigInteger(val.mag);
2040 
2041         a.divideKnuth(b, q, false);
2042         return q.toBigInteger(this.signum * val.signum);
2043     }
2044 
2045     /**
2046      * Returns an array of two BigIntegers containing {@code (this / val)}
2047      * followed by {@code (this % val)}.
2048      *
2049      * @param  val value by which this BigInteger is to be divided, and the
2050      *         remainder computed.
2051      * @return an array of two BigIntegers: the quotient {@code (this / val)}
2052      *         is the initial element, and the remainder {@code (this % val)}
2053      *         is the final element.
2054      * @throws ArithmeticException if {@code val} is zero.
2055      */
2056     public BigInteger[] divideAndRemainder(BigInteger val) {
2057         if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2058                 val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
2059             return divideAndRemainderKnuth(val);
2060         } else {
2061             return divideAndRemainderBurnikelZiegler(val);
2062         }
2063     }
2064 
2065     /** Long division */
2066     private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
2067         BigInteger[] result = new BigInteger[2];
2068         MutableBigInteger q = new MutableBigInteger(),
2069                           a = new MutableBigInteger(this.mag),
2070                           b = new MutableBigInteger(val.mag);
2071         MutableBigInteger r = a.divideKnuth(b, q);
2072         result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
2073         result[1] = r.toBigInteger(this.signum);
2074         return result;
2075     }
2076 
2077     /**
2078      * Returns a BigInteger whose value is {@code (this % val)}.
2079      *
2080      * @param  val value by which this BigInteger is to be divided, and the
2081      *         remainder computed.
2082      * @return {@code this % val}
2083      * @throws ArithmeticException if {@code val} is zero.
2084      */
2085     public BigInteger remainder(BigInteger val) {
2086         if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2087                 val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
2088             return remainderKnuth(val);
2089         } else {
2090             return remainderBurnikelZiegler(val);
2091         }
2092     }
2093 
2094     /** Long division */
2095     private BigInteger remainderKnuth(BigInteger val) {
2096         MutableBigInteger q = new MutableBigInteger(),
2097                           a = new MutableBigInteger(this.mag),
2098                           b = new MutableBigInteger(val.mag);
2099 
2100         return a.divideKnuth(b, q).toBigInteger(this.signum);
2101     }
2102 
2103     /**
2104      * Calculates {@code this / val} using the Burnikel-Ziegler algorithm.
2105      * @param  val the divisor
2106      * @return {@code this / val}
2107      */




 227     private static final int TOOM_COOK_THRESHOLD = 240;
 228 
 229     /**
 230      * The threshold value for using Karatsuba squaring.  If the number
 231      * of ints in the number are larger than this value,
 232      * Karatsuba squaring will be used.   This value is found
 233      * experimentally to work well.
 234      */
 235     private static final int KARATSUBA_SQUARE_THRESHOLD = 128;
 236 
 237     /**
 238      * The threshold value for using Toom-Cook squaring.  If the number
 239      * of ints in the number are larger than this value,
 240      * Toom-Cook squaring will be used.   This value is found
 241      * experimentally to work well.
 242      */
 243     private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;
 244 
 245     /**
 246      * The threshold value for using Burnikel-Ziegler division.  If the number
 247      * of ints in the divisor are larger than this value, Burnikel-Ziegler
 248      * division may be used.  This value is found experimentally to work well.

 249      */
 250     static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;
 251 
 252     /**
 253      * The offset value for using Burnikel-Ziegler division.  If the number
 254      * of ints in the divisor exceeds the Burnikel-Ziegler threshold, and the
 255      * number of ints in the dividend is greater than the number of ints in the
 256      * divisor plus this value, Burnikel-Ziegler division will be used.  This
 257      * value is found experimentally to work well.
 258      */
 259     static final int BURNIKEL_ZIEGLER_OFFSET = 40;
 260 
 261     /**
 262      * The threshold value for using Schoenhage recursive base conversion. If
 263      * the number of ints in the number are larger than this value,
 264      * the Schoenhage algorithm will be used.  In practice, it appears that the
 265      * Schoenhage routine is faster for any threshold down to 2, and is
 266      * relatively flat for thresholds between 2-25, so this choice may be
 267      * varied within this range for very small effect.
 268      */
 269     private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
 270 
 271     //Constructors
 272 
 273     /**
 274      * Translates a byte array containing the two's-complement binary
 275      * representation of a BigInteger into a BigInteger.  The input array is
 276      * assumed to be in <i>big-endian</i> byte-order: the most significant
 277      * byte is in the zeroth element.
 278      *
 279      * @param  val big-endian two's-complement binary representation of
 280      *         BigInteger.
 281      * @throws NumberFormatException {@code val} is zero bytes long.


2008         t1 = t1.subtract(tm1).subtract(vinf);
2009         t2 = t2.subtract(vinf.shiftLeft(1));
2010         tm1 = tm1.subtract(t2);
2011 
2012         // Number of bits to shift left.
2013         int ss = k*32;
2014 
2015         return vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
2016     }
2017 
2018     // Division
2019 
2020     /**
2021      * Returns a BigInteger whose value is {@code (this / val)}.
2022      *
2023      * @param  val value by which this BigInteger is to be divided.
2024      * @return {@code this / val}
2025      * @throws ArithmeticException if {@code val} is zero.
2026      */
2027     public BigInteger divide(BigInteger val) {
2028         if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2029                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
2030             return divideKnuth(val);
2031         } else {
2032             return divideBurnikelZiegler(val);
2033         }
2034     }
2035 
2036     /**
2037      * Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
2038      *
2039      * @param  val value by which this BigInteger is to be divided.
2040      * @return {@code this / val}
2041      * @throws ArithmeticException if {@code val} is zero.
2042      * @see MutableBigInteger#divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
2043      */
2044     private BigInteger divideKnuth(BigInteger val) {
2045         MutableBigInteger q = new MutableBigInteger(),
2046                           a = new MutableBigInteger(this.mag),
2047                           b = new MutableBigInteger(val.mag);
2048 
2049         a.divideKnuth(b, q, false);
2050         return q.toBigInteger(this.signum * val.signum);
2051     }
2052 
2053     /**
2054      * Returns an array of two BigIntegers containing {@code (this / val)}
2055      * followed by {@code (this % val)}.
2056      *
2057      * @param  val value by which this BigInteger is to be divided, and the
2058      *         remainder computed.
2059      * @return an array of two BigIntegers: the quotient {@code (this / val)}
2060      *         is the initial element, and the remainder {@code (this % val)}
2061      *         is the final element.
2062      * @throws ArithmeticException if {@code val} is zero.
2063      */
2064     public BigInteger[] divideAndRemainder(BigInteger val) {
2065         if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2066                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
2067             return divideAndRemainderKnuth(val);
2068         } else {
2069             return divideAndRemainderBurnikelZiegler(val);
2070         }
2071     }
2072 
2073     /** Long division */
2074     private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
2075         BigInteger[] result = new BigInteger[2];
2076         MutableBigInteger q = new MutableBigInteger(),
2077                           a = new MutableBigInteger(this.mag),
2078                           b = new MutableBigInteger(val.mag);
2079         MutableBigInteger r = a.divideKnuth(b, q);
2080         result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
2081         result[1] = r.toBigInteger(this.signum);
2082         return result;
2083     }
2084 
2085     /**
2086      * Returns a BigInteger whose value is {@code (this % val)}.
2087      *
2088      * @param  val value by which this BigInteger is to be divided, and the
2089      *         remainder computed.
2090      * @return {@code this % val}
2091      * @throws ArithmeticException if {@code val} is zero.
2092      */
2093     public BigInteger remainder(BigInteger val) {
2094         if (val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
2095                 mag.length - val.mag.length < BURNIKEL_ZIEGLER_OFFSET) {
2096             return remainderKnuth(val);
2097         } else {
2098             return remainderBurnikelZiegler(val);
2099         }
2100     }
2101 
2102     /** Long division */
2103     private BigInteger remainderKnuth(BigInteger val) {
2104         MutableBigInteger q = new MutableBigInteger(),
2105                           a = new MutableBigInteger(this.mag),
2106                           b = new MutableBigInteger(val.mag);
2107 
2108         return a.divideKnuth(b, q).toBigInteger(this.signum);
2109     }
2110 
2111     /**
2112      * Calculates {@code this / val} using the Burnikel-Ziegler algorithm.
2113      * @param  val the divisor
2114      * @return {@code this / val}
2115      */