RFC 6910473: BigInteger negative bit length, value range, and future prospects

[Dmitry Nadezhin]

It is important that BigInteger objects be full-fledged instances on which
all methods may be correctly invoked.

This bitLength bug started this discussion:
P4 JDK-6910473 : java.math.BigInteger.bitLength() may return negative "int"
on large numbers
https://bugs.openjdk.java.net/browse/JDK-6910473

I reviewed the behavior of very large BigInteger objects and found a few
other bugs:

P3 JDK-8021204 : Constructor BigInteger(String val, int radix) doesn't
detect overflow
https://bugs.openjdk.java.net/browse/JDK-8021204

P3 JDK-8021203 : BigInteger.doubleValue/floatValue returns 0.0 instead of
Infinity
https://bugs.openjdk.java.net/browse/JDK-8021203

P3 JDK-8022780 : Incorrect BigInteger division because of
MutableBigInteger.bitLength() overflow
https://bugs.openjdk.java.net/browse/JDK-8022780

In these bugs (and also in the original bitLength bug) a BigInteger method
silently returns an incorrect result.
Silently incorrect behavior may lead to unexpected failures and difficult
to debug scenarios in applications.

Some applications try to adapt to these bugs with performance overhead. As
clients of java.math.BigInteger can't trust bitLength() , they have to
perform inefficient checks for bitLength overflow. See for example the
methods isValidFloat, isValidDouble, bitLengthOverflow in lines 135-167 of
this file from the Scala library:
https://github.com/scala/scala/blob/master/src/library/scala/math/BigInt.scala

As Brian said:
http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018403.html
there are two ways to fix bitLength bug:
a) simply by throwing an ArithmeticException if the bit length as an int
would be negative;
b) to define BigInteger to support a limited range and to clamp to that
range in the constructor,
   throwing an ArithmeticException if the supplied parameter(s) would cause
the BigInteger to overflow.
This can be applied to other bugs too.

We found a few bugs appearing on large BigInteger objects, but I'm not sure
that we find all of them.
So I prefer to limit the supported range because this not only fixes known
bugs
but also prevents the occurrence of bugs that haven't been discovered yet.

Joe Darcy suggested that the limiting of the supported range would not be
a specification change but instead an implementation note
"in JDK 8, BigInteger operates on values in the range ....":
http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-July/018644.html

So I prepared a patch that fixes the bitLength bug together with another
bugs mentioned above.

The WebRev is here:
http://cr.openjdk.java.net/~bpb/BigIntRange/

This patch limits the supported range of BigInteger in JDK 8. The APIdoc of
the class contains an implementation note that BigInteger constructors and
operations throw an ArithmeticException when the result is out of the
supported range.
The supported range in JDK 8 is -2^Integer.MAX_VALUE to
2^Integer.MAX_VALUE, exclusive. This range is symmetric to make patch
simpler.

All constructors contains call checkRange() guarded by cheap test
"mag.length >= MAX_MAG_LENGTH". The checkRange() method throws an
ArithmeticException if the BigInteger instance would be out of the
supported range. APIdocs of public constructors and methods contain an
appropriate @throws ArithmeticException clause .

The patch contains a fix of various other problems related to overflow:
1) Calculation of prime searchLen suffered from int overflow when bitLength
was large;
2) int overflow in pow() method;
3) Overflow of intermediate results in modPow() method;
4) Removed the implementation restriction on Integer.MIN_VALUE
  in shiftLeft() and shiftRight() methods introduced during the fix of:
JDK-6371401 : java.math.BigInteger.shift(Integer.MIN_VALUE) throws
StackOverflowError
https://bugs.openjdk.java.net/browse/JDK-6371401

Please, review this patch.



On Wed, Jul 3, 2013 at 6:06 AM, Joseph Darcy <joe.darcy at oracle.com> wrote:

> Hello,
>
> A quick note on this issue, before the recent work to use better
> algorithms for BigInteger arithmetic operation, working with huge numbers
> was impractical and thus BigInteger.bitLength misbehavior was mostly an
> academic concern. With the better algorithms, exposure to these large
> values is likely to increase so BigInteger.bitLength should do something
> reasonable.
>
> There are at least two implementation limits of note in the current code:
>
> * Total bit length given a single backing array
> * Max size of serializable BigInteger given old byte-array based format.
>
> My preference for addressing this issue includes adding an implementation
> note along the lines of "in JDK 8, BigInteger operates on values in the
> range ...." without requiring that range to be part of the specification.
>
> Cheers,
>
> -Joe
>
>
> On 6/25/2013 6:18 PM, Brian Burkhalter wrote:
>
>> This request for comment regards this issue
>>
>> http://bugs.sun.com/**bugdatabase/view_bug.do?bug_**id=6910473<http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6910473>
>> BigInteger.bigLength() may return negative value for large numbers
>>
>> but more importantly Dmitry's thread
>>
>> http://mail.openjdk.java.net/**pipermail/core-libs-dev/2013-**
>> June/018345.html<http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018345.html>
>> What is the range of BigInteger values?
>>
>> The issue may be fixed superficially simply by throwing an
>> ArithmeticException if the bit length as an int would be negative. A better
>> fix suggested both in the issue description and in the aforementioned
>> thread (option 1 of 3), is to define BigInteger to support a limited range
>> and to clamp to that range in the constructor, throwing an
>> ArithmeticException if the supplied parameter(s) would cause the BigInteger
>> to overflow. This check would be relatively inexpensive. The suggested
>> constraint range is
>> [ -pow(2, pow(2,31) - 1), pow(2, pow(2,31) - 1) )
>> This constraint would guarantee that all BigInteger instances are capable
>> of accurately returning their properties such as bit length, bit count, etc.
>>
>> This naturally would require a minor specification change to BigInteger.
>> The question is whether this change would limit any future developments of
>> this and related classes. For example, one could envision BigInteger
>> supporting bit lengths representable by a long instead of an int. In this
>> case the second option would be preferable.
>>
>> It has been suggested that an alternative to extending the ranges
>> supported by BigInteger would be to define a different class altogether to
>> handle the larger ranges, keeping BigInteger as a well-specified API for
>> the ranges it supports. Other related classes for arbitrary precision
>> binary floating point and rational numbers might also be considered.
>>
>> In summary the specific questions being posed here are:
>>
>> 1) what is the general opinion on clamping the range of BigInteger and
>> the various options suggested at the end of
>>
>> http://mail.openjdk.java.net/**pipermail/core-libs-dev/2013-**
>> June/018345.html<http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/018345.html>?
>>
>> 2) what are the forward looking thoughts on handling integers outside the
>> current BigInteger range?
>>
>>  From a practical point of view, any changes need to be considered with
>> respect to what may be done in the short term (JDK 8) versus the long (JDK
>> 9), so to speak.
>>
>> Thanks,
>>
>> Brian
>>
>
>