Description
FULL PRODUCT VERSION :
java version " 1.8.0-ea "
Java(TM) SE Runtime Environment (build 1.8.0-ea-b102)
Java HotSpot(TM) 64-Bit Server VM (build 25.0-b44, mixed mode)
ADDITIONAL OS VERSION INFORMATION :
Linux kisa 3.8.0-26-generic #38-Ubuntu SMP Mon Jun 17 21:43:33 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux
A DESCRIPTION OF THE PROBLEM :
This is the bug in the implementation of BurnikelZiegler division algorithm.
Both dividend and divisor are powers of two. So the expected remainder is zero, and expected quotent is another power of two.
Divident is maximal power of two pow(2, Integer.MAX_VALUE - 1)) from the supported range
[-pow(2,Integer.MAX_VALUE),pow(2,Integer.MAX_VALUE)-1].
Divisor is the first value above BURNIKEL_ZIEGLER_THRESHOLD.
When division algorithms normalizes the divisor, divident becomes out of the supported range
and its " int MutableBigInteger.bitLength() " becomes negative.
See Step 5 in MutableBigInteger.divideAndRemainderBurnikelZiegler .
MutableBigInteger is not in public API so possible fix is to refactor to " long MutableBigInteger.bitLength() "
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the attached test case
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
q.bitLenth=2147482079
r.signum=0
r.bitLength=0
ACTUAL -
q.bitLenth=1600
r.signum=1
r.bitLength=2147483646
REPRODUCIBILITY :
This bug can be reproduced always.
---------- BEGIN SOURCE ----------
import java.math.BigInteger;
public class DivideBug {
public static void main(String[] args) {
BigInteger a = BigInteger.ONE.shiftLeft(2147483646);
BigInteger b = BigInteger.ONE.shiftLeft(1568);
BigInteger[] qr = a.divideAndRemainder(b);
BigInteger q = qr[0];
BigInteger r = qr[1];
System.out.println( " q.bitLenth= " + q.bitLength()); // expected 2147482079
System.out.println( " r.signum= " + r.signum()); // expected 0
System.out.println( " r.bitLength= " + r.bitLength()); // expected 0
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Refactor MutableBigInteger.bitLength() to return " long " instead of " int " .
It is possible because class MutableBigInteger is not in public API.
java version " 1.8.0-ea "
Java(TM) SE Runtime Environment (build 1.8.0-ea-b102)
Java HotSpot(TM) 64-Bit Server VM (build 25.0-b44, mixed mode)
ADDITIONAL OS VERSION INFORMATION :
Linux kisa 3.8.0-26-generic #38-Ubuntu SMP Mon Jun 17 21:43:33 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux
A DESCRIPTION OF THE PROBLEM :
This is the bug in the implementation of BurnikelZiegler division algorithm.
Both dividend and divisor are powers of two. So the expected remainder is zero, and expected quotent is another power of two.
Divident is maximal power of two pow(2, Integer.MAX_VALUE - 1)) from the supported range
[-pow(2,Integer.MAX_VALUE),pow(2,Integer.MAX_VALUE)-1].
Divisor is the first value above BURNIKEL_ZIEGLER_THRESHOLD.
When division algorithms normalizes the divisor, divident becomes out of the supported range
and its " int MutableBigInteger.bitLength() " becomes negative.
See Step 5 in MutableBigInteger.divideAndRemainderBurnikelZiegler .
MutableBigInteger is not in public API so possible fix is to refactor to " long MutableBigInteger.bitLength() "
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the attached test case
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
q.bitLenth=2147482079
r.signum=0
r.bitLength=0
ACTUAL -
q.bitLenth=1600
r.signum=1
r.bitLength=2147483646
REPRODUCIBILITY :
This bug can be reproduced always.
---------- BEGIN SOURCE ----------
import java.math.BigInteger;
public class DivideBug {
public static void main(String[] args) {
BigInteger a = BigInteger.ONE.shiftLeft(2147483646);
BigInteger b = BigInteger.ONE.shiftLeft(1568);
BigInteger[] qr = a.divideAndRemainder(b);
BigInteger q = qr[0];
BigInteger r = qr[1];
System.out.println( " q.bitLenth= " + q.bitLength()); // expected 2147482079
System.out.println( " r.signum= " + r.signum()); // expected 0
System.out.println( " r.bitLength= " + r.bitLength()); // expected 0
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Refactor MutableBigInteger.bitLength() to return " long " instead of " int " .
It is possible because class MutableBigInteger is not in public API.
Attachments
Issue Links
- relates to
-
JDK-6910473 java.math.BigInteger.bitLength() may return negative "int" on large numbers
- Closed
-
JDK-8027595 Enable BigInteger overflow tests in JTREG
- Closed