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