test/java/math/BigInteger/BigIntegerTest.java
Print this page
rev 7721 : 8014319: Faster division of large integers
Summary: Implement Burnickel-Ziegler division algorithm in BigInteger
Reviewed-by: bpb, martin
Contributed-by: Tim Buktu <tbuktu@hotmail.com>
*** 41,56 ****
* This is a simple test class created to ensure that the results
* generated by BigInteger adhere to certain identities. Passing
* this test is a strong assurance that the BigInteger operations
* are working correctly.
*
! * Three arguments may be specified which give the number of
! * decimal digits you desire in the three batches of test numbers.
*
* The tests are performed on arrays of random numbers which are
* generated by a Random class as well as special cases which
! * throw in boundary numbers such as 0, 1, maximum sized, etc.
*
*/
public class BigIntegerTest {
//
// Bit large number thresholds based on the int thresholds
--- 41,56 ----
* This is a simple test class created to ensure that the results
* generated by BigInteger adhere to certain identities. Passing
* this test is a strong assurance that the BigInteger operations
* are working correctly.
*
! * Four arguments may be specified which give the number of
! * decimal digits you desire in the four batches of test numbers.
*
* The tests are performed on arrays of random numbers which are
* generated by a Random class as well as special cases which
! * throw in boundary numbers such as 0, 1, maximum SIZEd, etc.
*
*/
public class BigIntegerTest {
//
// Bit large number thresholds based on the int thresholds
*** 61,75 ****
--- 61,78 ----
// KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits
// TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
//
// SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
//
+ // BURNIKEL_ZIEGLER_THRESHOLD = 50 ints = 1600 bits
+ //
static final int BITS_KARATSUBA = 1600;
static final int BITS_TOOM_COOK = 2400;
static final int BITS_KARATSUBA_SQUARE = 2880;
static final int BITS_TOOM_COOK_SQUARE = 4480;
static final int BITS_SCHOENHAGE_BASE = 256;
+ static final int BITS_BURNIKEL_ZIEGLER = 1600;
static final int ORDER_SMALL = 60;
static final int ORDER_MEDIUM = 100;
// #bits for testing Karatsuba and Burnikel-Ziegler
static final int ORDER_KARATSUBA = 1800;
*** 78,95 ****
// #bits for testing Karatsuba squaring
static final int ORDER_KARATSUBA_SQUARE = 3200;
// #bits for testing Toom-Cook squaring
static final int ORDER_TOOM_COOK_SQUARE = 4600;
static Random rnd = new Random();
- static int size = 1000; // numbers per batch
static boolean failure = false;
public static void pow(int order) {
int failCount1 = 0;
! for (int i=0; i<size; i++) {
// Test identity x^power == x*x*x ... *x
int power = rnd.nextInt(6) + 2;
BigInteger x = fetchNumber(order);
BigInteger y = x.pow(power);
BigInteger z = x;
--- 81,99 ----
// #bits for testing Karatsuba squaring
static final int ORDER_KARATSUBA_SQUARE = 3200;
// #bits for testing Toom-Cook squaring
static final int ORDER_TOOM_COOK_SQUARE = 4600;
+ static final int SIZE = 1000; // numbers per batch
+
static Random rnd = new Random();
static boolean failure = false;
public static void pow(int order) {
int failCount1 = 0;
! for (int i=0; i<SIZE; i++) {
// Test identity x^power == x*x*x ... *x
int power = rnd.nextInt(6) + 2;
BigInteger x = fetchNumber(order);
BigInteger y = x.pow(power);
BigInteger z = x;
*** 104,114 ****
}
public static void square(int order) {
int failCount1 = 0;
! for (int i=0; i<size; i++) {
// Test identity x^2 == x*x
BigInteger x = fetchNumber(order);
BigInteger xx = x.multiply(x);
BigInteger x2 = x.pow(2);
--- 108,118 ----
}
public static void square(int order) {
int failCount1 = 0;
! for (int i=0; i<SIZE; i++) {
// Test identity x^2 == x*x
BigInteger x = fetchNumber(order);
BigInteger xx = x.multiply(x);
BigInteger x2 = x.pow(2);
*** 119,129 ****
}
public static void arithmetic(int order) {
int failCount = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order);
while(x.compareTo(BigInteger.ZERO) != 1)
x = fetchNumber(order);
BigInteger y = fetchNumber(order/2);
while(x.compareTo(y) == -1)
--- 123,133 ----
}
public static void arithmetic(int order) {
int failCount = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
while(x.compareTo(BigInteger.ZERO) != 1)
x = fetchNumber(order);
BigInteger y = fetchNumber(order/2);
while(x.compareTo(y) == -1)
*** 185,195 ****
*/
public static void multiplyLarge() {
int failCount = 0;
BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
--- 189,199 ----
*/
public static void multiplyLarge() {
int failCount = 0;
BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
*** 208,218 ****
report("multiplyLarge Karatsuba", failCount);
failCount = 0;
base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
BigInteger u = base.add(x);
BigInteger u2 = u.shiftLeft(1);
BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
BigInteger v = base.add(y);
--- 212,222 ----
report("multiplyLarge Karatsuba", failCount);
failCount = 0;
base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
BigInteger u = base.add(x);
BigInteger u2 = u.shiftLeft(1);
BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
BigInteger v = base.add(y);
*** 239,249 ****
*/
public static void squareLarge() {
int failCount = 0;
BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
--- 243,253 ----
*/
public static void squareLarge() {
int failCount = 0;
BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
*** 257,267 ****
report("squareLarge Karatsuba", failCount);
failCount = 0;
base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
--- 261,271 ----
report("squareLarge Karatsuba", failCount);
failCount = 0;
base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
BigInteger u = base.add(x);
int a = 1 + rnd.nextInt(31);
BigInteger w = u.shiftLeft(a);
*** 274,287 ****
}
report("squareLarge Toom-Cook", failCount);
}
public static void bitCount() {
int failCount = 0;
! for (int i=0; i<size*10; i++) {
int x = rnd.nextInt();
BigInteger bigX = BigInteger.valueOf((long)x);
int bit = (x < 0 ? 0 : 1);
int tmp = x, bitCount = 0;
for (int j=0; j<32; j++) {
--- 278,342 ----
}
report("squareLarge Toom-Cook", failCount);
}
+ /**
+ * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division
+ * algorithm is used when each of the dividend and the divisor has at least
+ * a specified number of ints in its representation. This test is based on
+ * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
+ * 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.
+ */
+ public static void divideLarge() {
+ int failCount = 0;
+
+ BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33);
+ for (int i=0; i<SIZE; i++) {
+ BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd);
+ BigInteger v = base.add(addend);
+
+ BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));
+
+ if(rnd.nextBoolean()) {
+ u = u.negate();
+ }
+ if(rnd.nextBoolean()) {
+ v = v.negate();
+ }
+
+ int a = 17 + 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[] divideResult = u.divideAndRemainder(v);
+ divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b)));
+ divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b));
+ BigInteger[] bzResult = w.divideAndRemainder(z);
+
+ if (divideResult[0].compareTo(bzResult[0]) != 0 ||
+ divideResult[1].compareTo(bzResult[1]) != 0) {
+ failCount++;
+ }
+ }
+
+ report("divideLarge", failCount);
+ }
+
public static void bitCount() {
int failCount = 0;
! for (int i=0; i<SIZE*10; i++) {
int x = rnd.nextInt();
BigInteger bigX = BigInteger.valueOf((long)x);
int bit = (x < 0 ? 0 : 1);
int tmp = x, bitCount = 0;
for (int j=0; j<32; j++) {
*** 298,308 ****
}
public static void bitLength() {
int failCount = 0;
! for (int i=0; i<size*10; i++) {
int x = rnd.nextInt();
BigInteger bigX = BigInteger.valueOf((long)x);
int signBit = (x < 0 ? 0x80000000 : 0);
int tmp = x, bitLength, j;
for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
--- 353,363 ----
}
public static void bitLength() {
int failCount = 0;
! for (int i=0; i<SIZE*10; i++) {
int x = rnd.nextInt();
BigInteger bigX = BigInteger.valueOf((long)x);
int signBit = (x < 0 ? 0x80000000 : 0);
int tmp = x, bitLength, j;
for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
*** 319,329 ****
}
public static void bitOps(int order) {
int failCount1 = 0, failCount2 = 0, failCount3 = 0;
! for (int i=0; i<size*5; i++) {
BigInteger x = fetchNumber(order);
BigInteger y;
// Test setBit and clearBit (and testBit)
if (x.signum() < 0) {
--- 374,384 ----
}
public static void bitOps(int order) {
int failCount1 = 0, failCount2 = 0, failCount3 = 0;
! for (int i=0; i<SIZE*5; i++) {
BigInteger x = fetchNumber(order);
BigInteger y;
// Test setBit and clearBit (and testBit)
if (x.signum() < 0) {
*** 349,359 ****
failCount2++;
}
report("clearBit/testBit for " + order + " bits", failCount1);
report("flipBit/testBit for " + order + " bits", failCount2);
! for (int i=0; i<size*5; i++) {
BigInteger x = fetchNumber(order);
// Test getLowestSetBit()
int k = x.getLowestSetBit();
if (x.signum() == 0) {
--- 404,414 ----
failCount2++;
}
report("clearBit/testBit for " + order + " bits", failCount1);
report("flipBit/testBit for " + order + " bits", failCount2);
! for (int i=0; i<SIZE*5; i++) {
BigInteger x = fetchNumber(order);
// Test getLowestSetBit()
int k = x.getLowestSetBit();
if (x.signum() == 0) {
*** 373,383 ****
public static void bitwise(int order) {
// Test identity x^y == x|y &~ x&y
int failCount = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order);
BigInteger y = fetchNumber(order);
BigInteger z = x.xor(y);
BigInteger w = x.or(y).andNot(x.and(y));
if (!z.equals(w))
--- 428,438 ----
public static void bitwise(int order) {
// Test identity x^y == x|y &~ x&y
int failCount = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
BigInteger y = fetchNumber(order);
BigInteger z = x.xor(y);
BigInteger w = x.or(y).andNot(x.and(y));
if (!z.equals(w))
*** 385,395 ****
}
report("Logic (^ | & ~) for " + order + " bits", failCount);
// Test identity x &~ y == ~(~x | y)
failCount = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order);
BigInteger y = fetchNumber(order);
BigInteger z = x.andNot(y);
BigInteger w = x.not().or(y).not();
if (!z.equals(w))
--- 440,450 ----
}
report("Logic (^ | & ~) for " + order + " bits", failCount);
// Test identity x &~ y == ~(~x | y)
failCount = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
BigInteger y = fetchNumber(order);
BigInteger z = x.andNot(y);
BigInteger w = x.not().or(y).not();
if (!z.equals(w))
*** 438,448 ****
}
public static void divideAndRemainder(int order) {
int failCount1 = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order).abs();
while(x.compareTo(BigInteger.valueOf(3L)) != 1)
x = fetchNumber(order).abs();
BigInteger z = x.divide(BigInteger.valueOf(2L));
BigInteger y[] = x.divideAndRemainder(x);
--- 493,503 ----
}
public static void divideAndRemainder(int order) {
int failCount1 = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order).abs();
while(x.compareTo(BigInteger.valueOf(3L)) != 1)
x = fetchNumber(order).abs();
BigInteger z = x.divide(BigInteger.valueOf(2L));
BigInteger y[] = x.divideAndRemainder(x);
*** 517,527 ****
}
public static void byteArrayConv(int order) {
int failCount = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order);
while (x.equals(BigInteger.ZERO))
x = fetchNumber(order);
BigInteger y = new BigInteger(x.toByteArray());
if (!x.equals(y)) {
--- 572,582 ----
}
public static void byteArrayConv(int order) {
int failCount = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
while (x.equals(BigInteger.ZERO))
x = fetchNumber(order);
BigInteger y = new BigInteger(x.toByteArray());
if (!x.equals(y)) {
*** 534,544 ****
}
public static void modInv(int order) {
int failCount = 0, successCount = 0, nonInvCount = 0;
! for (int i=0; i<size; i++) {
BigInteger x = fetchNumber(order);
while(x.equals(BigInteger.ZERO))
x = fetchNumber(order);
BigInteger m = fetchNumber(order).abs();
while(m.compareTo(BigInteger.ONE) != 1)
--- 589,599 ----
}
public static void modInv(int order) {
int failCount = 0, successCount = 0, nonInvCount = 0;
! for (int i=0; i<SIZE; i++) {
BigInteger x = fetchNumber(order);
while(x.equals(BigInteger.ZERO))
x = fetchNumber(order);
BigInteger m = fetchNumber(order).abs();
while(m.compareTo(BigInteger.ONE) != 1)
*** 563,573 ****
}
public static void modExp(int order1, int order2) {
int failCount = 0;
! for (int i=0; i<size/10; i++) {
BigInteger m = fetchNumber(order1).abs();
while(m.compareTo(BigInteger.ONE) != 1)
m = fetchNumber(order1).abs();
BigInteger base = fetchNumber(order2);
BigInteger exp = fetchNumber(8).abs();
--- 618,628 ----
}
public static void modExp(int order1, int order2) {
int failCount = 0;
! for (int i=0; i<SIZE/10; i++) {
BigInteger m = fetchNumber(order1).abs();
while(m.compareTo(BigInteger.ONE) != 1)
m = fetchNumber(order1).abs();
BigInteger base = fetchNumber(order2);
BigInteger exp = fetchNumber(8).abs();
*** 881,892 ****
}
/**
* Main to interpret arguments and run several tests.
*
! * Up to three arguments may be given to specify the size of BigIntegers
! * used for call parameters 1, 2, and 3. The size is interpreted as
* the maximum number of decimal digits that the parameters will have.
*
*/
public static void main(String[] args) throws Exception {
--- 936,947 ----
}
/**
* Main to interpret arguments and run several tests.
*
! * Up to three arguments may be given to specify the SIZE of BigIntegers
! * used for call parameters 1, 2, and 3. The SIZE is interpreted as
* the maximum number of decimal digits that the parameters will have.
*
*/
public static void main(String[] args) throws Exception {
*** 943,960 ****
stringConv();
serialize();
multiplyLarge();
squareLarge();
if (failure)
throw new RuntimeException("Failure in BigIntegerTest.");
}
/*
* Get a random or boundary-case number. This is designed to provide
! * a lot of numbers that will find failure points, such as max sized
* numbers, empty BigIntegers, etc.
*
* If order is less than 2, order is changed to 2.
*/
private static BigInteger fetchNumber(int order) {
--- 998,1016 ----
stringConv();
serialize();
multiplyLarge();
squareLarge();
+ divideLarge();
if (failure)
throw new RuntimeException("Failure in BigIntegerTest.");
}
/*
* Get a random or boundary-case number. This is designed to provide
! * a lot of numbers that will find failure points, such as max SIZEd
* numbers, empty BigIntegers, etc.
*
* If order is less than 2, order is changed to 2.
*/
private static BigInteger fetchNumber(int order) {
*** 985,1001 ****
case 3: // One bit in number
result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
break;
case 4: // Random bit density
! int iterations = rnd.nextInt(order-1);
! result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
! for(int i=0; i<iterations; i++) {
! BigInteger temp = BigInteger.ONE.shiftLeft(
! rnd.nextInt(order));
! result = result.or(temp);
}
break;
case 5: // Runs of consecutive ones and zeros
result = ZERO;
int remaining = order;
int bit = rnd.nextInt(2);
--- 1041,1057 ----
case 3: // One bit in number
result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
break;
case 4: // Random bit density
! byte[] val = new byte[(order+7)/8];
! int iterations = rnd.nextInt(order);
! for (int i=0; i<iterations; i++) {
! int bitIdx = rnd.nextInt(order);
! val[bitIdx/8] |= 1 << (bitIdx%8);
}
+ result = new BigInteger(1, val);
break;
case 5: // Runs of consecutive ones and zeros
result = ZERO;
int remaining = order;
int bit = rnd.nextInt(2);