Mercurial Mercurial > jdk-sandbox / changeset
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8022180: BigInteger Burnikel-Ziegler quotient and remainder calculation assumes quotient parameter is zero
authorbpb
Mon, 12 Aug 2013 16:21:10 -0700
changeset 19393 d99a9ebf9c10
parent 19392 c08a64a9a5f1
child 19394 6975323f4243
8022180: BigInteger Burnikel-Ziegler quotient and remainder calculation assumes quotient parameter is zero Summary: Clear the quotient in divideAndRemainderBurnikelZiegler() if the divisor is larger than the dividend. Reviewed-by: alanb, bpb Contributed-by: Timothy Buktu <tbuktu@hotmail.com>
jdk/src/share/classes/java/math/MutableBigInteger.java file | annotate | diff | comparison | revisions
jdk/test/java/math/BigInteger/BigIntegerTest.java file | annotate | diff | comparison | revisions 
--- a/jdk/src/share/classes/java/math/MutableBigInteger.java	Tue Aug 13 14:18:57 2013 +0100
+++ b/jdk/src/share/classes/java/math/MutableBigInteger.java	Mon Aug 12 16:21:10 2013 -0700
@@ -1242,6 +1242,9 @@
         int r = intLen;
         int s = b.intLen;
 
+        // Clear the quotient
+        quotient.offset = quotient.intLen = 0;
+
         if (r < s) {
             return this;
         } else {
@@ -1276,7 +1279,6 @@
             // do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers
             MutableBigInteger qi = new MutableBigInteger();
             MutableBigInteger ri;
-            quotient.offset = quotient.intLen = 0;
             for (int i=t-2; i > 0; i--) {
                 // step 8a: compute (qi,ri) such that z=b*qi+ri
                 ri = z.divide2n1n(bShifted, qi);
--- a/jdk/test/java/math/BigInteger/BigIntegerTest.java	Tue Aug 13 14:18:57 2013 +0100
+++ b/jdk/test/java/math/BigInteger/BigIntegerTest.java	Mon Aug 12 16:21:10 2013 -0700
@@ -74,10 +74,10 @@
 
     static final int ORDER_SMALL = 60;
     static final int ORDER_MEDIUM = 100;
-    // #bits for testing Karatsuba and Burnikel-Ziegler
+    // #bits for testing Karatsuba
     static final int ORDER_KARATSUBA = 1800;
-    // #bits for testing Toom-Cook
-    static final int ORDER_TOOM_COOK = 3000;
+    // #bits for testing Toom-Cook and Burnikel-Ziegler
+    static final int ORDER_TOOM_COOK = 4000;
     // #bits for testing Karatsuba squaring
     static final int ORDER_KARATSUBA_SQUARE = 3200;
     // #bits for testing Toom-Cook squaring
@@ -964,12 +964,12 @@
         nextProbablePrime();
 
         arithmetic(order1);   // small numbers
-        arithmetic(order3);   // Karatsuba / Burnikel-Ziegler range
-        arithmetic(order4);   // Toom-Cook range
+        arithmetic(order3);   // Karatsuba range
+        arithmetic(order4);   // Toom-Cook / Burnikel-Ziegler range
 
         divideAndRemainder(order1);   // small numbers
-        divideAndRemainder(order3);   // Karatsuba / Burnikel-Ziegler range
-        divideAndRemainder(order4);   // Toom-Cook range
+        divideAndRemainder(order3);   // Karatsuba range
+        divideAndRemainder(order4);   // Toom-Cook / Burnikel-Ziegler range
 
         pow(order1);
         pow(order3);
@@ -989,8 +989,8 @@
         byteArrayConv(order1);
 
         modInv(order1);   // small numbers
-        modInv(order3);   // Karatsuba / Burnikel-Ziegler range
-        modInv(order4);   // Toom-Cook range
+        modInv(order3);   // Karatsuba range
+        modInv(order4);   // Toom-Cook / Burnikel-Ziegler range
 
         modExp(order1, order2);
         modExp2(order1);
jdk-sandbox