RFR 8057793 BigDecimal is no longer effectively immutable
Hi there, I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.) The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please? Thanks, Robert --- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Hello, Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale. Thanks for the bug report, -Joe On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Hello, I created a formal webrev: Issue: https://bugs.openjdk.java.net/browse/JDK-8057793 Webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.00/ Based on manual inspection of the revised code the patch looks good to me. The test submitted with the issue now succeeds as do all regression tests in jdk/test/java/math to which I also added the code from the test case in the issue report. Note that this webrev is with respect to JDK 9. Thanks, Brian On Sep 11, 2014, at 6:35 PM, Joe Darcy <joe.darcy@oracle.com> wrote:
Hello,
Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale.
Thanks for the bug report,
-Joe
On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
I forgot to add setScaleDoesNotMutateTest() to main() in ZeroScalingTests. D’oh! Here’s the corrected webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.01/ Thanks, Brian On Sep 12, 2014, at 4:54 PM, Brian Burkhalter <brian.burkhalter@oracle.com> wrote:
Hello,
I created a formal webrev:
Issue: https://bugs.openjdk.java.net/browse/JDK-8057793 Webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.00/
Based on manual inspection of the revised code the patch looks good to me. The test submitted with the issue now succeeds as do all regression tests in jdk/test/java/math to which I also added the code from the test case in the issue report.
Note that this webrev is with respect to JDK 9.
Thanks,
Brian
On Sep 11, 2014, at 6:35 PM, Joe Darcy <joe.darcy@oracle.com> wrote:
Hello,
Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale.
Thanks for the bug report,
-Joe
On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Hi Brian, Other than removing the // bug 8057793 comment on the new test method, this looks good to be pushed. Thanks, -Joe On 9/13/2014 7:56 AM, Brian Burkhalter wrote:
I forgot to add setScaleDoesNotMutateTest() to main() in ZeroScalingTests. D’oh! Here’s the corrected webrev:
http://cr.openjdk.java.net/~bpb/8057793/webrev.01/
Thanks,
Brian
On Sep 12, 2014, at 4:54 PM, Brian Burkhalter <brian.burkhalter@oracle.com> wrote:
Hello,
I created a formal webrev:
Issue: https://bugs.openjdk.java.net/browse/JDK-8057793 Webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.00/
Based on manual inspection of the revised code the patch looks good to me. The test submitted with the issue now succeeds as do all regression tests in jdk/test/java/math to which I also added the code from the test case in the issue report.
Note that this webrev is with respect to JDK 9.
Thanks,
Brian
On Sep 11, 2014, at 6:35 PM, Joe Darcy <joe.darcy@oracle.com> wrote:
Hello,
Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale.
Thanks for the bug report,
-Joe
On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Hi Joe, This has been pushed http://hg.openjdk.java.net/jdk9/dev/jdk/rev/3b20d87c5905 with the indicated comment excised. Thanks, Brian On Sep 13, 2014, at 10:10 AM, Joe Darcy <joe.darcy@oracle.com> wrote:
Other than removing the
// bug 8057793
comment on the new test method, this looks good to be pushed.
Hi Brian, I hope there will be a backport to JDK8? Regards, Robert
On 15 Sep 2014, at 22:14, Brian Burkhalter <brian.burkhalter@oracle.com> wrote:
Hi Joe,
This has been pushed http://hg.openjdk.java.net/jdk9/dev/jdk/rev/3b20d87c5905 with the indicated comment excised.
Thanks,
Brian
On Sep 13, 2014, at 10:10 AM, Joe Darcy <joe.darcy@oracle.com> wrote:
Other than removing the
// bug 8057793
comment on the new test method, this looks good to be pushed.
Hi Robert, That’s the plan. Regards, Brian On Sep 17, 2014, at 2:35 AM, Robbie Gibson <robbiexgibson@yahoo.com> wrote:
I hope there will be a backport to JDK8?
Hi Brian, How are the performance characteristics after the patch? I see that a lot of effort went in to tuning last December under 8029501. By the way, as part of my investigations into this bug I noticed that BigIntegerTest::divideLarge no longer tests the Burnikel-Ziegler part of the division code, since the heuristic to decide Knuth or BZ diverged from the algorithm to generate the test cases (as part of 8029501). Best, Robert On Saturday, 13 September 2014, 2:09, Brian Burkhalter <brian.burkhalter@oracle.com> wrote: Hello, I created a formal webrev: Issue: https://bugs.openjdk.java.net/browse/JDK-8057793 Webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.00/ Based on manual inspection of the revised code the patch looks good to me. The test submitted with the issue now succeeds as do all regression tests in jdk/test/java/math to which I also added the code from the test case in the issue report. Note that this webrev is with respect to JDK 9. Thanks, Brian On Sep 11, 2014, at 6:35 PM, Joe Darcy <joe.darcy@oracle.com> wrote:
Hello,
Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale.
Thanks for the bug report,
-Joe
On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Here is a patch to fix the test bug mentioned previously. The Burnikel-Ziegler division code is now exercised, and you'll be glad to know that the tests still pass! Robert --- BigIntegerTest.java 2014-09-15 15:55:47.632012000 +0200 +++ BigIntegerTestPatched.java 2014-09-15 16:07:53.363563000 +0200 @@ -71,6 +71,7 @@ static final int BITS_TOOM_COOK_SQUARE = 6912; static final int BITS_SCHOENHAGE_BASE = 640; static final int BITS_BURNIKEL_ZIEGLER = 2560; + static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280; static final int ORDER_SMALL = 60; static final int ORDER_MEDIUM = 100; @@ -288,19 +289,19 @@ * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test - * ensures that {@code v} is just under the B-Z threshold and that {@code w} - * and {@code z} are both over the threshold. This implies that {@code u/v} - * uses the standard division algorithm and {@code w/z} uses the B-Z - * algorithm. The results of the two algorithms are then compared using the - * observation described in the foregoing and if they are not equal a - * failure is logged. + * ensures that {@code v} is just under the B-Z threshold, that {@code z} is + * over the threshold and {@code w} is much larger than {@code z}. This + * implies that {@code u/v} uses the standard division algorithm and + * {@code w/z} uses the B-Z algorithm. The results of the two algorithms + * are then compared using the observation described in the foregoing and + * if they are not equal a failure is logged. */ public static void divideLarge() { int failCount = 0; - BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33); + BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33); for (int i=0; i<SIZE; i++) { - BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd); + BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd); BigInteger v = base.add(addend); BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1))); @@ -312,14 +313,14 @@ v = v.negate(); } - int a = 17 + rnd.nextInt(16); + int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16); int b = 1 + rnd.nextInt(16); - BigInteger w = u.multiply(BigInteger.valueOf(1L << a)); - BigInteger z = v.multiply(BigInteger.valueOf(1L << b)); + BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a)); + BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] divideResult = u.divideAndRemainder(v); - divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b))); - divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b)); + divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b)); + divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] bzResult = w.divideAndRemainder(z); if (divideResult[0].compareTo(bzResult[0]) != 0 || On Monday, 15 September 2014, 11:09, Robert Gibson <robbiexgibson@yahoo.com> wrote: Hi Brian, How are the performance characteristics after the patch? I see that a lot of effort went in to tuning last December under 8029501. By the way, as part of my investigations into this bug I noticed that BigIntegerTest::divideLarge no longer tests the Burnikel-Ziegler part of the division code, since the heuristic to decide Knuth or BZ diverged from the algorithm to generate the test cases (as part of 8029501). Best, Robert On Saturday, 13 September 2014, 2:09, Brian Burkhalter <brian.burkhalter@oracle.com> wrote: Hello, I created a formal webrev: Issue: https://bugs.openjdk.java.net/browse/JDK-8057793 Webrev: http://cr.openjdk.java.net/~bpb/8057793/webrev.00/ Based on manual inspection of the revised code the patch looks good to me. The test submitted with the issue now succeeds as do all regression tests in jdk/test/java/math to which I also added the code from the test case in the issue report. Note that this webrev is with respect to JDK 9. Thanks, Brian On Sep 11, 2014, at 6:35 PM, Joe Darcy <joe.darcy@oracle.com> wrote:
Hello,
Hmmm. I haven't dived into the details of the code, but setScale calls out to divide functionality so it is plausible a bug in divide could cause a problem in setScale.
Thanks for the bug report,
-Joe
On 9/9/2014 1:30 AM, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
Hello, This is a test-only change. Issue: https://bugs.openjdk.java.net/browse/JDK-8058505 Webrev: http://cr.openjdk.java.net/~bpb/8058505/webrev.00/ I verified that the updated version passes (as mentioned below) and in fact exercises the B-Z division branch of the library code. Thanks, Brian On Sep 15, 2014, at 7:17 AM, Robert Gibson <robbiexgibson@yahoo.com> wrote:
Here is a patch to fix the test bug mentioned previously. The Burnikel-Ziegler division code is now exercised, and you'll be glad to know that the tests still pass! Robert
--- BigIntegerTest.java 2014-09-15 15:55:47.632012000 +0200 +++ BigIntegerTestPatched.java 2014-09-15 16:07:53.363563000 +0200 @@ -71,6 +71,7 @@ static final int BITS_TOOM_COOK_SQUARE = 6912; static final int BITS_SCHOENHAGE_BASE = 640; static final int BITS_BURNIKEL_ZIEGLER = 2560; + static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280; static final int ORDER_SMALL = 60; static final int ORDER_MEDIUM = 100; @@ -288,19 +289,19 @@ * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test - * ensures that {@code v} is just under the B-Z threshold and that {@code w} - * and {@code z} are both over the threshold. This implies that {@code u/v} - * uses the standard division algorithm and {@code w/z} uses the B-Z - * algorithm. The results of the two algorithms are then compared using the - * observation described in the foregoing and if they are not equal a - * failure is logged. + * ensures that {@code v} is just under the B-Z threshold, that {@code z} is + * over the threshold and {@code w} is much larger than {@code z}. This + * implies that {@code u/v} uses the standard division algorithm and + * {@code w/z} uses the B-Z algorithm. The results of the two algorithms + * are then compared using the observation described in the foregoing and + * if they are not equal a failure is logged. */ public static void divideLarge() { int failCount = 0; - BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33); + BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33); for (int i=0; i<SIZE; i++) { - BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd); + BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd); BigInteger v = base.add(addend); BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1))); @@ -312,14 +313,14 @@ v = v.negate(); } - int a = 17 + rnd.nextInt(16); + int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16); int b = 1 + rnd.nextInt(16); - BigInteger w = u.multiply(BigInteger.valueOf(1L << a)); - BigInteger z = v.multiply(BigInteger.valueOf(1L << b)); + BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a)); + BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] divideResult = u.divideAndRemainder(v); - divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b))); - divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b)); + divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b)); + divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] bzResult = w.divideAndRemainder(z); if (divideResult[0].compareTo(bzResult[0]) != 0 ||
Hi Brian, The test change looks fine; thanks, -Joe On 9/15/2014 1:30 PM, Brian Burkhalter wrote:
Hello,
This is a test-only change.
Issue:https://bugs.openjdk.java.net/browse/JDK-8058505 Webrev:http://cr.openjdk.java.net/~bpb/8058505/webrev.00/ <http://cr.openjdk.java.net/%7Ebpb/8058505/webrev.00/>
I verified that the updated version passes (as mentioned below) and in fact exercises the B-Z division branch of the library code.
Thanks,
Brian
On Sep 15, 2014, at 7:17 AM, Robert Gibson <robbiexgibson@yahoo.com <mailto:robbiexgibson@yahoo.com>> wrote:
Here is a patch to fix the test bug mentioned previously. The Burnikel-Ziegler division code is now exercised, and you'll be glad to know that the tests still pass! Robert
--- BigIntegerTest.java 2014-09-15 15:55:47.632012000 +0200 +++ BigIntegerTestPatched.java 2014-09-15 16:07:53.363563000 +0200 @@ -71,6 +71,7 @@ static final int BITS_TOOM_COOK_SQUARE = 6912; static final int BITS_SCHOENHAGE_BASE = 640; static final int BITS_BURNIKEL_ZIEGLER = 2560; + static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280; static final int ORDER_SMALL = 60; static final int ORDER_MEDIUM = 100; @@ -288,19 +289,19 @@ * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test - * ensures that {@code v} is just under the B-Z threshold and that {@code w} - * and {@code z} are both over the threshold. This implies that {@code u/v} - * uses the standard division algorithm and {@code w/z} uses the B-Z - * algorithm. The results of the two algorithms are then compared using the - * observation described in the foregoing and if they are not equal a - * failure is logged. + * ensures that {@code v} is just under the B-Z threshold, that {@code z} is + * over the threshold and {@code w} is much larger than {@code z}. This + * implies that {@code u/v} uses the standard division algorithm and + * {@code w/z} uses the B-Z algorithm. The results of the two algorithms + * are then compared using the observation described in the foregoing and + * if they are not equal a failure is logged. */ public static void divideLarge() { int failCount = 0; - BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33); + BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33); for (int i=0; i<SIZE; i++) { - BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd); + BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd); BigInteger v = base.add(addend); BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1))); @@ -312,14 +313,14 @@ v = v.negate(); } - int a = 17 + rnd.nextInt(16); + int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16); int b = 1 + rnd.nextInt(16); - BigInteger w = u.multiply(BigInteger.valueOf(1L << a)); - BigInteger z = v.multiply(BigInteger.valueOf(1L << b)); + BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a)); + BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] divideResult = u.divideAndRemainder(v); - divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b))); - divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b)); + divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b)); + divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b)); BigInteger[] bzResult = w.divideAndRemainder(z); if (divideResult[0].compareTo(bzResult[0]) != 0 ||
Hi Robert, On Sep 15, 2014, at 2:09 AM, Robert Gibson <robbiexgibson@yahoo.com> wrote:
How are the performance characteristics after the patch?
I have not tested that aspect as yet but clearly it should be evaluated. Given that JDK-8057793 causes a violation of the specification of BigDecimal I thought it was important to check in the fix as-is without further delay.
I see that a lot of effort went in to tuning last December under 8029501.
Yes, that was a fair bit of work.
By the way, as part of my investigations into this bug I noticed that BigIntegerTest::divideLarge no longer tests the Burnikel-Ziegler part of the division code, since the heuristic to decide Knuth or BZ diverged from the algorithm to generate the test cases (as part of 8029501).
I created https://bugs.openjdk.java.net/browse/JDK-8058505 for this problem. Thanks, Brian
That was my screw-up. Thanks for fixing it. Tim On 09.09.2014 10:30, Robert Gibson wrote:
Hi there,
I came across a case in BigDecimal division where the dividend ends up getting mutated, which is rather strange for a seemingly immutable class! (It's a subset of the cases where the Burnikel-Ziegler algorithm is used, I haven't done the analysis to find out under which exact conditions it's triggered.)
The attached patch - against the JDK8 version - should fix the problem, at the cost of an extra array copy. Could somebody review and/or comment please?
Thanks, Robert
--- MutableBigInteger.java 2014-09-04 09:42:23.426815000 +0200 +++ MutableBigInteger.java.patched 2014-09-04 09:46:21.344132000 +0200 @@ -1261,19 +1261,20 @@ int sigma = (int) Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n} MutableBigInteger bShifted = new MutableBigInteger(b); bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n - safeLeftShift(sigma); // step 4b: shift this by the same amount + MutableBigInteger aShifted = new MutableBigInteger (this); + aShifted.safeLeftShift(sigma); // step 4b: shift a by the same amount - // step 5: t is the number of blocks needed to accommodate this plus one additional bit - int t = (int) ((bitLength()+n32) / n32); + // step 5: t is the number of blocks needed to accommodate a plus one additional bit + int t = (int) ((aShifted.bitLength()+n32) / n32); if (t < 2) { t = 2; } - // step 6: conceptually split this into blocks a[t-1], ..., a[0] - MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this + // step 6: conceptually split a into blocks a[t-1], ..., a[0] + MutableBigInteger a1 = aShifted.getBlock(t-1, t, n); // the most significant block of a // step 7: z[t-2] = [a[t-1], a[t-2]] - MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block + MutableBigInteger z = aShifted.getBlock(t-2, t, n); // the second to most significant block z.addDisjoint(a1, n); // z[t-2] // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers @@ -1284,7 +1285,7 @@ ri = z.divide2n1n(bShifted, qi); // step 8b: z = [ri, a[i-1]] - z = getBlock(i-1, t, n); // a[i-1] + z = aShifted.getBlock(i-1, t, n); // a[i-1] z.addDisjoint(ri, n); quotient.addShifted(qi, i*n); // update q (part of step 9) } @@ -1292,7 +1293,7 @@ ri = z.divide2n1n(bShifted, qi); quotient.add(qi); - ri.rightShift(sigma); // step 9: this and b were shifted, so shift back + ri.rightShift(sigma); // step 9: a and b were shifted, so shift back return ri; } }
And none of us who reviewed it nor any of the tests caught it either. Thanks to both (Tim & Robert) for the original and current patches. Brian On Sep 15, 2014, at 11:53 AM, Tim Buktu <tbuktu@hotmail.com> wrote:
That was my screw-up. Thanks for fixing it.
participants (5)
-
Brian Burkhalter
-
Joe Darcy
-
Robbie Gibson
-
Robert Gibson
-
Tim Buktu