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 <cow...@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.nadez...@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.da...@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
