54 public class BigIntegerTest {
55 //
56 // Bit large number thresholds based on the int thresholds
57 // defined in BigInteger itself:
58 //
59 // KARATSUBA_THRESHOLD = 80 ints = 2560 bits
60 // TOOM_COOK_THRESHOLD = 240 ints = 7680 bits
61 // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits
62 // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits
63 //
64 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits
65 //
66 // BURNIKEL_ZIEGLER_THRESHOLD = 80 ints = 2560 bits
67 //
68 static final int BITS_KARATSUBA = 2560;
69 static final int BITS_TOOM_COOK = 7680;
70 static final int BITS_KARATSUBA_SQUARE = 4096;
71 static final int BITS_TOOM_COOK_SQUARE = 6912;
72 static final int BITS_SCHOENHAGE_BASE = 640;
73 static final int BITS_BURNIKEL_ZIEGLER = 2560;
74
75 static final int ORDER_SMALL = 60;
76 static final int ORDER_MEDIUM = 100;
77 // #bits for testing Karatsuba
78 static final int ORDER_KARATSUBA = 2760;
79 // #bits for testing Toom-Cook and Burnikel-Ziegler
80 static final int ORDER_TOOM_COOK = 8000;
81 // #bits for testing Karatsuba squaring
82 static final int ORDER_KARATSUBA_SQUARE = 4200;
83 // #bits for testing Toom-Cook squaring
84 static final int ORDER_TOOM_COOK_SQUARE = 7000;
85
86 static final int SIZE = 1000; // numbers per batch
87
88 static Random rnd = new Random();
89 static boolean failure = false;
90
91 public static void pow(int order) {
92 int failCount1 = 0;
93
271
272 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
273 BigInteger toomCookSquareResult = w.multiply(w);
274
275 if (!squareResult.equals(toomCookSquareResult)) {
276 failCount++;
277 }
278 }
279
280 report("squareLarge Toom-Cook", failCount);
281 }
282
283 /**
284 * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division
285 * algorithm is used when each of the dividend and the divisor has at least
286 * a specified number of ints in its representation. This test is based on
287 * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
288 * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
289 * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
290 * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test
291 * ensures that {@code v} is just under the B-Z threshold and that {@code w}
292 * and {@code z} are both over the threshold. This implies that {@code u/v}
293 * uses the standard division algorithm and {@code w/z} uses the B-Z
294 * algorithm. The results of the two algorithms are then compared using the
295 * observation described in the foregoing and if they are not equal a
296 * failure is logged.
297 */
298 public static void divideLarge() {
299 int failCount = 0;
300
301 BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33);
302 for (int i=0; i<SIZE; i++) {
303 BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd);
304 BigInteger v = base.add(addend);
305
306 BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));
307
308 if(rnd.nextBoolean()) {
309 u = u.negate();
310 }
311 if(rnd.nextBoolean()) {
312 v = v.negate();
313 }
314
315 int a = 17 + rnd.nextInt(16);
316 int b = 1 + rnd.nextInt(16);
317 BigInteger w = u.multiply(BigInteger.valueOf(1L << a));
318 BigInteger z = v.multiply(BigInteger.valueOf(1L << b));
319
320 BigInteger[] divideResult = u.divideAndRemainder(v);
321 divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b)));
322 divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b));
323 BigInteger[] bzResult = w.divideAndRemainder(z);
324
325 if (divideResult[0].compareTo(bzResult[0]) != 0 ||
326 divideResult[1].compareTo(bzResult[1]) != 0) {
327 failCount++;
328 }
329 }
330
331 report("divideLarge", failCount);
332 }
333
334 public static void bitCount() {
335 int failCount = 0;
336
337 for (int i=0; i<SIZE*10; i++) {
338 int x = rnd.nextInt();
339 BigInteger bigX = BigInteger.valueOf((long)x);
340 int bit = (x < 0 ? 0 : 1);
341 int tmp = x, bitCount = 0;
342 for (int j=0; j<32; j++) {
|
54 public class BigIntegerTest {
55 //
56 // Bit large number thresholds based on the int thresholds
57 // defined in BigInteger itself:
58 //
59 // KARATSUBA_THRESHOLD = 80 ints = 2560 bits
60 // TOOM_COOK_THRESHOLD = 240 ints = 7680 bits
61 // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits
62 // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits
63 //
64 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits
65 //
66 // BURNIKEL_ZIEGLER_THRESHOLD = 80 ints = 2560 bits
67 //
68 static final int BITS_KARATSUBA = 2560;
69 static final int BITS_TOOM_COOK = 7680;
70 static final int BITS_KARATSUBA_SQUARE = 4096;
71 static final int BITS_TOOM_COOK_SQUARE = 6912;
72 static final int BITS_SCHOENHAGE_BASE = 640;
73 static final int BITS_BURNIKEL_ZIEGLER = 2560;
74 static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280;
75
76 static final int ORDER_SMALL = 60;
77 static final int ORDER_MEDIUM = 100;
78 // #bits for testing Karatsuba
79 static final int ORDER_KARATSUBA = 2760;
80 // #bits for testing Toom-Cook and Burnikel-Ziegler
81 static final int ORDER_TOOM_COOK = 8000;
82 // #bits for testing Karatsuba squaring
83 static final int ORDER_KARATSUBA_SQUARE = 4200;
84 // #bits for testing Toom-Cook squaring
85 static final int ORDER_TOOM_COOK_SQUARE = 7000;
86
87 static final int SIZE = 1000; // numbers per batch
88
89 static Random rnd = new Random();
90 static boolean failure = false;
91
92 public static void pow(int order) {
93 int failCount1 = 0;
94
272
273 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
274 BigInteger toomCookSquareResult = w.multiply(w);
275
276 if (!squareResult.equals(toomCookSquareResult)) {
277 failCount++;
278 }
279 }
280
281 report("squareLarge Toom-Cook", failCount);
282 }
283
284 /**
285 * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division
286 * algorithm is used when each of the dividend and the divisor has at least
287 * a specified number of ints in its representation. This test is based on
288 * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
289 * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
290 * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
291 * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test
292 * ensures that {@code v} is just under the B-Z threshold, that {@code z} is
293 * over the threshold and {@code w} is much larger than {@code z}. This
294 * implies that {@code u/v} uses the standard division algorithm and
295 * {@code w/z} uses the B-Z algorithm. The results of the two algorithms
296 * are then compared using the observation described in the foregoing and
297 * if they are not equal a failure is logged.
298 */
299 public static void divideLarge() {
300 int failCount = 0;
301
302 BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33);
303 for (int i=0; i<SIZE; i++) {
304 BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd);
305 BigInteger v = base.add(addend);
306
307 BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));
308
309 if(rnd.nextBoolean()) {
310 u = u.negate();
311 }
312 if(rnd.nextBoolean()) {
313 v = v.negate();
314 }
315
316 int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16);
317 int b = 1 + rnd.nextInt(16);
318 BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a));
319 BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b));
320
321 BigInteger[] divideResult = u.divideAndRemainder(v);
322 divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b));
323 divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b));
324 BigInteger[] bzResult = w.divideAndRemainder(z);
325
326 if (divideResult[0].compareTo(bzResult[0]) != 0 ||
327 divideResult[1].compareTo(bzResult[1]) != 0) {
328 failCount++;
329 }
330 }
331
332 report("divideLarge", failCount);
333 }
334
335 public static void bitCount() {
336 int failCount = 0;
337
338 for (int i=0; i<SIZE*10; i++) {
339 int x = rnd.nextInt();
340 BigInteger bigX = BigInteger.valueOf((long)x);
341 int bit = (x < 0 ? 0 : 1);
342 int tmp = x, bitCount = 0;
343 for (int j=0; j<32; j++) {
|