What is the range of BigInteger values ? (original) (raw)
Dmitry Nadezhin dmitry.nadezhin at gmail.com
Tue Jun 25 07:48:18 UTC 2013
- Previous message: hg: jdk8/tl/jdk: 8017550: Fix doclint issues in java.lang and subpackages
- Next message: What is the range of BigInteger values ?
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Primitive integer types have well-specified value ranges byte [ -pow(2,7) , pow(2,7) ) short [ -pow(2,15) , pow(2,15) ) int [ -pow(2,31) , pow(2,31) ) long [ -pow(2,63) , pow(2,63) ) .
Primitive operations on these types wrap-around in case of overflow, but there are methods which throws ArithmeticExceptions in case of overflow like static int Math.addExact(int x, int y) .
BigInteger type represents "arbitrary-precision integers". BigInteger operation don't wrap-around. However, it is an illusion that range of BigInteger values is unbounded. Nothing in computer is unbounded. Let's explore the BigInteger range.
The magnitude of BigInteger is stored in int[] array. Number of element in array doesn't exceed pow(2,31) - 1. Each element contaons 32 bits. So the range of BigInteger is surely contained in ( -pow(2, pow(2,31) + 31) , pow(2, pow(2,31) + 31).
However, there are methods that may return invalid results on very large BigInteger values: int BigInteger.bitLength(); int BigInteger.bitCount(); int BigInteger.getLowestSetBit(); They return primitive "int" values, so they can't return numbers larger then Integer.MAX_VALUE .
The method BigInteger.bitLength() returns correct result for BigInteger values in the range [ -pow(2, pow(2,31) - 1), pow(2, pow(2,31) - 1) ) . The methods bitCount() and getLowestSetBit() also return correct result in this range.
I recollect this issue because:
- The asymptotic time of BigInteger operations became better after Alan Eliasen's changes, so huge BigInteger values are more likely to appear in user programs;
- I found a call of bitLength() method in the line BigInteger.java:3431 of this WebRev http://cr.openjdk.java.net/~bpb/4641897/
I see a few options with this issue:
Specify that range of BigInteger is [ -pow(2, pow(2,31) - 1), pow(2, pow(2,31) - 1) ) and throw an ArithmeticException() on attempt to construct values out of this range .
Keep the range unrestricted ( -pow(2, pow(2,31) + 31) , pow(2, pow(2,31) + 31). Define new methods long BigInteger.bitLengthLong(); long BigInteger.bitCountLong(); long BigInteger.getLowestSetBitLong(); Deprecate int BigInteger.bitLength(); int BigInteger.bitCount(); int BigInteger.getLowestSetBit(); Verify all other BigInteger methods that they are correct on huge values.
Keep the range unrestricted ( -pow(2, pow(2,31) + 31) , pow(2, pow(2,31) + 31). Methods int BigInteger.bitLength(); int BigInteger.bitCount(); int BigInteger.getLowestSetBit(); throw Exception on huge values Verify all other BigInteger methods that they are correct on huge values.
My preference is (1).
- Previous message: hg: jdk8/tl/jdk: 8017550: Fix doclint issues in java.lang and subpackages
- Next message: What is the range of BigInteger values ?
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]