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

Tue Oct 1 19:45:52 UTC 2013

     I prefer throwing exceptions on unusual conditions (e.g. overflow) 
and letting the user clamp the value if they so wish. Clamping will lead 
to unexpected behavior once values fall outside this range. Yes, it will 
be documented, but I daresay most applications won't ever check for it 
and produce incorrect results as a consequence.

Gili

On 01/10/2013 2:19 PM, Dmitry Nadezhin wrote:
> Dear BigInteger experts,
> Do you have comments to my previous message ?
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html
>
>
> On Sat, Sep 21, 2013 at 8:13 AM, Dmitry Nadezhin
> <dmitry.nadezhin at gmail.com>wrote:
>
>> 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
>>>>
>>>