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

Wed Oct 2 01:25:55 UTC 2013

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