What is the range of BigInteger values ?

[Dmitry Nadezhin]

Correction.
The unrestricted BigInteger range is
( -pow(2, (pow(2,31) - 1)*32) , pow(2, (pow(2,31) - 1)*32) )
instead of
( -pow(2, pow(2,31) + 31) , pow(2, pow(2,31) + 31).

The restricted BigInteger range
[ -pow(2, pow(2,31) - 1), pow(2, pow(2,31) - 1) )
is ok.



On Tue, Jun 25, 2013 at 11:48 AM, Dmitry Nadezhin <dmitry.nadezhin at gmail.com
> wrote:

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