Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
The updated patch is here: http://cr.openjdk.java.net/~bpb/6910473/webrev.4/ It contains 4 new small tests - one for each bug: 6910473 BitLengthOverflow.java 8021203 DoubleValueOverflow.java 8021204 StringConstructorOverflow.java 8022780 DivisionOverflow.java Each test catches possible OutOfMemoryError. It passes with a message in System.out when this happens. When I add -javaoption:-Xmx8g to jtreg command-line these four tests (and also ExtremeShiftingTests) fail before the patch and pass after the patch - all without OutOfMemoryError. One of the tests (StringConstructorOverflow) passes because of OutOfMemoryError both before and after the patch with default jtreg command-line on my computer . SymmetricRangeTests.java is intentionally disabled by invalid jtreg tag @ test. It is for manual run only. On Fri, Oct 18, 2013 at 9:58 PM, Alan Bateman alan.bate...@oracle.comwrote: On 18/10/2013 17:24, Dmitry Nadezhin wrote: The WebRev with @ignore in SymmetricRangeTests is here: http://cr.openjdk.java.net/~**bpb/6910473/webrev.3/http://cr.openjdk.java.net/~bpb/6910473/webrev.3/ jtreg ignores the test with a message test result: Error. Test ignored: hugeMemory with default jtreg command-line; jtreg runs it with additional switch -ignore:run. I don't think we want @ignore here as it will cause jtreg to report it as an error (unless run with -ignore:quiet). If we are adding the test but just not having it run automatically then it might be best to just drop the jtreg meta-data completely. Alternatively, if feasible, is to dial-down the test so that it runs without requiring a lot of resources, but perhaps a second mode for interactive runs that does the full thing. -Alan.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
On 17/10/2013 15:59, Dmitry Nadezhin wrote: Another solution may be to exclude the SymmetricRangeTests from automatic test runs, and to keep this file somewhere for manual tests runs only. What do you think about this ? Yes, this make sense. Also we have other examples of long-running or resource-intensive tests have two execution modes. The downside of course is that there is no guarantee that it will be run on a regular basis. Can this be implemented in jtreg (for example by @key hugeMemory tag) ? Keywords are possible but I think there is bigger question/discussion needed on test selection. -Alan
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
The WebRev with @ignore in SymmetricRangeTests is here: http://cr.openjdk.java.net/~bpb/6910473/webrev.3/ jtreg ignores the test with a message test result: Error. Test ignored: hugeMemory with default jtreg command-line; jtreg runs it with additional switch -ignore:run. On Fri, Oct 18, 2013 at 2:12 PM, Alan Bateman alan.bate...@oracle.comwrote: On 17/10/2013 15:59, Dmitry Nadezhin wrote: Another solution may be to exclude the SymmetricRangeTests from automatic test runs, and to keep this file somewhere for manual tests runs only. What do you think about this ? Yes, this make sense. Also we have other examples of long-running or resource-intensive tests have two execution modes. The downside of course is that there is no guarantee that it will be run on a regular basis. Can this be implemented in jtreg (for example by @key hugeMemory tag) ? Keywords are possible but I think there is bigger question/discussion needed on test selection. -Alan
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
On 18/10/2013 17:24, Dmitry Nadezhin wrote: The WebRev with @ignore in SymmetricRangeTests is here: http://cr.openjdk.java.net/~bpb/6910473/webrev.3/ jtreg ignores the test with a message test result: Error. Test ignored: hugeMemory with default jtreg command-line; jtreg runs it with additional switch -ignore:run. I don't think we want @ignore here as it will cause jtreg to report it as an error (unless run with -ignore:quiet). If we are adding the test but just not having it run automatically then it might be best to just drop the jtreg meta-data completely. Alternatively, if feasible, is to dial-down the test so that it runs without requiring a lot of resources, but perhaps a second mode for interactive runs that does the full thing. -Alan.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
On Oct 16, 2013, at 7:46 PM, Dmitry Nadezhin dmitry.nadez...@gmail.com wrote: Thank you, Paul. I tried to combine your and Joe's suggestions in the updated WebRev: http://cr.openjdk.java.net/~bpb/6910473/webrev.2/ Looks good. A slight concern is that the test sets the max heap size to 8g. Not sure what can be done about that. It may cause some execution issues on certain environments. Unfortunately i am not sure we have a good way to classify tests in terms of resource requirements (beyond scraping the jtreg args) to restrict what tests are run in what environments (which i don't think we do), nor i do know of a way for the test itself to not bother testing if there will be insufficient resources. Paul.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
On 15/10/2013 01:27, Brian Burkhalter wrote: Ping! This proposal could use more comments, not to mention review(s). http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html Just to follow up on Paul's observation that the test runs with -Xmx8g. I assume this isn't going to work on 32-bit systems, also I'm sure it will cause problems in other environments too, esp. when running the tests concurrently with a pool of VMs running the tests. Paul's suggestion to have the test just pass if there is insufficient heap is one choice, another might be to test on a smaller range when there isn't enough memory. Another potential approach is to have it launch a new VM with -Xmx8g once you establish that the VM is 64-bit and that there is sufficient memory available. -Alan
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
Another solution may be to exclude the SymmetricRangeTests from automatic test runs, and to keep this file somewhere for manual tests runs only. What do you think about this ? Can this be implemented in jtreg (for example by @key hugeMemory tag) ? On Thu, Oct 17, 2013 at 2:18 PM, Alan Bateman alan.bate...@oracle.comwrote: On 15/10/2013 01:27, Brian Burkhalter wrote: Ping! This proposal could use more comments, not to mention review(s). http://mail.openjdk.java.net/**pipermail/core-libs-dev/2013-** September/021264.htmlhttp://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html Just to follow up on Paul's observation that the test runs with -Xmx8g. I assume this isn't going to work on 32-bit systems, also I'm sure it will cause problems in other environments too, esp. when running the tests concurrently with a pool of VMs running the tests. Paul's suggestion to have the test just pass if there is insufficient heap is one choice, another might be to test on a smaller range when there isn't enough memory. Another potential approach is to have it launch a new VM with -Xmx8g once you establish that the VM is 64-bit and that there is sufficient memory available. -Alan
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
I suggest to insert a line * @ignore hugeMemory to SymmeticRangeTests.java after the line * @test . The automatic run of jtreg with usual arguments fails with diagnostics test result: Error. Test ignored: hugeMemory . If somebody wants to run this test he can run jtreg with additional switch -ignore:run . On Thu, Oct 17, 2013 at 6:59 PM, Dmitry Nadezhin dmitry.nadez...@gmail.comwrote: Another solution may be to exclude the SymmetricRangeTests from automatic test runs, and to keep this file somewhere for manual tests runs only. What do you think about this ? Can this be implemented in jtreg (for example by @key hugeMemory tag) ? On Thu, Oct 17, 2013 at 2:18 PM, Alan Bateman alan.bate...@oracle.comwrote: On 15/10/2013 01:27, Brian Burkhalter wrote: Ping! This proposal could use more comments, not to mention review(s). http://mail.openjdk.java.net/**pipermail/core-libs-dev/2013-** September/021264.htmlhttp://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html Just to follow up on Paul's observation that the test runs with -Xmx8g. I assume this isn't going to work on 32-bit systems, also I'm sure it will cause problems in other environments too, esp. when running the tests concurrently with a pool of VMs running the tests. Paul's suggestion to have the test just pass if there is insufficient heap is one choice, another might be to test on a smaller range when there isn't enough memory. Another potential approach is to have it launch a new VM with -Xmx8g once you establish that the VM is 64-bit and that there is sufficient memory available. -Alan
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
Thank you, Paul.
I tried to combine your and Joe's suggestions in the updated WebRev:
http://cr.openjdk.java.net/~bpb/6910473/webrev.2/
-Dima
On Tue, Oct 15, 2013 at 12:20 PM, Paul Sandoz paul.san...@oracle.comwrote:
Hi,
I took a look at the patch, but i am not an expert in this area.
On BigInteger:
99 * @implNote
100 * BigInteger constructors and operations throw {@code
ArithmeticException} when
101 * the result is out of the supported range. The supported range in
JDK 8 is
102 * -2sup{@code Integer.MAX_VALUE}/sup to
103 * 2sup{@code Integer.MAX_VALUE}/sup, exclusive.
I suggest changing to:
@implNote
BigInteger constructors and operations throw {@code ArithmeticException}
when
the result is out of the supported range of -2sup{@code
Integer.MAX_VALUE}/sup
(exclusive) to 2sup{@code Integer.MAX_VALUE}/sup (exclusive).
I don't think it is worth declaring @throws ArithmeticException for all
relevant constructors and operations. This is likely to be noise for most
people and the implNote is sufficient.
Paul.
On Oct 15, 2013, at 2:27 AM, Brian Burkhalter brian.burkhal...@oracle.com
wrote:
Ping!
This proposal could use more comments, not to mention review(s).
http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html
Thanks,
Brian
On Oct 3, 2013, at 5:58 PM, Brian Burkhalter wrote:
I have reviewed this proposed change a couple of times in its current
form and it looks good to me.
It would be good to see some comments about the general concept from
BigInt cognoscenti, and from (a) Reviewer(s) as concerns the @implNote
addition as well as the new ArithmeticExceptions added at several points in
the javadoc.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
Hi,
I took a look at the patch, but i am not an expert in this area.
On BigInteger:
99 * @implNote
100 * BigInteger constructors and operations throw {@code
ArithmeticException} when
101 * the result is out of the supported range. The supported range in JDK 8
is
102 * -2sup{@code Integer.MAX_VALUE}/sup to
103 * 2sup{@code Integer.MAX_VALUE}/sup, exclusive.
I suggest changing to:
@implNote
BigInteger constructors and operations throw {@code ArithmeticException} when
the result is out of the supported range of -2sup{@code
Integer.MAX_VALUE}/sup
(exclusive) to 2sup{@code Integer.MAX_VALUE}/sup (exclusive).
I don't think it is worth declaring @throws ArithmeticException for all
relevant constructors and operations. This is likely to be noise for most
people and the implNote is sufficient.
Paul.
On Oct 15, 2013, at 2:27 AM, Brian Burkhalter brian.burkhal...@oracle.com
wrote:
Ping!
This proposal could use more comments, not to mention review(s).
http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html
Thanks,
Brian
On Oct 3, 2013, at 5:58 PM, Brian Burkhalter wrote:
I have reviewed this proposed change a couple of times in its current form
and it looks good to me.
It would be good to see some comments about the general concept from BigInt
cognoscenti, and from (a) Reviewer(s) as concerns the @implNote addition as
well as the new ArithmeticExceptions added at several points in the javadoc.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
Ping! This proposal could use more comments, not to mention review(s). http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html Thanks, Brian On Oct 3, 2013, at 5:58 PM, Brian Burkhalter wrote: I have reviewed this proposed change a couple of times in its current form and it looks good to me. It would be good to see some comments about the general concept from BigInt cognoscenti, and from (a) Reviewer(s) as concerns the @implNote addition as well as the new ArithmeticExceptions added at several points in the javadoc.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
Without comments on the contents of the patch, a change in documented
behavior would require a ccc request.
Cheers,
-Joe
On 10/3/2013 5:58 PM, Brian Burkhalter wrote:
I have reviewed this proposed change a couple of times in its current form and
it looks good to me.
It would be good to see some comments about the general concept from BigInt
cognoscenti, and from (a) Reviewer(s) as concerns the @implNote addition as
well as the new ArithmeticExceptions added at several points in the javadoc.
With respect to these latter, in the event the patch were to be approved, would
a CCC request be in order?
Brian
On Oct 1, 2013, at 7:50 PM, cowwoc wrote:
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.htmlhttp://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
I would expect as much, but that's an exercise I'd prefer to avoid at this time if the content does not appear likely to be acceptable. Thanks, Brian On Oct 7, 2013, at 3:26 PM, Joseph Darcy wrote: Without comments on the contents of the patch, a change in documented behavior would require a ccc request.
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
I have reviewed this proposed change a couple of times in its current form and
it looks good to me.
It would be good to see some comments about the general concept from BigInt
cognoscenti, and from (a) Reviewer(s) as concerns the @implNote addition as
well as the new ArithmeticExceptions added at several points in the javadoc.
With respect to these latter, in the event the patch were to be approved, would
a CCC request be in order?
Brian
On Oct 1, 2013, at 7:50 PM, cowwoc wrote:
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.htmlhttp://mail.openjdk.java.net/pipermail/core-libs-dev/2013-September/021264.html
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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.comwrote: 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
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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 On Sat, Sep 21, 2013 at 8:13 AM, Dmitry Nadezhin dmitry.nadez...@gmail.comwrote: 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
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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.htmlhttp://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-6910473https://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-8021204https://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-8021203https://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-8022780https://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.scalahttps://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.htmlhttp://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.htmlhttp://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
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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.htmlhttp://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-6910473https://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-8021204https://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-8021203https://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-8022780https://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.scalahttps://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.htmlhttp://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.htmlhttp://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
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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=6910473http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6910473 BigInteger.bigLength() may return negative value for large
Re: RFC 6910473: BigInteger negative bit length, value range, and future prospects
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 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 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 ? 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
RFC 6910473: BigInteger negative bit length, value range, and future prospects
This request for comment regards this issue 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 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 ? 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
