# What is the range of BigInteger values ?

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

```