26 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946
27 * @summary tests methods in BigInteger
28 * @run main/timeout=400 BigIntegerTest
29 * @author madbot
30 */
31
32 import java.io.File;
33 import java.io.FileInputStream;
34 import java.io.FileOutputStream;
35 import java.io.ObjectInputStream;
36 import java.io.ObjectOutputStream;
37 import java.math.BigInteger;
38 import java.util.Random;
39
40 /**
41 * This is a simple test class created to ensure that the results
42 * generated by BigInteger adhere to certain identities. Passing
43 * this test is a strong assurance that the BigInteger operations
44 * are working correctly.
45 *
46 * Three arguments may be specified which give the number of
47 * decimal digits you desire in the three batches of test numbers.
48 *
49 * The tests are performed on arrays of random numbers which are
50 * generated by a Random class as well as special cases which
51 * throw in boundary numbers such as 0, 1, maximum sized, etc.
52 *
53 */
54 public class BigIntegerTest {
55 //
56 // Bit large number thresholds based on the int thresholds
57 // defined in BigInteger itself:
58 //
59 // KARATSUBA_THRESHOLD = 50 ints = 1600 bits
60 // TOOM_COOK_THRESHOLD = 75 ints = 2400 bits
61 // KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits
62 // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
63 //
64 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
65 //
66 static final int BITS_KARATSUBA = 1600;
67 static final int BITS_TOOM_COOK = 2400;
68 static final int BITS_KARATSUBA_SQUARE = 2880;
69 static final int BITS_TOOM_COOK_SQUARE = 4480;
70 static final int BITS_SCHOENHAGE_BASE = 256;
71
72 static final int ORDER_SMALL = 60;
73 static final int ORDER_MEDIUM = 100;
74 // #bits for testing Karatsuba and Burnikel-Ziegler
75 static final int ORDER_KARATSUBA = 1800;
76 // #bits for testing Toom-Cook
77 static final int ORDER_TOOM_COOK = 3000;
78 // #bits for testing Karatsuba squaring
79 static final int ORDER_KARATSUBA_SQUARE = 3200;
80 // #bits for testing Toom-Cook squaring
81 static final int ORDER_TOOM_COOK_SQUARE = 4600;
82
83 static Random rnd = new Random();
84 static int size = 1000; // numbers per batch
85 static boolean failure = false;
86
87 public static void pow(int order) {
88 int failCount1 = 0;
89
90 for (int i=0; i<size; i++) {
91 // Test identity x^power == x*x*x ... *x
92 int power = rnd.nextInt(6) + 2;
93 BigInteger x = fetchNumber(order);
94 BigInteger y = x.pow(power);
95 BigInteger z = x;
96
97 for (int j=1; j<power; j++)
98 z = z.multiply(x);
99
100 if (!y.equals(z))
101 failCount1++;
102 }
103 report("pow for " + order + " bits", failCount1);
104 }
105
106 public static void square(int order) {
107 int failCount1 = 0;
108
109 for (int i=0; i<size; i++) {
110 // Test identity x^2 == x*x
111 BigInteger x = fetchNumber(order);
112 BigInteger xx = x.multiply(x);
113 BigInteger x2 = x.pow(2);
114
115 if (!x2.equals(xx))
116 failCount1++;
117 }
118 report("square for " + order + " bits", failCount1);
119 }
120
121 public static void arithmetic(int order) {
122 int failCount = 0;
123
124 for (int i=0; i<size; i++) {
125 BigInteger x = fetchNumber(order);
126 while(x.compareTo(BigInteger.ZERO) != 1)
127 x = fetchNumber(order);
128 BigInteger y = fetchNumber(order/2);
129 while(x.compareTo(y) == -1)
130 y = fetchNumber(order/2);
131 if (y.equals(BigInteger.ZERO))
132 y = y.add(BigInteger.ONE);
133
134 // Test identity ((x/y))*y + x%y - x == 0
135 // using separate divide() and remainder()
136 BigInteger baz = x.divide(y);
137 baz = baz.multiply(y);
138 baz = baz.add(x.remainder(y));
139 baz = baz.subtract(x);
140 if (!baz.equals(BigInteger.ZERO))
141 failCount++;
142 }
143 report("Arithmetic I for " + order + " bits", failCount);
144
170 * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
171 * construct two factors each with a mag array one element shorter than the
172 * threshold, and with the most significant bit set and the rest of the bits
173 * random. Each of these numbers will therefore be below the threshold but
174 * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
175 * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
176 * identity
177 * <pre>
178 * (u << a)*(v << b) = (u*v) << (a + b)
179 * </pre>
180 * For Karatsuba multiplication, the right hand expression will be evaluated
181 * using the standard naive algorithm, and the left hand expression using
182 * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
183 * hand expression will be evaluated using Karatsuba multiplication, and the
184 * left hand expression using 3-way Toom-Cook multiplication.
185 */
186 public static void multiplyLarge() {
187 int failCount = 0;
188
189 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
190 for (int i=0; i<size; i++) {
191 BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
192 BigInteger u = base.add(x);
193 int a = 1 + rnd.nextInt(31);
194 BigInteger w = u.shiftLeft(a);
195
196 BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
197 BigInteger v = base.add(y);
198 int b = 1 + rnd.nextInt(32);
199 BigInteger z = v.shiftLeft(b);
200
201 BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
202 BigInteger karatsubaMultiplyResult = w.multiply(z);
203
204 if (!multiplyResult.equals(karatsubaMultiplyResult)) {
205 failCount++;
206 }
207 }
208
209 report("multiplyLarge Karatsuba", failCount);
210
211 failCount = 0;
212 base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
213 for (int i=0; i<size; i++) {
214 BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
215 BigInteger u = base.add(x);
216 BigInteger u2 = u.shiftLeft(1);
217 BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
218 BigInteger v = base.add(y);
219 BigInteger v2 = v.shiftLeft(1);
220
221 BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
222 BigInteger toomCookMultiplyResult = u2.multiply(v2);
223
224 if (!multiplyResult.equals(toomCookMultiplyResult)) {
225 failCount++;
226 }
227 }
228
229 report("multiplyLarge Toom-Cook", failCount);
230 }
231
232 /**
233 * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
234 * This test is analogous to {@link AbstractMethodError#multiplyLarge}
235 * with both factors being equal. The squaring methods will not be tested
236 * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
237 * the parameter is the same instance on which the method is being invoked
238 * and calls <code>square()</code> accordingly.
239 */
240 public static void squareLarge() {
241 int failCount = 0;
242
243 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
244 for (int i=0; i<size; i++) {
245 BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
246 BigInteger u = base.add(x);
247 int a = 1 + rnd.nextInt(31);
248 BigInteger w = u.shiftLeft(a);
249
250 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
251 BigInteger karatsubaSquareResult = w.multiply(w);
252
253 if (!squareResult.equals(karatsubaSquareResult)) {
254 failCount++;
255 }
256 }
257
258 report("squareLarge Karatsuba", failCount);
259
260 failCount = 0;
261 base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
262 for (int i=0; i<size; i++) {
263 BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
264 BigInteger u = base.add(x);
265 int a = 1 + rnd.nextInt(31);
266 BigInteger w = u.shiftLeft(a);
267
268 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
269 BigInteger toomCookSquareResult = w.multiply(w);
270
271 if (!squareResult.equals(toomCookSquareResult)) {
272 failCount++;
273 }
274 }
275
276 report("squareLarge Toom-Cook", failCount);
277 }
278
279 public static void bitCount() {
280 int failCount = 0;
281
282 for (int i=0; i<size*10; i++) {
283 int x = rnd.nextInt();
284 BigInteger bigX = BigInteger.valueOf((long)x);
285 int bit = (x < 0 ? 0 : 1);
286 int tmp = x, bitCount = 0;
287 for (int j=0; j<32; j++) {
288 bitCount += ((tmp & 1) == bit ? 1 : 0);
289 tmp >>= 1;
290 }
291
292 if (bigX.bitCount() != bitCount) {
293 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
294 failCount++;
295 }
296 }
297 report("Bit Count", failCount);
298 }
299
300 public static void bitLength() {
301 int failCount = 0;
302
303 for (int i=0; i<size*10; i++) {
304 int x = rnd.nextInt();
305 BigInteger bigX = BigInteger.valueOf((long)x);
306 int signBit = (x < 0 ? 0x80000000 : 0);
307 int tmp = x, bitLength, j;
308 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
309 tmp <<= 1;
310 bitLength = 32 - j;
311
312 if (bigX.bitLength() != bitLength) {
313 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
314 failCount++;
315 }
316 }
317
318 report("BitLength", failCount);
319 }
320
321 public static void bitOps(int order) {
322 int failCount1 = 0, failCount2 = 0, failCount3 = 0;
323
324 for (int i=0; i<size*5; i++) {
325 BigInteger x = fetchNumber(order);
326 BigInteger y;
327
328 // Test setBit and clearBit (and testBit)
329 if (x.signum() < 0) {
330 y = BigInteger.valueOf(-1);
331 for (int j=0; j<x.bitLength(); j++)
332 if (!x.testBit(j))
333 y = y.clearBit(j);
334 } else {
335 y = BigInteger.ZERO;
336 for (int j=0; j<x.bitLength(); j++)
337 if (x.testBit(j))
338 y = y.setBit(j);
339 }
340 if (!x.equals(y))
341 failCount1++;
342
343 // Test flipBit (and testBit)
344 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
345 for (int j=0; j<x.bitLength(); j++)
346 if (x.signum()<0 ^ x.testBit(j))
347 y = y.flipBit(j);
348 if (!x.equals(y))
349 failCount2++;
350 }
351 report("clearBit/testBit for " + order + " bits", failCount1);
352 report("flipBit/testBit for " + order + " bits", failCount2);
353
354 for (int i=0; i<size*5; i++) {
355 BigInteger x = fetchNumber(order);
356
357 // Test getLowestSetBit()
358 int k = x.getLowestSetBit();
359 if (x.signum() == 0) {
360 if (k != -1)
361 failCount3++;
362 } else {
363 BigInteger z = x.and(x.negate());
364 int j;
365 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
366 ;
367 if (k != j)
368 failCount3++;
369 }
370 }
371 report("getLowestSetBit for " + order + " bits", failCount3);
372 }
373
374 public static void bitwise(int order) {
375
376 // Test identity x^y == x|y &~ x&y
377 int failCount = 0;
378 for (int i=0; i<size; i++) {
379 BigInteger x = fetchNumber(order);
380 BigInteger y = fetchNumber(order);
381 BigInteger z = x.xor(y);
382 BigInteger w = x.or(y).andNot(x.and(y));
383 if (!z.equals(w))
384 failCount++;
385 }
386 report("Logic (^ | & ~) for " + order + " bits", failCount);
387
388 // Test identity x &~ y == ~(~x | y)
389 failCount = 0;
390 for (int i=0; i<size; i++) {
391 BigInteger x = fetchNumber(order);
392 BigInteger y = fetchNumber(order);
393 BigInteger z = x.andNot(y);
394 BigInteger w = x.not().or(y).not();
395 if (!z.equals(w))
396 failCount++;
397 }
398 report("Logic (&~ | ~) for " + order + " bits", failCount);
399 }
400
401 public static void shift(int order) {
402 int failCount1 = 0;
403 int failCount2 = 0;
404 int failCount3 = 0;
405
406 for (int i=0; i<100; i++) {
407 BigInteger x = fetchNumber(order);
408 int n = Math.abs(rnd.nextInt()%200);
409
410 if (!x.shiftLeft(n).equals
423 System.err.println("shift is "+n);
424
425 System.err.println("Divided "+z.toString(2));
426 System.err.println("Shifted is "+b.toString(2));
427 if (b.toString().equals(z.toString()))
428 System.err.println("Houston, we have a problem.");
429 failCount2++;
430 }
431
432 if (!x.shiftLeft(n).shiftRight(n).equals(x))
433 failCount3++;
434 }
435 report("baz shiftLeft for " + order + " bits", failCount1);
436 report("baz shiftRight for " + order + " bits", failCount2);
437 report("baz shiftLeft/Right for " + order + " bits", failCount3);
438 }
439
440 public static void divideAndRemainder(int order) {
441 int failCount1 = 0;
442
443 for (int i=0; i<size; i++) {
444 BigInteger x = fetchNumber(order).abs();
445 while(x.compareTo(BigInteger.valueOf(3L)) != 1)
446 x = fetchNumber(order).abs();
447 BigInteger z = x.divide(BigInteger.valueOf(2L));
448 BigInteger y[] = x.divideAndRemainder(x);
449 if (!y[0].equals(BigInteger.ONE)) {
450 failCount1++;
451 System.err.println("fail1 x :"+x);
452 System.err.println(" y :"+y);
453 }
454 else if (!y[1].equals(BigInteger.ZERO)) {
455 failCount1++;
456 System.err.println("fail2 x :"+x);
457 System.err.println(" y :"+y);
458 }
459
460 y = x.divideAndRemainder(z);
461 if (!y[0].equals(BigInteger.valueOf(2))) {
462 failCount1++;
463 System.err.println("fail3 x :"+x);
502 for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
503 String result = x.toString(radix);
504 BigInteger test = new BigInteger(result, radix);
505 if (!test.equals(x)) {
506 failCount++;
507 System.err.println("BigInteger toString: " + x);
508 System.err.println("Test: " + test);
509 System.err.println(radix);
510 }
511 }
512 }
513 }
514 }
515
516 report("String Conversion", failCount);
517 }
518
519 public static void byteArrayConv(int order) {
520 int failCount = 0;
521
522 for (int i=0; i<size; i++) {
523 BigInteger x = fetchNumber(order);
524 while (x.equals(BigInteger.ZERO))
525 x = fetchNumber(order);
526 BigInteger y = new BigInteger(x.toByteArray());
527 if (!x.equals(y)) {
528 failCount++;
529 System.err.println("orig is "+x);
530 System.err.println("new is "+y);
531 }
532 }
533 report("Array Conversion for " + order + " bits", failCount);
534 }
535
536 public static void modInv(int order) {
537 int failCount = 0, successCount = 0, nonInvCount = 0;
538
539 for (int i=0; i<size; i++) {
540 BigInteger x = fetchNumber(order);
541 while(x.equals(BigInteger.ZERO))
542 x = fetchNumber(order);
543 BigInteger m = fetchNumber(order).abs();
544 while(m.compareTo(BigInteger.ONE) != 1)
545 m = fetchNumber(order).abs();
546
547 try {
548 BigInteger inv = x.modInverse(m);
549 BigInteger prod = inv.multiply(x).remainder(m);
550
551 if (prod.signum() == -1)
552 prod = prod.add(m);
553
554 if (prod.equals(BigInteger.ONE))
555 successCount++;
556 else
557 failCount++;
558 } catch(ArithmeticException e) {
559 nonInvCount++;
560 }
561 }
562 report("Modular Inverse for " + order + " bits", failCount);
563 }
564
565 public static void modExp(int order1, int order2) {
566 int failCount = 0;
567
568 for (int i=0; i<size/10; i++) {
569 BigInteger m = fetchNumber(order1).abs();
570 while(m.compareTo(BigInteger.ONE) != 1)
571 m = fetchNumber(order1).abs();
572 BigInteger base = fetchNumber(order2);
573 BigInteger exp = fetchNumber(8).abs();
574
575 BigInteger z = base.modPow(exp, m);
576 BigInteger w = base.pow(exp.intValue()).mod(m);
577 if (!z.equals(w)) {
578 System.err.println("z is "+z);
579 System.err.println("w is "+w);
580 System.err.println("mod is "+m);
581 System.err.println("base is "+base);
582 System.err.println("exp is "+exp);
583 failCount++;
584 }
585 }
586 report("Exponentiation I for " + order1 + " and " +
587 order2 + " bits", failCount);
588 }
866
867 try (FileInputStream fis = new FileInputStream(f);
868 ObjectInputStream ois = new ObjectInputStream(fis))
869 {
870 b2 = (BigInteger)ois.readObject();
871 }
872 }
873
874 if (!b1.equals(b2) ||
875 !b1.equals(b1.or(b2)))
876 failCount++;
877 f.delete();
878 }
879
880 report("Serialize", failCount);
881 }
882
883 /**
884 * Main to interpret arguments and run several tests.
885 *
886 * Up to three arguments may be given to specify the size of BigIntegers
887 * used for call parameters 1, 2, and 3. The size is interpreted as
888 * the maximum number of decimal digits that the parameters will have.
889 *
890 */
891 public static void main(String[] args) throws Exception {
892
893 // Some variables for sizing test numbers in bits
894 int order1 = ORDER_MEDIUM;
895 int order2 = ORDER_SMALL;
896 int order3 = ORDER_KARATSUBA;
897 int order4 = ORDER_TOOM_COOK;
898
899 if (args.length >0)
900 order1 = (int)((Integer.parseInt(args[0]))* 3.333);
901 if (args.length >1)
902 order2 = (int)((Integer.parseInt(args[1]))* 3.333);
903 if (args.length >2)
904 order3 = (int)((Integer.parseInt(args[2]))* 3.333);
905 if (args.length >3)
906 order4 = (int)((Integer.parseInt(args[3]))* 3.333);
907
928 bitLength();
929 bitOps(order1);
930 bitwise(order1);
931
932 shift(order1);
933
934 byteArrayConv(order1);
935
936 modInv(order1); // small numbers
937 modInv(order3); // Karatsuba / Burnikel-Ziegler range
938 modInv(order4); // Toom-Cook range
939
940 modExp(order1, order2);
941 modExp2(order1);
942
943 stringConv();
944 serialize();
945
946 multiplyLarge();
947 squareLarge();
948
949 if (failure)
950 throw new RuntimeException("Failure in BigIntegerTest.");
951 }
952
953 /*
954 * Get a random or boundary-case number. This is designed to provide
955 * a lot of numbers that will find failure points, such as max sized
956 * numbers, empty BigIntegers, etc.
957 *
958 * If order is less than 2, order is changed to 2.
959 */
960 private static BigInteger fetchNumber(int order) {
961 boolean negative = rnd.nextBoolean();
962 int numType = rnd.nextInt(7);
963 BigInteger result = null;
964 if (order < 2) order = 2;
965
966 switch (numType) {
967 case 0: // Empty
968 result = BigInteger.ZERO;
969 break;
970
971 case 1: // One
972 result = BigInteger.ONE;
973 break;
974
975 case 2: // All bits set in number
976 int numBytes = (order+7)/8;
977 byte[] fullBits = new byte[numBytes];
978 for(int i=0; i<numBytes; i++)
979 fullBits[i] = (byte)0xff;
980 int excessBits = 8*numBytes - order;
981 fullBits[0] &= (1 << (8-excessBits)) - 1;
982 result = new BigInteger(1, fullBits);
983 break;
984
985 case 3: // One bit in number
986 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
987 break;
988
989 case 4: // Random bit density
990 int iterations = rnd.nextInt(order-1);
991 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
992 for(int i=0; i<iterations; i++) {
993 BigInteger temp = BigInteger.ONE.shiftLeft(
994 rnd.nextInt(order));
995 result = result.or(temp);
996 }
997 break;
998 case 5: // Runs of consecutive ones and zeros
999 result = ZERO;
1000 int remaining = order;
1001 int bit = rnd.nextInt(2);
1002 while (remaining > 0) {
1003 int runLength = Math.min(remaining, rnd.nextInt(order));
1004 result = result.shiftLeft(runLength);
1005 if (bit > 0)
1006 result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
1007 remaining -= runLength;
1008 bit = 1 - bit;
1009 }
1010 break;
1011
1012 default: // random bits
1013 result = new BigInteger(order, rnd);
1014 }
1015
1016 if (negative)
|
26 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946
27 * @summary tests methods in BigInteger
28 * @run main/timeout=400 BigIntegerTest
29 * @author madbot
30 */
31
32 import java.io.File;
33 import java.io.FileInputStream;
34 import java.io.FileOutputStream;
35 import java.io.ObjectInputStream;
36 import java.io.ObjectOutputStream;
37 import java.math.BigInteger;
38 import java.util.Random;
39
40 /**
41 * This is a simple test class created to ensure that the results
42 * generated by BigInteger adhere to certain identities. Passing
43 * this test is a strong assurance that the BigInteger operations
44 * are working correctly.
45 *
46 * Four arguments may be specified which give the number of
47 * decimal digits you desire in the four batches of test numbers.
48 *
49 * The tests are performed on arrays of random numbers which are
50 * generated by a Random class as well as special cases which
51 * throw in boundary numbers such as 0, 1, maximum SIZEd, etc.
52 *
53 */
54 public class BigIntegerTest {
55 //
56 // Bit large number thresholds based on the int thresholds
57 // defined in BigInteger itself:
58 //
59 // KARATSUBA_THRESHOLD = 50 ints = 1600 bits
60 // TOOM_COOK_THRESHOLD = 75 ints = 2400 bits
61 // KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits
62 // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
63 //
64 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
65 //
66 // BURNIKEL_ZIEGLER_THRESHOLD = 50 ints = 1600 bits
67 //
68 static final int BITS_KARATSUBA = 1600;
69 static final int BITS_TOOM_COOK = 2400;
70 static final int BITS_KARATSUBA_SQUARE = 2880;
71 static final int BITS_TOOM_COOK_SQUARE = 4480;
72 static final int BITS_SCHOENHAGE_BASE = 256;
73 static final int BITS_BURNIKEL_ZIEGLER = 1600;
74
75 static final int ORDER_SMALL = 60;
76 static final int ORDER_MEDIUM = 100;
77 // #bits for testing Karatsuba and Burnikel-Ziegler
78 static final int ORDER_KARATSUBA = 1800;
79 // #bits for testing Toom-Cook
80 static final int ORDER_TOOM_COOK = 3000;
81 // #bits for testing Karatsuba squaring
82 static final int ORDER_KARATSUBA_SQUARE = 3200;
83 // #bits for testing Toom-Cook squaring
84 static final int ORDER_TOOM_COOK_SQUARE = 4600;
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
94 for (int i=0; i<SIZE; i++) {
95 // Test identity x^power == x*x*x ... *x
96 int power = rnd.nextInt(6) + 2;
97 BigInteger x = fetchNumber(order);
98 BigInteger y = x.pow(power);
99 BigInteger z = x;
100
101 for (int j=1; j<power; j++)
102 z = z.multiply(x);
103
104 if (!y.equals(z))
105 failCount1++;
106 }
107 report("pow for " + order + " bits", failCount1);
108 }
109
110 public static void square(int order) {
111 int failCount1 = 0;
112
113 for (int i=0; i<SIZE; i++) {
114 // Test identity x^2 == x*x
115 BigInteger x = fetchNumber(order);
116 BigInteger xx = x.multiply(x);
117 BigInteger x2 = x.pow(2);
118
119 if (!x2.equals(xx))
120 failCount1++;
121 }
122 report("square for " + order + " bits", failCount1);
123 }
124
125 public static void arithmetic(int order) {
126 int failCount = 0;
127
128 for (int i=0; i<SIZE; i++) {
129 BigInteger x = fetchNumber(order);
130 while(x.compareTo(BigInteger.ZERO) != 1)
131 x = fetchNumber(order);
132 BigInteger y = fetchNumber(order/2);
133 while(x.compareTo(y) == -1)
134 y = fetchNumber(order/2);
135 if (y.equals(BigInteger.ZERO))
136 y = y.add(BigInteger.ONE);
137
138 // Test identity ((x/y))*y + x%y - x == 0
139 // using separate divide() and remainder()
140 BigInteger baz = x.divide(y);
141 baz = baz.multiply(y);
142 baz = baz.add(x.remainder(y));
143 baz = baz.subtract(x);
144 if (!baz.equals(BigInteger.ZERO))
145 failCount++;
146 }
147 report("Arithmetic I for " + order + " bits", failCount);
148
174 * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
175 * construct two factors each with a mag array one element shorter than the
176 * threshold, and with the most significant bit set and the rest of the bits
177 * random. Each of these numbers will therefore be below the threshold but
178 * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
179 * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
180 * identity
181 * <pre>
182 * (u << a)*(v << b) = (u*v) << (a + b)
183 * </pre>
184 * For Karatsuba multiplication, the right hand expression will be evaluated
185 * using the standard naive algorithm, and the left hand expression using
186 * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
187 * hand expression will be evaluated using Karatsuba multiplication, and the
188 * left hand expression using 3-way Toom-Cook multiplication.
189 */
190 public static void multiplyLarge() {
191 int failCount = 0;
192
193 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
194 for (int i=0; i<SIZE; i++) {
195 BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
196 BigInteger u = base.add(x);
197 int a = 1 + rnd.nextInt(31);
198 BigInteger w = u.shiftLeft(a);
199
200 BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
201 BigInteger v = base.add(y);
202 int b = 1 + rnd.nextInt(32);
203 BigInteger z = v.shiftLeft(b);
204
205 BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
206 BigInteger karatsubaMultiplyResult = w.multiply(z);
207
208 if (!multiplyResult.equals(karatsubaMultiplyResult)) {
209 failCount++;
210 }
211 }
212
213 report("multiplyLarge Karatsuba", failCount);
214
215 failCount = 0;
216 base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
217 for (int i=0; i<SIZE; i++) {
218 BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
219 BigInteger u = base.add(x);
220 BigInteger u2 = u.shiftLeft(1);
221 BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
222 BigInteger v = base.add(y);
223 BigInteger v2 = v.shiftLeft(1);
224
225 BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
226 BigInteger toomCookMultiplyResult = u2.multiply(v2);
227
228 if (!multiplyResult.equals(toomCookMultiplyResult)) {
229 failCount++;
230 }
231 }
232
233 report("multiplyLarge Toom-Cook", failCount);
234 }
235
236 /**
237 * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
238 * This test is analogous to {@link AbstractMethodError#multiplyLarge}
239 * with both factors being equal. The squaring methods will not be tested
240 * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
241 * the parameter is the same instance on which the method is being invoked
242 * and calls <code>square()</code> accordingly.
243 */
244 public static void squareLarge() {
245 int failCount = 0;
246
247 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
248 for (int i=0; i<SIZE; i++) {
249 BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
250 BigInteger u = base.add(x);
251 int a = 1 + rnd.nextInt(31);
252 BigInteger w = u.shiftLeft(a);
253
254 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
255 BigInteger karatsubaSquareResult = w.multiply(w);
256
257 if (!squareResult.equals(karatsubaSquareResult)) {
258 failCount++;
259 }
260 }
261
262 report("squareLarge Karatsuba", failCount);
263
264 failCount = 0;
265 base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
266 for (int i=0; i<SIZE; i++) {
267 BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
268 BigInteger u = base.add(x);
269 int a = 1 + rnd.nextInt(31);
270 BigInteger w = u.shiftLeft(a);
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++) {
343 bitCount += ((tmp & 1) == bit ? 1 : 0);
344 tmp >>= 1;
345 }
346
347 if (bigX.bitCount() != bitCount) {
348 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
349 failCount++;
350 }
351 }
352 report("Bit Count", failCount);
353 }
354
355 public static void bitLength() {
356 int failCount = 0;
357
358 for (int i=0; i<SIZE*10; i++) {
359 int x = rnd.nextInt();
360 BigInteger bigX = BigInteger.valueOf((long)x);
361 int signBit = (x < 0 ? 0x80000000 : 0);
362 int tmp = x, bitLength, j;
363 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
364 tmp <<= 1;
365 bitLength = 32 - j;
366
367 if (bigX.bitLength() != bitLength) {
368 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
369 failCount++;
370 }
371 }
372
373 report("BitLength", failCount);
374 }
375
376 public static void bitOps(int order) {
377 int failCount1 = 0, failCount2 = 0, failCount3 = 0;
378
379 for (int i=0; i<SIZE*5; i++) {
380 BigInteger x = fetchNumber(order);
381 BigInteger y;
382
383 // Test setBit and clearBit (and testBit)
384 if (x.signum() < 0) {
385 y = BigInteger.valueOf(-1);
386 for (int j=0; j<x.bitLength(); j++)
387 if (!x.testBit(j))
388 y = y.clearBit(j);
389 } else {
390 y = BigInteger.ZERO;
391 for (int j=0; j<x.bitLength(); j++)
392 if (x.testBit(j))
393 y = y.setBit(j);
394 }
395 if (!x.equals(y))
396 failCount1++;
397
398 // Test flipBit (and testBit)
399 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
400 for (int j=0; j<x.bitLength(); j++)
401 if (x.signum()<0 ^ x.testBit(j))
402 y = y.flipBit(j);
403 if (!x.equals(y))
404 failCount2++;
405 }
406 report("clearBit/testBit for " + order + " bits", failCount1);
407 report("flipBit/testBit for " + order + " bits", failCount2);
408
409 for (int i=0; i<SIZE*5; i++) {
410 BigInteger x = fetchNumber(order);
411
412 // Test getLowestSetBit()
413 int k = x.getLowestSetBit();
414 if (x.signum() == 0) {
415 if (k != -1)
416 failCount3++;
417 } else {
418 BigInteger z = x.and(x.negate());
419 int j;
420 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
421 ;
422 if (k != j)
423 failCount3++;
424 }
425 }
426 report("getLowestSetBit for " + order + " bits", failCount3);
427 }
428
429 public static void bitwise(int order) {
430
431 // Test identity x^y == x|y &~ x&y
432 int failCount = 0;
433 for (int i=0; i<SIZE; i++) {
434 BigInteger x = fetchNumber(order);
435 BigInteger y = fetchNumber(order);
436 BigInteger z = x.xor(y);
437 BigInteger w = x.or(y).andNot(x.and(y));
438 if (!z.equals(w))
439 failCount++;
440 }
441 report("Logic (^ | & ~) for " + order + " bits", failCount);
442
443 // Test identity x &~ y == ~(~x | y)
444 failCount = 0;
445 for (int i=0; i<SIZE; i++) {
446 BigInteger x = fetchNumber(order);
447 BigInteger y = fetchNumber(order);
448 BigInteger z = x.andNot(y);
449 BigInteger w = x.not().or(y).not();
450 if (!z.equals(w))
451 failCount++;
452 }
453 report("Logic (&~ | ~) for " + order + " bits", failCount);
454 }
455
456 public static void shift(int order) {
457 int failCount1 = 0;
458 int failCount2 = 0;
459 int failCount3 = 0;
460
461 for (int i=0; i<100; i++) {
462 BigInteger x = fetchNumber(order);
463 int n = Math.abs(rnd.nextInt()%200);
464
465 if (!x.shiftLeft(n).equals
478 System.err.println("shift is "+n);
479
480 System.err.println("Divided "+z.toString(2));
481 System.err.println("Shifted is "+b.toString(2));
482 if (b.toString().equals(z.toString()))
483 System.err.println("Houston, we have a problem.");
484 failCount2++;
485 }
486
487 if (!x.shiftLeft(n).shiftRight(n).equals(x))
488 failCount3++;
489 }
490 report("baz shiftLeft for " + order + " bits", failCount1);
491 report("baz shiftRight for " + order + " bits", failCount2);
492 report("baz shiftLeft/Right for " + order + " bits", failCount3);
493 }
494
495 public static void divideAndRemainder(int order) {
496 int failCount1 = 0;
497
498 for (int i=0; i<SIZE; i++) {
499 BigInteger x = fetchNumber(order).abs();
500 while(x.compareTo(BigInteger.valueOf(3L)) != 1)
501 x = fetchNumber(order).abs();
502 BigInteger z = x.divide(BigInteger.valueOf(2L));
503 BigInteger y[] = x.divideAndRemainder(x);
504 if (!y[0].equals(BigInteger.ONE)) {
505 failCount1++;
506 System.err.println("fail1 x :"+x);
507 System.err.println(" y :"+y);
508 }
509 else if (!y[1].equals(BigInteger.ZERO)) {
510 failCount1++;
511 System.err.println("fail2 x :"+x);
512 System.err.println(" y :"+y);
513 }
514
515 y = x.divideAndRemainder(z);
516 if (!y[0].equals(BigInteger.valueOf(2))) {
517 failCount1++;
518 System.err.println("fail3 x :"+x);
557 for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
558 String result = x.toString(radix);
559 BigInteger test = new BigInteger(result, radix);
560 if (!test.equals(x)) {
561 failCount++;
562 System.err.println("BigInteger toString: " + x);
563 System.err.println("Test: " + test);
564 System.err.println(radix);
565 }
566 }
567 }
568 }
569 }
570
571 report("String Conversion", failCount);
572 }
573
574 public static void byteArrayConv(int order) {
575 int failCount = 0;
576
577 for (int i=0; i<SIZE; i++) {
578 BigInteger x = fetchNumber(order);
579 while (x.equals(BigInteger.ZERO))
580 x = fetchNumber(order);
581 BigInteger y = new BigInteger(x.toByteArray());
582 if (!x.equals(y)) {
583 failCount++;
584 System.err.println("orig is "+x);
585 System.err.println("new is "+y);
586 }
587 }
588 report("Array Conversion for " + order + " bits", failCount);
589 }
590
591 public static void modInv(int order) {
592 int failCount = 0, successCount = 0, nonInvCount = 0;
593
594 for (int i=0; i<SIZE; i++) {
595 BigInteger x = fetchNumber(order);
596 while(x.equals(BigInteger.ZERO))
597 x = fetchNumber(order);
598 BigInteger m = fetchNumber(order).abs();
599 while(m.compareTo(BigInteger.ONE) != 1)
600 m = fetchNumber(order).abs();
601
602 try {
603 BigInteger inv = x.modInverse(m);
604 BigInteger prod = inv.multiply(x).remainder(m);
605
606 if (prod.signum() == -1)
607 prod = prod.add(m);
608
609 if (prod.equals(BigInteger.ONE))
610 successCount++;
611 else
612 failCount++;
613 } catch(ArithmeticException e) {
614 nonInvCount++;
615 }
616 }
617 report("Modular Inverse for " + order + " bits", failCount);
618 }
619
620 public static void modExp(int order1, int order2) {
621 int failCount = 0;
622
623 for (int i=0; i<SIZE/10; i++) {
624 BigInteger m = fetchNumber(order1).abs();
625 while(m.compareTo(BigInteger.ONE) != 1)
626 m = fetchNumber(order1).abs();
627 BigInteger base = fetchNumber(order2);
628 BigInteger exp = fetchNumber(8).abs();
629
630 BigInteger z = base.modPow(exp, m);
631 BigInteger w = base.pow(exp.intValue()).mod(m);
632 if (!z.equals(w)) {
633 System.err.println("z is "+z);
634 System.err.println("w is "+w);
635 System.err.println("mod is "+m);
636 System.err.println("base is "+base);
637 System.err.println("exp is "+exp);
638 failCount++;
639 }
640 }
641 report("Exponentiation I for " + order1 + " and " +
642 order2 + " bits", failCount);
643 }
921
922 try (FileInputStream fis = new FileInputStream(f);
923 ObjectInputStream ois = new ObjectInputStream(fis))
924 {
925 b2 = (BigInteger)ois.readObject();
926 }
927 }
928
929 if (!b1.equals(b2) ||
930 !b1.equals(b1.or(b2)))
931 failCount++;
932 f.delete();
933 }
934
935 report("Serialize", failCount);
936 }
937
938 /**
939 * Main to interpret arguments and run several tests.
940 *
941 * Up to three arguments may be given to specify the SIZE of BigIntegers
942 * used for call parameters 1, 2, and 3. The SIZE is interpreted as
943 * the maximum number of decimal digits that the parameters will have.
944 *
945 */
946 public static void main(String[] args) throws Exception {
947
948 // Some variables for sizing test numbers in bits
949 int order1 = ORDER_MEDIUM;
950 int order2 = ORDER_SMALL;
951 int order3 = ORDER_KARATSUBA;
952 int order4 = ORDER_TOOM_COOK;
953
954 if (args.length >0)
955 order1 = (int)((Integer.parseInt(args[0]))* 3.333);
956 if (args.length >1)
957 order2 = (int)((Integer.parseInt(args[1]))* 3.333);
958 if (args.length >2)
959 order3 = (int)((Integer.parseInt(args[2]))* 3.333);
960 if (args.length >3)
961 order4 = (int)((Integer.parseInt(args[3]))* 3.333);
962
983 bitLength();
984 bitOps(order1);
985 bitwise(order1);
986
987 shift(order1);
988
989 byteArrayConv(order1);
990
991 modInv(order1); // small numbers
992 modInv(order3); // Karatsuba / Burnikel-Ziegler range
993 modInv(order4); // Toom-Cook range
994
995 modExp(order1, order2);
996 modExp2(order1);
997
998 stringConv();
999 serialize();
1000
1001 multiplyLarge();
1002 squareLarge();
1003 divideLarge();
1004
1005 if (failure)
1006 throw new RuntimeException("Failure in BigIntegerTest.");
1007 }
1008
1009 /*
1010 * Get a random or boundary-case number. This is designed to provide
1011 * a lot of numbers that will find failure points, such as max SIZEd
1012 * numbers, empty BigIntegers, etc.
1013 *
1014 * If order is less than 2, order is changed to 2.
1015 */
1016 private static BigInteger fetchNumber(int order) {
1017 boolean negative = rnd.nextBoolean();
1018 int numType = rnd.nextInt(7);
1019 BigInteger result = null;
1020 if (order < 2) order = 2;
1021
1022 switch (numType) {
1023 case 0: // Empty
1024 result = BigInteger.ZERO;
1025 break;
1026
1027 case 1: // One
1028 result = BigInteger.ONE;
1029 break;
1030
1031 case 2: // All bits set in number
1032 int numBytes = (order+7)/8;
1033 byte[] fullBits = new byte[numBytes];
1034 for(int i=0; i<numBytes; i++)
1035 fullBits[i] = (byte)0xff;
1036 int excessBits = 8*numBytes - order;
1037 fullBits[0] &= (1 << (8-excessBits)) - 1;
1038 result = new BigInteger(1, fullBits);
1039 break;
1040
1041 case 3: // One bit in number
1042 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
1043 break;
1044
1045 case 4: // Random bit density
1046 byte[] val = new byte[(order+7)/8];
1047 int iterations = rnd.nextInt(order);
1048 for (int i=0; i<iterations; i++) {
1049 int bitIdx = rnd.nextInt(order);
1050 val[bitIdx/8] |= 1 << (bitIdx%8);
1051 }
1052 result = new BigInteger(1, val);
1053 break;
1054 case 5: // Runs of consecutive ones and zeros
1055 result = ZERO;
1056 int remaining = order;
1057 int bit = rnd.nextInt(2);
1058 while (remaining > 0) {
1059 int runLength = Math.min(remaining, rnd.nextInt(order));
1060 result = result.shiftLeft(runLength);
1061 if (bit > 0)
1062 result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
1063 remaining -= runLength;
1064 bit = 1 - bit;
1065 }
1066 break;
1067
1068 default: // random bits
1069 result = new BigInteger(order, rnd);
1070 }
1071
1072 if (negative)
|