Mercurial > hg > openjdk > jdk8 > jdk
changeset 8953:303f4bccfca2
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: darcy
author | bpb |
---|---|
date | Thu, 05 Dec 2013 07:45:27 -0800 |
parents | d3c4e8fe98c3 |
children | 72ea199e3e1b |
files | src/share/classes/java/math/BigInteger.java src/share/classes/java/math/MutableBigInteger.java |
diffstat | 2 files changed, 19 insertions(+), 11 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/math/BigInteger.java Thu Dec 05 07:44:59 2013 -0800 +++ b/src/share/classes/java/math/BigInteger.java Thu Dec 05 07:45:27 2013 -0800 @@ -244,13 +244,21 @@ /** * 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 @@ -2017,8 +2025,8 @@ * @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); @@ -2054,8 +2062,8 @@ * @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); @@ -2083,8 +2091,8 @@ * @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);
--- a/src/share/classes/java/math/MutableBigInteger.java Thu Dec 05 07:44:59 2013 -0800 +++ b/src/share/classes/java/math/MutableBigInteger.java Thu Dec 05 07:45:27 2013 -0800 @@ -1148,8 +1148,8 @@ } MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) { - if (intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD || - b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD) { + if (b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD || + intLen - b.intLen < BigInteger.BURNIKEL_ZIEGLER_OFFSET) { return divideKnuth(b, quotient, needRemainder); } else { return divideAndRemainderBurnikelZiegler(b, quotient);