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

Dmitry Nadezhin dmitry.nadezhin at gmail.com
Tue Jun 25 08:33:46 UTC 2013

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