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 <[email protected]>
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
<[email protected]> 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 <[email protected]> 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;
>> }
>> }
>
