I propose the patch below to fix a theoretical bug in
divideAndRemainderBurnikelZiegler(). That method assumes the quotient
parameter to be zero which is the case in all places it is called from.
But there is no guarantee this won't change in the future and besides,
the assumption is not documented. The right way to do it, in my opinion,
is to set quotient to zero when needed instead of relying on a zero
being passed in.
--- a/MutableBigInteger.java
+++ b/MutableBigInteger.java
@@ -1243,6 +1243,7 @@ class MutableBigInteger {
int s = b.intLen;
if (r < s) {
+ quotient.intLen = quotient.offset = 0;
return this;
} else {
// Unlike Knuth division, we don't check for common powers
of two here because
The second patch I'd like to submit changes the ORDER_TOOM_COOK value in
BigIntegerTest.java which is currently set to 3000. This is too low for
BZ division to be triggered in arithmetic() (although it does get
triggered in several other tests). The number used to be higher but it
must have changed along the way.
--- a/BigIntegerTest.java
+++ b/BigIntegerTest.java
@@ -74,10 +74,10 @@ public class BigIntegerTest {
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 @@ public class BigIntegerTest {
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 @@ public class BigIntegerTest {
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);
The patched files are at
https://gist.github.com/tbuktu/1576025/raw/7eb495658353779fe579e89fc4d82ae787402a9e/MutableBigInteger.java.phase3
and
https://gist.github.com/tbuktu/1576025/raw/279f5546b58523254c6a4d3c393058c6a12c5a71/BigIntegerTest.java.phase3
Tim
