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

Tue Oct 1 18:19:06 UTC 2013

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