1 /*
2 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
26 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225
27 * @summary tests methods in BigInteger
28 * @run main/timeout=400 BigIntegerTest
29 * @author madbot
30 */
31
32 import java.util.Random;
33 import java.math.BigInteger;
34 import java.io.*;
35
36 /**
37 * This is a simple test class created to ensure that the results
38 * generated by BigInteger adhere to certain identities. Passing
39 * this test is a strong assurance that the BigInteger operations
40 * are working correctly.
41 *
42 * Three arguments may be specified which give the number of
43 * decimal digits you desire in the three batches of test numbers.
44 *
45 * The tests are performed on arrays of random numbers which are
46 * generated by a Random class as well as special cases which
47 * throw in boundary numbers such as 0, 1, maximum sized, etc.
48 *
49 */
50 public class BigIntegerTest {
51 static Random rnd = new Random();
52 static int size = 1000; // numbers per batch
53 static boolean failure = false;
54
55 // Some variables for sizing test numbers in bits
56 private static int order1 = 100;
57 private static int order2 = 60;
58 private static int order3 = 30;
59
60 public static void pow() {
61 int failCount1 = 0;
62
63 for (int i=0; i<size; i++) {
64 int power = rnd.nextInt(6) +2;
65 BigInteger x = fetchNumber(order1);
66 BigInteger y = x.pow(power);
67 BigInteger z = x;
68
69 for (int j=1; j<power; j++)
70 z = z.multiply(x);
71
72 if (!y.equals(z))
73 failCount1++;
74 }
75 report("pow", failCount1);
76 }
77
78 public static void arithmetic() {
79 int failCount = 0;
80
81 for (int i=0; i<size; i++) {
82 BigInteger x = fetchNumber(order1);
83 while(x.compareTo(BigInteger.ZERO) != 1)
84 x = fetchNumber(order1);
85 BigInteger y = fetchNumber(order1/2);
86 while(x.compareTo(y) == -1)
87 y = fetchNumber(order1/2);
88 if (y.equals(BigInteger.ZERO))
89 y = y.add(BigInteger.ONE);
90
91 BigInteger baz = x.divide(y);
92 baz = baz.multiply(y);
93 baz = baz.add(x.remainder(y));
94 baz = baz.subtract(x);
95 if (!baz.equals(BigInteger.ZERO))
96 failCount++;
97 }
98 report("Arithmetic I", failCount);
99
100 failCount = 0;
101 for (int i=0; i<100; i++) {
102 BigInteger x = fetchNumber(order1);
103 while(x.compareTo(BigInteger.ZERO) != 1)
104 x = fetchNumber(order1);
105 BigInteger y = fetchNumber(order1/2);
106 while(x.compareTo(y) == -1)
107 y = fetchNumber(order1/2);
108 if (y.equals(BigInteger.ZERO))
109 y = y.add(BigInteger.ONE);
110
111 BigInteger baz[] = x.divideAndRemainder(y);
112 baz[0] = baz[0].multiply(y);
113 baz[0] = baz[0].add(baz[1]);
114 baz[0] = baz[0].subtract(x);
115 if (!baz[0].equals(BigInteger.ZERO))
116 failCount++;
117 }
118 report("Arithmetic II", failCount);
119 }
120
121 public static void bitCount() {
122 int failCount = 0;
123
124 for (int i=0; i<size*10; i++) {
125 int x = rnd.nextInt();
126 BigInteger bigX = BigInteger.valueOf((long)x);
127 int bit = (x < 0 ? 0 : 1);
128 int tmp = x, bitCount = 0;
129 for (int j=0; j<32; j++) {
130 bitCount += ((tmp & 1) == bit ? 1 : 0);
131 tmp >>= 1;
132 }
133
134 if (bigX.bitCount() != bitCount) {
135 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
136 failCount++;
137 }
138 }
143 int failCount = 0;
144
145 for (int i=0; i<size*10; i++) {
146 int x = rnd.nextInt();
147 BigInteger bigX = BigInteger.valueOf((long)x);
148 int signBit = (x < 0 ? 0x80000000 : 0);
149 int tmp = x, bitLength, j;
150 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
151 tmp <<= 1;
152 bitLength = 32 - j;
153
154 if (bigX.bitLength() != bitLength) {
155 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
156 failCount++;
157 }
158 }
159
160 report("BitLength", failCount);
161 }
162
163 public static void bitOps() {
164 int failCount1 = 0, failCount2 = 0, failCount3 = 0;
165
166 for (int i=0; i<size*5; i++) {
167 BigInteger x = fetchNumber(order1);
168 BigInteger y;
169
170 /* Test setBit and clearBit (and testBit) */
171 if (x.signum() < 0) {
172 y = BigInteger.valueOf(-1);
173 for (int j=0; j<x.bitLength(); j++)
174 if (!x.testBit(j))
175 y = y.clearBit(j);
176 } else {
177 y = BigInteger.ZERO;
178 for (int j=0; j<x.bitLength(); j++)
179 if (x.testBit(j))
180 y = y.setBit(j);
181 }
182 if (!x.equals(y))
183 failCount1++;
184
185 /* Test flipBit (and testBit) */
186 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
187 for (int j=0; j<x.bitLength(); j++)
188 if (x.signum()<0 ^ x.testBit(j))
189 y = y.flipBit(j);
190 if (!x.equals(y))
191 failCount2++;
192 }
193 report("clearBit/testBit", failCount1);
194 report("flipBit/testBit", failCount2);
195
196 for (int i=0; i<size*5; i++) {
197 BigInteger x = fetchNumber(order1);
198
199 /* Test getLowestSetBit() */
200 int k = x.getLowestSetBit();
201 if (x.signum() == 0) {
202 if (k != -1)
203 failCount3++;
204 } else {
205 BigInteger z = x.and(x.negate());
206 int j;
207 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
208 ;
209 if (k != j)
210 failCount3++;
211 }
212 }
213 report("getLowestSetBit", failCount3);
214 }
215
216 public static void bitwise() {
217
218 /* Test identity x^y == x|y &~ x&y */
219 int failCount = 0;
220 for (int i=0; i<size; i++) {
221 BigInteger x = fetchNumber(order1);
222 BigInteger y = fetchNumber(order1);
223 BigInteger z = x.xor(y);
224 BigInteger w = x.or(y).andNot(x.and(y));
225 if (!z.equals(w))
226 failCount++;
227 }
228 report("Logic (^ | & ~)", failCount);
229
230 /* Test identity x &~ y == ~(~x | y) */
231 failCount = 0;
232 for (int i=0; i<size; i++) {
233 BigInteger x = fetchNumber(order1);
234 BigInteger y = fetchNumber(order1);
235 BigInteger z = x.andNot(y);
236 BigInteger w = x.not().or(y).not();
237 if (!z.equals(w))
238 failCount++;
239 }
240 report("Logic (&~ | ~)", failCount);
241 }
242
243 public static void shift() {
244 int failCount1 = 0;
245 int failCount2 = 0;
246 int failCount3 = 0;
247
248 for (int i=0; i<100; i++) {
249 BigInteger x = fetchNumber(order1);
250 int n = Math.abs(rnd.nextInt()%200);
251
252 if (!x.shiftLeft(n).equals
253 (x.multiply(BigInteger.valueOf(2L).pow(n))))
254 failCount1++;
255
256 BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));
257 BigInteger z = (x.signum()<0 && y[1].signum()!=0
258 ? y[0].subtract(BigInteger.ONE)
259 : y[0]);
260
261 BigInteger b = x.shiftRight(n);
262
263 if (!b.equals(z)) {
264 System.err.println("Input is "+x.toString(2));
265 System.err.println("shift is "+n);
266
267 System.err.println("Divided "+z.toString(2));
268 System.err.println("Shifted is "+b.toString(2));
269 if (b.toString().equals(z.toString()))
270 System.err.println("Houston, we have a problem.");
271 failCount2++;
272 }
273
274 if (!x.shiftLeft(n).shiftRight(n).equals(x))
275 failCount3++;
276 }
277 report("baz shiftLeft", failCount1);
278 report("baz shiftRight", failCount2);
279 report("baz shiftLeft/Right", failCount3);
280 }
281
282 public static void divideAndRemainder() {
283 int failCount1 = 0;
284
285 for (int i=0; i<size; i++) {
286 BigInteger x = fetchNumber(order1).abs();
287 while(x.compareTo(BigInteger.valueOf(3L)) != 1)
288 x = fetchNumber(order1).abs();
289 BigInteger z = x.divide(BigInteger.valueOf(2L));
290 BigInteger y[] = x.divideAndRemainder(x);
291 if (!y[0].equals(BigInteger.ONE)) {
292 failCount1++;
293 System.err.println("fail1 x :"+x);
294 System.err.println(" y :"+y);
295 }
296 else if (!y[1].equals(BigInteger.ZERO)) {
297 failCount1++;
298 System.err.println("fail2 x :"+x);
299 System.err.println(" y :"+y);
300 }
301
302 y = x.divideAndRemainder(z);
303 if (!y[0].equals(BigInteger.valueOf(2))) {
304 failCount1++;
305 System.err.println("fail3 x :"+x);
306 System.err.println(" y :"+y);
307 }
308 }
309 report("divideAndRemainder I", failCount1);
310 }
311
312 public static void stringConv() {
313 int failCount = 0;
314
315 for (int i=0; i<100; i++) {
316 byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1];
317 rnd.nextBytes(xBytes);
318 BigInteger x = new BigInteger(xBytes);
319
320 for (int radix=2; radix < 37; radix++) {
321 String result = x.toString(radix);
322 BigInteger test = new BigInteger(result, radix);
323 if (!test.equals(x)) {
324 failCount++;
325 System.err.println("BigInteger toString: "+x);
326 System.err.println("Test: "+test);
327 System.err.println(radix);
328 }
329 }
330 }
331 report("String Conversion", failCount);
332 }
333
334 public static void byteArrayConv() {
335 int failCount = 0;
336
337 for (int i=0; i<size; i++) {
338 BigInteger x = fetchNumber(order1);
339 while (x.equals(BigInteger.ZERO))
340 x = fetchNumber(order1);
341 BigInteger y = new BigInteger(x.toByteArray());
342 if (!x.equals(y)) {
343 failCount++;
344 System.err.println("orig is "+x);
345 System.err.println("new is "+y);
346 }
347 }
348 report("Array Conversion", failCount);
349 }
350
351 public static void modInv() {
352 int failCount = 0, successCount = 0, nonInvCount = 0;
353
354 for (int i=0; i<size; i++) {
355 BigInteger x = fetchNumber(order1);
356 while(x.equals(BigInteger.ZERO))
357 x = fetchNumber(order1);
358 BigInteger m = fetchNumber(order1).abs();
359 while(m.compareTo(BigInteger.ONE) != 1)
360 m = fetchNumber(order1).abs();
361
362 try {
363 BigInteger inv = x.modInverse(m);
364 BigInteger prod = inv.multiply(x).remainder(m);
365
366 if (prod.signum() == -1)
367 prod = prod.add(m);
368
369 if (prod.equals(BigInteger.ONE))
370 successCount++;
371 else
372 failCount++;
373 } catch(ArithmeticException e) {
374 nonInvCount++;
375 }
376 }
377 report("Modular Inverse", failCount);
378 }
379
380 public static void modExp() {
381 int failCount = 0;
382
383 for (int i=0; i<size/10; i++) {
384 BigInteger m = fetchNumber(order1).abs();
385 while(m.compareTo(BigInteger.ONE) != 1)
386 m = fetchNumber(order1).abs();
387 BigInteger base = fetchNumber(order2);
388 BigInteger exp = fetchNumber(8).abs();
389
390 BigInteger z = base.modPow(exp, m);
391 BigInteger w = base.pow(exp.intValue()).mod(m);
392 if (!z.equals(w)) {
393 System.err.println("z is "+z);
394 System.err.println("w is "+w);
395 System.err.println("mod is "+m);
396 System.err.println("base is "+base);
397 System.err.println("exp is "+exp);
398 failCount++;
399 }
400 }
401 report("Exponentiation I", failCount);
402 }
403
404 // This test is based on Fermat's theorem
405 // which is not ideal because base must not be multiple of modulus
406 // and modulus must be a prime or pseudoprime (Carmichael number)
407 public static void modExp2() {
408 int failCount = 0;
409
410 for (int i=0; i<10; i++) {
411 BigInteger m = new BigInteger(100, 5, rnd);
412 while(m.compareTo(BigInteger.ONE) != 1)
413 m = new BigInteger(100, 5, rnd);
414 BigInteger exp = m.subtract(BigInteger.ONE);
415 BigInteger base = fetchNumber(order1).abs();
416 while(base.compareTo(m) != -1)
417 base = fetchNumber(order1).abs();
418 while(base.equals(BigInteger.ZERO))
419 base = fetchNumber(order1).abs();
420
421 BigInteger one = base.modPow(exp, m);
422 if (!one.equals(BigInteger.ONE)) {
423 System.err.println("m is "+m);
424 System.err.println("base is "+base);
425 System.err.println("exp is "+exp);
426 failCount++;
427 }
428 }
429 report("Exponentiation II", failCount);
430 }
431
432 private static final int[] mersenne_powers = {
433 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
434 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
435 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };
436
437 private static final long[] carmichaels = {
438 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
439 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
440 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
441 225593397919L };
442
443 // Note: testing the larger ones takes too long.
444 private static final int NUM_MERSENNES_TO_TEST = 7;
445 // Note: this constant used for computed Carmichaels, not the array above
446 private static final int NUM_CARMICHAELS_TO_TEST = 5;
447
448 private static final String[] customer_primes = {
449 "120000000000000000000000000000000019",
687
688 if (!b1.equals(b2) ||
689 !b1.equals(b1.or(b2)))
690 failCount++;
691 f.delete();
692 }
693
694 report("Serialize", failCount);
695 }
696
697 /**
698 * Main to interpret arguments and run several tests.
699 *
700 * Up to three arguments may be given to specify the size of BigIntegers
701 * used for call parameters 1, 2, and 3. The size is interpreted as
702 * the maximum number of decimal digits that the parameters will have.
703 *
704 */
705 public static void main(String[] args) throws Exception {
706
707 if (args.length >0)
708 order1 = (int)((Integer.parseInt(args[0]))* 3.333);
709 if (args.length >1)
710 order2 = (int)((Integer.parseInt(args[1]))* 3.333);
711 if (args.length >2)
712 order3 = (int)((Integer.parseInt(args[2]))* 3.333);
713
714 prime();
715 nextProbablePrime();
716
717 arithmetic();
718 divideAndRemainder();
719 pow();
720
721 bitCount();
722 bitLength();
723 bitOps();
724 bitwise();
725
726 shift();
727
728 byteArrayConv();
729
730 modInv();
731 modExp();
732 modExp2();
733
734 stringConv();
735 serialize();
736
737 if (failure)
738 throw new RuntimeException("Failure in BigIntegerTest.");
739 }
740
741 /*
742 * Get a random or boundary-case number. This is designed to provide
743 * a lot of numbers that will find failure points, such as max sized
744 * numbers, empty BigIntegers, etc.
745 *
746 * If order is less than 2, order is changed to 2.
747 */
748 private static BigInteger fetchNumber(int order) {
749 boolean negative = rnd.nextBoolean();
750 int numType = rnd.nextInt(6);
751 BigInteger result = null;
752 if (order < 2) order = 2;
753
754 switch (numType) {
755 case 0: // Empty
756 result = BigInteger.ZERO;
757 break;
758
759 case 1: // One
760 result = BigInteger.ONE;
761 break;
762
763 case 2: // All bits set in number
764 int numBytes = (order+7)/8;
765 byte[] fullBits = new byte[numBytes];
766 for(int i=0; i<numBytes; i++)
767 fullBits[i] = (byte)0xff;
768 int excessBits = 8*numBytes - order;
769 fullBits[0] &= (1 << (8-excessBits)) - 1;
770 result = new BigInteger(1, fullBits);
771 break;
772
773 case 3: // One bit in number
774 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
775 break;
776
777 case 4: // Random bit density
778 int iterations = rnd.nextInt(order-1);
779 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
780 for(int i=0; i<iterations; i++) {
781 BigInteger temp = BigInteger.ONE.shiftLeft(
782 rnd.nextInt(order));
783 result = result.or(temp);
784 }
785 break;
786
787 default: // random bits
788 result = new BigInteger(order, rnd);
789 }
790
791 if (negative)
792 result = result.negate();
793
794 return result;
795 }
796
797 static void report(String testName, int failCount) {
798 System.err.println(testName+": " +
799 (failCount==0 ? "Passed":"Failed("+failCount+")"));
800 if (failCount > 0)
801 failure = true;
802 }
803 }
|
1 /*
2 * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /*
25 * @test
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 static final int BITS_KARATSUBA = 1600;
65 static final int BITS_TOOM_COOK = 2400;
66 static final int BITS_KARATSUBA_SQUARE = 2880;
67 static final int BITS_TOOM_COOK_SQUARE = 4480;
68
69 static final int ORDER_SMALL = 60;
70 static final int ORDER_MEDIUM = 100;
71 // #bits for testing Karatsuba and Burnikel-Ziegler
72 static final int ORDER_KARATSUBA = 1800;
73 // #bits for testing Toom-Cook
74 static final int ORDER_TOOM_COOK = 3000;
75 // #bits for testing Karatsuba squaring
76 static final int ORDER_KARATSUBA_SQUARE = 3200;
77 // #bits for testing Toom-Cook squaring
78 static final int ORDER_TOOM_COOK_SQUARE = 4600;
79
80 static Random rnd = new Random();
81 static int size = 1000; // numbers per batch
82 static boolean failure = false;
83
84 public static void pow(int order) {
85 int failCount1 = 0;
86
87 for (int i=0; i<size; i++) {
88 // Test identity x^power == x*x*x ... *x
89 int power = rnd.nextInt(6) + 2;
90 BigInteger x = fetchNumber(order);
91 BigInteger y = x.pow(power);
92 BigInteger z = x;
93
94 for (int j=1; j<power; j++)
95 z = z.multiply(x);
96
97 if (!y.equals(z))
98 failCount1++;
99 }
100 report("pow for " + order + " bits", failCount1);
101 }
102
103 public static void square(int order) {
104 int failCount1 = 0;
105
106 for (int i=0; i<size; i++) {
107 // Test identity x^2 == x*x
108 BigInteger x = fetchNumber(order);
109 BigInteger xx = x.multiply(x);
110 BigInteger x2 = x.pow(2);
111
112 if (!x2.equals(xx))
113 failCount1++;
114 }
115 report("square for " + order + " bits", failCount1);
116 }
117
118 public static void arithmetic(int order) {
119 int failCount = 0;
120
121 for (int i=0; i<size; i++) {
122 BigInteger x = fetchNumber(order);
123 while(x.compareTo(BigInteger.ZERO) != 1)
124 x = fetchNumber(order);
125 BigInteger y = fetchNumber(order/2);
126 while(x.compareTo(y) == -1)
127 y = fetchNumber(order/2);
128 if (y.equals(BigInteger.ZERO))
129 y = y.add(BigInteger.ONE);
130
131 // Test identity ((x/y))*y + x%y - x == 0
132 // using separate divide() and remainder()
133 BigInteger baz = x.divide(y);
134 baz = baz.multiply(y);
135 baz = baz.add(x.remainder(y));
136 baz = baz.subtract(x);
137 if (!baz.equals(BigInteger.ZERO))
138 failCount++;
139 }
140 report("Arithmetic I for " + order + " bits", failCount);
141
142 failCount = 0;
143 for (int i=0; i<100; i++) {
144 BigInteger x = fetchNumber(order);
145 while(x.compareTo(BigInteger.ZERO) != 1)
146 x = fetchNumber(order);
147 BigInteger y = fetchNumber(order/2);
148 while(x.compareTo(y) == -1)
149 y = fetchNumber(order/2);
150 if (y.equals(BigInteger.ZERO))
151 y = y.add(BigInteger.ONE);
152
153 // Test identity ((x/y))*y + x%y - x == 0
154 // using divideAndRemainder()
155 BigInteger baz[] = x.divideAndRemainder(y);
156 baz[0] = baz[0].multiply(y);
157 baz[0] = baz[0].add(baz[1]);
158 baz[0] = baz[0].subtract(x);
159 if (!baz[0].equals(BigInteger.ZERO))
160 failCount++;
161 }
162 report("Arithmetic II for " + order + " bits", failCount);
163 }
164
165 /**
166 * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.
167 * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
168 * construct two factors each with a mag array one element shorter than the
169 * threshold, and with the most significant bit set and the rest of the bits
170 * random. Each of these numbers will therefore be below the threshold but
171 * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
172 * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
173 * identity
174 * <pre>
175 * (u << a)*(v << b) = (u*v) << (a + b)
176 * </pre>
177 * For Karatsuba multiplication, the right hand expression will be evaluated
178 * using the standard naive algorithm, and the left hand expression using
179 * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
180 * hand expression will be evaluated using Karatsuba multiplication, and the
181 * left hand expression using 3-way Toom-Cook multiplication.
182 */
183 public static void multiplyLarge() {
184 int failCount = 0;
185
186 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
187 for (int i=0; i<size; i++) {
188 BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
189 BigInteger u = base.add(x);
190 int a = 1 + rnd.nextInt(31);
191 BigInteger w = u.shiftLeft(a);
192
193 BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
194 BigInteger v = base.add(y);
195 int b = 1 + rnd.nextInt(32);
196 BigInteger z = v.shiftLeft(b);
197
198 BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
199 BigInteger karatsubaMultiplyResult = w.multiply(z);
200
201 if (!multiplyResult.equals(karatsubaMultiplyResult)) {
202 failCount++;
203 }
204 }
205
206 report("multiplyLarge Karatsuba", failCount);
207
208 failCount = 0;
209 base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
210 for (int i=0; i<size; i++) {
211 BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
212 BigInteger u = base.add(x);
213 BigInteger u2 = u.shiftLeft(1);
214 BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
215 BigInteger v = base.add(y);
216 BigInteger v2 = v.shiftLeft(1);
217
218 BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
219 BigInteger toomCookMultiplyResult = u2.multiply(v2);
220
221 if (!multiplyResult.equals(toomCookMultiplyResult)) {
222 failCount++;
223 }
224 }
225
226 report("multiplyLarge Toom-Cook", failCount);
227 }
228
229 /**
230 * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
231 * This test is analogous to {@link AbstractMethodError#multiplyLarge}
232 * with both factors being equal. The squaring methods will not be tested
233 * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
234 * the parameter is the same instance on which the method is being invoked
235 * and calls <code>square()</code> accordingly.
236 */
237 public static void squareLarge() {
238 int failCount = 0;
239
240 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
241 for (int i=0; i<size; i++) {
242 BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
243 BigInteger u = base.add(x);
244 int a = 1 + rnd.nextInt(31);
245 BigInteger w = u.shiftLeft(a);
246
247 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
248 BigInteger karatsubaSquareResult = w.multiply(w);
249
250 if (!squareResult.equals(karatsubaSquareResult)) {
251 failCount++;
252 }
253 }
254
255 report("squareLarge Karatsuba", failCount);
256
257 failCount = 0;
258 base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
259 for (int i=0; i<size; i++) {
260 BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
261 BigInteger u = base.add(x);
262 int a = 1 + rnd.nextInt(31);
263 BigInteger w = u.shiftLeft(a);
264
265 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
266 BigInteger toomCookSquareResult = w.multiply(w);
267
268 if (!squareResult.equals(toomCookSquareResult)) {
269 failCount++;
270 }
271 }
272
273 report("squareLarge Toom-Cook", failCount);
274 }
275
276 public static void bitCount() {
277 int failCount = 0;
278
279 for (int i=0; i<size*10; i++) {
280 int x = rnd.nextInt();
281 BigInteger bigX = BigInteger.valueOf((long)x);
282 int bit = (x < 0 ? 0 : 1);
283 int tmp = x, bitCount = 0;
284 for (int j=0; j<32; j++) {
285 bitCount += ((tmp & 1) == bit ? 1 : 0);
286 tmp >>= 1;
287 }
288
289 if (bigX.bitCount() != bitCount) {
290 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
291 failCount++;
292 }
293 }
298 int failCount = 0;
299
300 for (int i=0; i<size*10; i++) {
301 int x = rnd.nextInt();
302 BigInteger bigX = BigInteger.valueOf((long)x);
303 int signBit = (x < 0 ? 0x80000000 : 0);
304 int tmp = x, bitLength, j;
305 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
306 tmp <<= 1;
307 bitLength = 32 - j;
308
309 if (bigX.bitLength() != bitLength) {
310 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
311 failCount++;
312 }
313 }
314
315 report("BitLength", failCount);
316 }
317
318 public static void bitOps(int order) {
319 int failCount1 = 0, failCount2 = 0, failCount3 = 0;
320
321 for (int i=0; i<size*5; i++) {
322 BigInteger x = fetchNumber(order);
323 BigInteger y;
324
325 // Test setBit and clearBit (and testBit)
326 if (x.signum() < 0) {
327 y = BigInteger.valueOf(-1);
328 for (int j=0; j<x.bitLength(); j++)
329 if (!x.testBit(j))
330 y = y.clearBit(j);
331 } else {
332 y = BigInteger.ZERO;
333 for (int j=0; j<x.bitLength(); j++)
334 if (x.testBit(j))
335 y = y.setBit(j);
336 }
337 if (!x.equals(y))
338 failCount1++;
339
340 // Test flipBit (and testBit)
341 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
342 for (int j=0; j<x.bitLength(); j++)
343 if (x.signum()<0 ^ x.testBit(j))
344 y = y.flipBit(j);
345 if (!x.equals(y))
346 failCount2++;
347 }
348 report("clearBit/testBit for " + order + " bits", failCount1);
349 report("flipBit/testBit for " + order + " bits", failCount2);
350
351 for (int i=0; i<size*5; i++) {
352 BigInteger x = fetchNumber(order);
353
354 // Test getLowestSetBit()
355 int k = x.getLowestSetBit();
356 if (x.signum() == 0) {
357 if (k != -1)
358 failCount3++;
359 } else {
360 BigInteger z = x.and(x.negate());
361 int j;
362 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
363 ;
364 if (k != j)
365 failCount3++;
366 }
367 }
368 report("getLowestSetBit for " + order + " bits", failCount3);
369 }
370
371 public static void bitwise(int order) {
372
373 // Test identity x^y == x|y &~ x&y
374 int failCount = 0;
375 for (int i=0; i<size; i++) {
376 BigInteger x = fetchNumber(order);
377 BigInteger y = fetchNumber(order);
378 BigInteger z = x.xor(y);
379 BigInteger w = x.or(y).andNot(x.and(y));
380 if (!z.equals(w))
381 failCount++;
382 }
383 report("Logic (^ | & ~) for " + order + " bits", failCount);
384
385 // Test identity x &~ y == ~(~x | y)
386 failCount = 0;
387 for (int i=0; i<size; i++) {
388 BigInteger x = fetchNumber(order);
389 BigInteger y = fetchNumber(order);
390 BigInteger z = x.andNot(y);
391 BigInteger w = x.not().or(y).not();
392 if (!z.equals(w))
393 failCount++;
394 }
395 report("Logic (&~ | ~) for " + order + " bits", failCount);
396 }
397
398 public static void shift(int order) {
399 int failCount1 = 0;
400 int failCount2 = 0;
401 int failCount3 = 0;
402
403 for (int i=0; i<100; i++) {
404 BigInteger x = fetchNumber(order);
405 int n = Math.abs(rnd.nextInt()%200);
406
407 if (!x.shiftLeft(n).equals
408 (x.multiply(BigInteger.valueOf(2L).pow(n))))
409 failCount1++;
410
411 BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));
412 BigInteger z = (x.signum()<0 && y[1].signum()!=0
413 ? y[0].subtract(BigInteger.ONE)
414 : y[0]);
415
416 BigInteger b = x.shiftRight(n);
417
418 if (!b.equals(z)) {
419 System.err.println("Input is "+x.toString(2));
420 System.err.println("shift is "+n);
421
422 System.err.println("Divided "+z.toString(2));
423 System.err.println("Shifted is "+b.toString(2));
424 if (b.toString().equals(z.toString()))
425 System.err.println("Houston, we have a problem.");
426 failCount2++;
427 }
428
429 if (!x.shiftLeft(n).shiftRight(n).equals(x))
430 failCount3++;
431 }
432 report("baz shiftLeft for " + order + " bits", failCount1);
433 report("baz shiftRight for " + order + " bits", failCount2);
434 report("baz shiftLeft/Right for " + order + " bits", failCount3);
435 }
436
437 public static void divideAndRemainder(int order) {
438 int failCount1 = 0;
439
440 for (int i=0; i<size; i++) {
441 BigInteger x = fetchNumber(order).abs();
442 while(x.compareTo(BigInteger.valueOf(3L)) != 1)
443 x = fetchNumber(order).abs();
444 BigInteger z = x.divide(BigInteger.valueOf(2L));
445 BigInteger y[] = x.divideAndRemainder(x);
446 if (!y[0].equals(BigInteger.ONE)) {
447 failCount1++;
448 System.err.println("fail1 x :"+x);
449 System.err.println(" y :"+y);
450 }
451 else if (!y[1].equals(BigInteger.ZERO)) {
452 failCount1++;
453 System.err.println("fail2 x :"+x);
454 System.err.println(" y :"+y);
455 }
456
457 y = x.divideAndRemainder(z);
458 if (!y[0].equals(BigInteger.valueOf(2))) {
459 failCount1++;
460 System.err.println("fail3 x :"+x);
461 System.err.println(" y :"+y);
462 }
463 }
464 report("divideAndRemainder for " + order + " bits", failCount1);
465 }
466
467 public static void stringConv() {
468 int failCount = 0;
469
470 for (int i=0; i<100; i++) {
471 byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1];
472 rnd.nextBytes(xBytes);
473 BigInteger x = new BigInteger(xBytes);
474
475 for (int radix=2; radix < 37; radix++) {
476 String result = x.toString(radix);
477 BigInteger test = new BigInteger(result, radix);
478 if (!test.equals(x)) {
479 failCount++;
480 System.err.println("BigInteger toString: "+x);
481 System.err.println("Test: "+test);
482 System.err.println(radix);
483 }
484 }
485 }
486 report("String Conversion", failCount);
487 }
488
489 public static void byteArrayConv(int order) {
490 int failCount = 0;
491
492 for (int i=0; i<size; i++) {
493 BigInteger x = fetchNumber(order);
494 while (x.equals(BigInteger.ZERO))
495 x = fetchNumber(order);
496 BigInteger y = new BigInteger(x.toByteArray());
497 if (!x.equals(y)) {
498 failCount++;
499 System.err.println("orig is "+x);
500 System.err.println("new is "+y);
501 }
502 }
503 report("Array Conversion for " + order + " bits", failCount);
504 }
505
506 public static void modInv(int order) {
507 int failCount = 0, successCount = 0, nonInvCount = 0;
508
509 for (int i=0; i<size; i++) {
510 BigInteger x = fetchNumber(order);
511 while(x.equals(BigInteger.ZERO))
512 x = fetchNumber(order);
513 BigInteger m = fetchNumber(order).abs();
514 while(m.compareTo(BigInteger.ONE) != 1)
515 m = fetchNumber(order).abs();
516
517 try {
518 BigInteger inv = x.modInverse(m);
519 BigInteger prod = inv.multiply(x).remainder(m);
520
521 if (prod.signum() == -1)
522 prod = prod.add(m);
523
524 if (prod.equals(BigInteger.ONE))
525 successCount++;
526 else
527 failCount++;
528 } catch(ArithmeticException e) {
529 nonInvCount++;
530 }
531 }
532 report("Modular Inverse for " + order + " bits", failCount);
533 }
534
535 public static void modExp(int order1, int order2) {
536 int failCount = 0;
537
538 for (int i=0; i<size/10; i++) {
539 BigInteger m = fetchNumber(order1).abs();
540 while(m.compareTo(BigInteger.ONE) != 1)
541 m = fetchNumber(order1).abs();
542 BigInteger base = fetchNumber(order2);
543 BigInteger exp = fetchNumber(8).abs();
544
545 BigInteger z = base.modPow(exp, m);
546 BigInteger w = base.pow(exp.intValue()).mod(m);
547 if (!z.equals(w)) {
548 System.err.println("z is "+z);
549 System.err.println("w is "+w);
550 System.err.println("mod is "+m);
551 System.err.println("base is "+base);
552 System.err.println("exp is "+exp);
553 failCount++;
554 }
555 }
556 report("Exponentiation I for " + order1 + " and " +
557 order2 + " bits", failCount);
558 }
559
560 // This test is based on Fermat's theorem
561 // which is not ideal because base must not be multiple of modulus
562 // and modulus must be a prime or pseudoprime (Carmichael number)
563 public static void modExp2(int order) {
564 int failCount = 0;
565
566 for (int i=0; i<10; i++) {
567 BigInteger m = new BigInteger(100, 5, rnd);
568 while(m.compareTo(BigInteger.ONE) != 1)
569 m = new BigInteger(100, 5, rnd);
570 BigInteger exp = m.subtract(BigInteger.ONE);
571 BigInteger base = fetchNumber(order).abs();
572 while(base.compareTo(m) != -1)
573 base = fetchNumber(order).abs();
574 while(base.equals(BigInteger.ZERO))
575 base = fetchNumber(order).abs();
576
577 BigInteger one = base.modPow(exp, m);
578 if (!one.equals(BigInteger.ONE)) {
579 System.err.println("m is "+m);
580 System.err.println("base is "+base);
581 System.err.println("exp is "+exp);
582 failCount++;
583 }
584 }
585 report("Exponentiation II for " + order + " bits", failCount);
586 }
587
588 private static final int[] mersenne_powers = {
589 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
590 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
591 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };
592
593 private static final long[] carmichaels = {
594 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
595 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
596 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
597 225593397919L };
598
599 // Note: testing the larger ones takes too long.
600 private static final int NUM_MERSENNES_TO_TEST = 7;
601 // Note: this constant used for computed Carmichaels, not the array above
602 private static final int NUM_CARMICHAELS_TO_TEST = 5;
603
604 private static final String[] customer_primes = {
605 "120000000000000000000000000000000019",
843
844 if (!b1.equals(b2) ||
845 !b1.equals(b1.or(b2)))
846 failCount++;
847 f.delete();
848 }
849
850 report("Serialize", failCount);
851 }
852
853 /**
854 * Main to interpret arguments and run several tests.
855 *
856 * Up to three arguments may be given to specify the size of BigIntegers
857 * used for call parameters 1, 2, and 3. The size is interpreted as
858 * the maximum number of decimal digits that the parameters will have.
859 *
860 */
861 public static void main(String[] args) throws Exception {
862
863 // Some variables for sizing test numbers in bits
864 int order1 = ORDER_MEDIUM;
865 int order2 = ORDER_SMALL;
866 int order3 = ORDER_KARATSUBA;
867 int order4 = ORDER_TOOM_COOK;
868
869 if (args.length >0)
870 order1 = (int)((Integer.parseInt(args[0]))* 3.333);
871 if (args.length >1)
872 order2 = (int)((Integer.parseInt(args[1]))* 3.333);
873 if (args.length >2)
874 order3 = (int)((Integer.parseInt(args[2]))* 3.333);
875 if (args.length >3)
876 order4 = (int)((Integer.parseInt(args[3]))* 3.333);
877
878 prime();
879 nextProbablePrime();
880
881 arithmetic(order1); // small numbers
882 arithmetic(order3); // Karatsuba / Burnikel-Ziegler range
883 arithmetic(order4); // Toom-Cook range
884
885 divideAndRemainder(order1); // small numbers
886 divideAndRemainder(order3); // Karatsuba / Burnikel-Ziegler range
887 divideAndRemainder(order4); // Toom-Cook range
888
889 pow(order1);
890 pow(order3);
891 pow(order4);
892
893 square(ORDER_MEDIUM);
894 square(ORDER_KARATSUBA_SQUARE);
895 square(ORDER_TOOM_COOK_SQUARE);
896
897 bitCount();
898 bitLength();
899 bitOps(order1);
900 bitwise(order1);
901
902 shift(order1);
903
904 byteArrayConv(order1);
905
906 modInv(order1); // small numbers
907 modInv(order3); // Karatsuba / Burnikel-Ziegler range
908 modInv(order4); // Toom-Cook range
909
910 modExp(order1, order2);
911 modExp2(order1);
912
913 stringConv();
914 serialize();
915
916 multiplyLarge();
917 squareLarge();
918
919 if (failure)
920 throw new RuntimeException("Failure in BigIntegerTest.");
921 }
922
923 /*
924 * Get a random or boundary-case number. This is designed to provide
925 * a lot of numbers that will find failure points, such as max sized
926 * numbers, empty BigIntegers, etc.
927 *
928 * If order is less than 2, order is changed to 2.
929 */
930 private static BigInteger fetchNumber(int order) {
931 boolean negative = rnd.nextBoolean();
932 int numType = rnd.nextInt(7);
933 BigInteger result = null;
934 if (order < 2) order = 2;
935
936 switch (numType) {
937 case 0: // Empty
938 result = BigInteger.ZERO;
939 break;
940
941 case 1: // One
942 result = BigInteger.ONE;
943 break;
944
945 case 2: // All bits set in number
946 int numBytes = (order+7)/8;
947 byte[] fullBits = new byte[numBytes];
948 for(int i=0; i<numBytes; i++)
949 fullBits[i] = (byte)0xff;
950 int excessBits = 8*numBytes - order;
951 fullBits[0] &= (1 << (8-excessBits)) - 1;
952 result = new BigInteger(1, fullBits);
953 break;
954
955 case 3: // One bit in number
956 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
957 break;
958
959 case 4: // Random bit density
960 int iterations = rnd.nextInt(order-1);
961 result = BigInteger.ONE.shiftLeft(rnd.nextInt(order));
962 for(int i=0; i<iterations; i++) {
963 BigInteger temp = BigInteger.ONE.shiftLeft(
964 rnd.nextInt(order));
965 result = result.or(temp);
966 }
967 break;
968 case 5: // Runs of consecutive ones and zeros
969 result = ZERO;
970 int remaining = order;
971 int bit = rnd.nextInt(2);
972 while (remaining > 0) {
973 int runLength = Math.min(remaining, rnd.nextInt(order));
974 result = result.shiftLeft(runLength);
975 if (bit > 0)
976 result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
977 remaining -= runLength;
978 bit = 1 - bit;
979 }
980 break;
981
982 default: // random bits
983 result = new BigInteger(order, rnd);
984 }
985
986 if (negative)
987 result = result.negate();
988
989 return result;
990 }
991
992 static void report(String testName, int failCount) {
993 System.err.println(testName+": " +
994 (failCount==0 ? "Passed":"Failed("+failCount+")"));
995 if (failCount > 0)
996 failure = true;
997 }
998 }
|