What is the range of BigInteger values ? (original) (raw)

Dmitry Nadezhin dmitry.nadezhin at gmail.com
Tue Jun 25 07:48:18 UTC 2013


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:

  1. 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;
  2. 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:

  1. 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 .

  2. 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.

  3. 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).



More information about the core-libs-dev mailing list