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

[cowwoc]

     Sounds good. Thanks for the clarification.

Gili

On 01/10/2013 9:25 PM, Dmitry Nadezhin wrote:
> I see that I misused the word "to clamp" in this discussion.
> I guess that addition with "clumping" means:
> return x + y < MIN_VALUE ? MIN_VALUE : x + y > MAX_VALUE ? MAX_VALUE : x +
> y;
>
> The patch actually throws ArithmeticException on overflow:
> if (x + y < MIN_VALUE || x + y > MAX_VALUE) throw new ArithmetiException();
> else return x + y;
>
> The word "clamp" appeared in the discussion only.
> Comments in the patch don't contain it. They say:
>
> BigInteger constructors and operations throw {@code
> ArithmeticException} whenthe result is out of the supported range.
>
>
>
>
> On Tue, Oct 1, 2013 at 11:45 PM, cowwoc <cowwoc at bbs.darktech.org> wrote:
>
>>      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<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<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<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<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<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<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<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<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/<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<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>
>>>>>> <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-****<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<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-****<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<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
>>>>>>
>>>>>>