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