RFR 8057793 BigDecimal is no longer effectively immutable
Robert Gibson
robbiexgibson at yahoo.com
Mon Sep 15 14:17:39 UTC 2014
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 at 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 at 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 at 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;
>> }
>> }
>
More information about the core-libs-dev
mailing list