1 /*
2 * Copyright (c) 1998, 2017, 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 * @library /test/lib
27 * @build jdk.test.lib.RandomFactory
28 * @run main BigIntegerTest
29 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027
30 * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed)
31 * @run main/timeout=400 BigIntegerTest
32 * @author madbot
33 * @key randomness
34 */
35
36 import java.io.File;
37 import java.io.FileInputStream;
38 import java.io.FileOutputStream;
39 import java.io.ObjectInputStream;
40 import java.io.ObjectOutputStream;
41 import java.math.BigDecimal;
42 import java.math.BigInteger;
43 import java.util.Random;
44 import java.util.function.ToIntFunction;
45 import java.util.stream.Collectors;
46 import java.util.stream.DoubleStream;
47 import java.util.stream.IntStream;
48 import java.util.stream.LongStream;
49 import java.util.stream.Stream;
50 import jdk.test.lib.RandomFactory;
51
52 /**
53 * This is a simple test class created to ensure that the results
54 * generated by BigInteger adhere to certain identities. Passing
55 * this test is a strong assurance that the BigInteger operations
56 * are working correctly.
57 *
58 * Four arguments may be specified which give the number of
59 * decimal digits you desire in the four batches of test numbers.
60 *
61 * The tests are performed on arrays of random numbers which are
62 * generated by a Random class as well as special cases which
63 * throw in boundary numbers such as 0, 1, maximum sized, etc.
64 *
65 */
66 public class BigIntegerTest {
67 //
68 // Bit large number thresholds based on the int thresholds
69 // defined in BigInteger itself:
70 //
71 // KARATSUBA_THRESHOLD = 80 ints = 2560 bits
72 // TOOM_COOK_THRESHOLD = 240 ints = 7680 bits
73 // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits
74 // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits
75 //
76 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits
77 //
78 // BURNIKEL_ZIEGLER_THRESHOLD = 80 ints = 2560 bits
79 //
80 static final int BITS_KARATSUBA = 2560;
81 static final int BITS_TOOM_COOK = 7680;
82 static final int BITS_KARATSUBA_SQUARE = 4096;
83 static final int BITS_TOOM_COOK_SQUARE = 6912;
84 static final int BITS_SCHOENHAGE_BASE = 640;
85 static final int BITS_BURNIKEL_ZIEGLER = 2560;
86 static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280;
87
88 static final int ORDER_SMALL = 60;
89 static final int ORDER_MEDIUM = 100;
90 // #bits for testing Karatsuba
91 static final int ORDER_KARATSUBA = 2760;
92 // #bits for testing Toom-Cook and Burnikel-Ziegler
93 static final int ORDER_TOOM_COOK = 8000;
94 // #bits for testing Karatsuba squaring
95 static final int ORDER_KARATSUBA_SQUARE = 4200;
96 // #bits for testing Toom-Cook squaring
97 static final int ORDER_TOOM_COOK_SQUARE = 7000;
98
99 static final int SIZE = 1000; // numbers per batch
100
101 private static Random random = RandomFactory.getRandom();
102
103 static boolean failure = false;
104
105 public static void constructor() {
106 int failCount = 0;
107
108 // --- guard condition tests for array indexing ---
109
110 int arrayLength = 23;
111 int halfLength = arrayLength/2;
112 byte[] array = new byte[arrayLength];
113 random.nextBytes(array);
114
115 int[][] offLen = new int[][] { // offset, length, num exceptions
116 {-1, arrayLength, 1}, // negative offset
117 {0, arrayLength, 0}, // OK
118 {1, arrayLength, 1}, // length overflow
119 {arrayLength - 1, 1, 0}, // OK
120 {arrayLength, 1, 1}, // offset overflow
121 {0, -1, 1}, // negative length
122 {halfLength, arrayLength - halfLength + 1, 1} // length overflow
123 };
124
125 // two's complement
126 for (int[] ol : offLen) {
127 int numExceptions = 0;
128 try {
129 BigInteger bi = new BigInteger(array, ol[0], ol[1]);
130 } catch (IndexOutOfBoundsException e) {
131 numExceptions++;
132 }
133 if (numExceptions != ol[2]) {
134 System.err.println("IndexOutOfBoundsException did not occur for "
135 + " two's complement constructor with parameters offset "
136 + ol[0] + " and length " + ol[1]);
137 failCount++;
138 }
139 }
140
141 // sign-magnitude
142 for (int[] ol : offLen) {
143 int numExceptions = 0;
144 try {
145 BigInteger bi = new BigInteger(1, array, ol[0], ol[1]);
146 } catch (IndexOutOfBoundsException e) {
147 numExceptions++;
148 }
149 if (numExceptions != ol[2]) {
150 System.err.println("IndexOutOfBoundsException did not occur for "
151 + " sign-magnitude constructor with parameters offset "
152 + ol[0] + " and length " + ol[1]);
153 failCount++;
154 }
155 }
156
157 // --- tests for creation of zero-valued BigIntegers ---
158
159 byte[] magZeroLength = new byte[0];
160 for (int signum = -1; signum <= 1; signum++) {
161 BigInteger bi = new BigInteger(signum, magZeroLength);
162 if (bi.compareTo(BigInteger.ZERO) != 0) {
163 System.err.println("A: Zero length BigInteger != 0 for signum " + signum);
164 failCount++;
165 }
166 }
167
168 for (int signum = -1; signum <= 1; signum++) {
169 BigInteger bi = new BigInteger(signum, magZeroLength, 0, 0);
170 if (bi.compareTo(BigInteger.ZERO) != 0) {
171 System.err.println("B: Zero length BigInteger != 0 for signum " + signum);
172 failCount++;
173 }
174 }
175
176 byte[] magNonZeroLength = new byte[42];
177 random.nextBytes(magNonZeroLength);
178 for (int signum = -1; signum <= 1; signum++) {
179 BigInteger bi = new BigInteger(signum, magNonZeroLength, 0, 0);
180 if (bi.compareTo(BigInteger.ZERO) != 0) {
181 System.err.println("C: Zero length BigInteger != 0 for signum " + signum);
182 failCount++;
183 }
184 }
185
186 // --- tests for accurate creation of non-zero BigIntegers ---
187
188 for (int i = 0; i < SIZE; i++) {
189 // create reference value via a different code path from those tested
190 BigInteger reference = new BigInteger(2 + random.nextInt(336), 4, random);
191
192 byte[] refArray = reference.toByteArray();
193 int refLen = refArray.length;
194 int factor = random.nextInt(5);
195 int objLen = refArray.length + factor*random.nextInt(refArray.length) + 1;
196 int offset = random.nextInt(objLen - refLen);
197 byte[] objArray = new byte[objLen];
198 System.arraycopy(refArray, 0, objArray, offset, refLen);
199
200 BigInteger twosComp = new BigInteger(objArray, offset, refLen);
201 if (twosComp.compareTo(reference) != 0) {
202 System.err.println("Two's-complement BigInteger not equal for offset " +
203 offset + " and length " + refLen);
204 failCount++;
205 }
206
207 boolean isNegative = random.nextBoolean();
208 BigInteger signMag = new BigInteger(isNegative ? -1 : 1, objArray, offset, refLen);
209 if (signMag.compareTo(isNegative ? reference.negate() : reference) != 0) {
210 System.err.println("Sign-magnitude BigInteger not equal for offset " +
211 offset + " and length " + refLen);
212 failCount++;
213 }
214 }
215
216 report("Constructor", failCount);
217 }
218
219 public static void pow(int order) {
220 int failCount1 = 0;
221
222 for (int i=0; i<SIZE; i++) {
223 // Test identity x^power == x*x*x ... *x
224 int power = random.nextInt(6) + 2;
225 BigInteger x = fetchNumber(order);
226 BigInteger y = x.pow(power);
227 BigInteger z = x;
228
229 for (int j=1; j<power; j++)
230 z = z.multiply(x);
231
232 if (!y.equals(z))
233 failCount1++;
234 }
235 report("pow for " + order + " bits", failCount1);
236 }
237
238 public static void square(int order) {
239 int failCount1 = 0;
240
241 for (int i=0; i<SIZE; i++) {
242 // Test identity x^2 == x*x
243 BigInteger x = fetchNumber(order);
244 BigInteger xx = x.multiply(x);
245 BigInteger x2 = x.pow(2);
246
247 if (!x2.equals(xx))
248 failCount1++;
249 }
250 report("square for " + order + " bits", failCount1);
251 }
252
253 private static void printErr(String msg) {
254 System.err.println(msg);
255 }
256
257 private static int checkResult(BigInteger expected, BigInteger actual,
258 String failureMessage) {
259 if (expected.compareTo(actual) != 0) {
260 printErr(failureMessage + " - expected: " + expected
261 + ", actual: " + actual);
262 return 1;
263 }
264 return 0;
265 }
266
267 private static void squareRootSmall() {
268 int failCount = 0;
269
270 // A negative value should cause an exception.
271 BigInteger n = BigInteger.ONE.negate();
272 BigInteger s;
273 try {
274 s = n.sqrt();
275 // If sqrt() does not throw an exception that is a failure.
276 failCount++;
277 printErr("sqrt() of negative number did not throw an exception");
278 } catch (ArithmeticException expected) {
279 // A negative value should cause an exception and is not a failure.
280 }
281
282 // A zero value should return BigInteger.ZERO.
283 failCount += checkResult(BigInteger.ZERO, BigInteger.ZERO.sqrt(),
284 "sqrt(0) != BigInteger.ZERO");
285
286 // 1 <= value < 4 should return BigInteger.ONE.
287 long[] smalls = new long[] {1, 2, 3};
288 for (long small : smalls) {
289 failCount += checkResult(BigInteger.ONE,
290 BigInteger.valueOf(small).sqrt(), "sqrt("+small+") != 1");
291 }
292
293 report("squareRootSmall", failCount);
294 }
295
296 public static void squareRoot() {
297 squareRootSmall();
298
299 ToIntFunction<BigInteger> f = (n) -> {
300 int failCount = 0;
301
302 // square root of n^2 -> n
303 BigInteger n2 = n.pow(2);
304 failCount += checkResult(n, n2.sqrt(), "sqrt() n^2 -> n");
305
306 // square root of n^2 + 1 -> n
307 BigInteger n2up = n2.add(BigInteger.ONE);
308 failCount += checkResult(n, n2up.sqrt(), "sqrt() n^2 + 1 -> n");
309
310 // square root of (n + 1)^2 - 1 -> n
311 BigInteger up =
312 n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
313 failCount += checkResult(n, up.sqrt(), "sqrt() (n + 1)^2 - 1 -> n");
314
315 // sqrt(n)^2 <= n
316 BigInteger s = n.sqrt();
317 if (s.multiply(s).compareTo(n) > 0) {
318 failCount++;
319 printErr("sqrt(n)^2 > n for n = " + n);
320 }
321
322 // (sqrt(n) + 1)^2 > n
323 if (s.add(BigInteger.ONE).pow(2).compareTo(n) <= 0) {
324 failCount++;
325 printErr("(sqrt(n) + 1)^2 <= n for n = " + n);
326 }
327
328 return failCount;
329 };
330
331 Stream.Builder<BigInteger> sb = Stream.builder();
332 int maxExponent = Double.MAX_EXPONENT + 1;
333 for (int i = 1; i <= maxExponent; i++) {
334 BigInteger p2 = BigInteger.ONE.shiftLeft(i);
335 sb.add(p2.subtract(BigInteger.ONE));
336 sb.add(p2);
337 sb.add(p2.add(BigInteger.ONE));
338 }
339 sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger());
340 sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger().add(BigInteger.ONE));
341 report("squareRoot for 2^N and 2^N - 1, 1 <= N <= Double.MAX_EXPONENT",
342 sb.build().collect(Collectors.summingInt(f)));
343
344 IntStream ints = random.ints(SIZE, 4, Integer.MAX_VALUE);
345 report("squareRoot for int", ints.mapToObj(x ->
346 BigInteger.valueOf(x)).collect(Collectors.summingInt(f)));
347
348 LongStream longs = random.longs(SIZE, (long)Integer.MAX_VALUE + 1L,
349 Long.MAX_VALUE);
350 report("squareRoot for long", longs.mapToObj(x ->
351 BigInteger.valueOf(x)).collect(Collectors.summingInt(f)));
352
353 DoubleStream doubles = random.doubles(SIZE,
354 (double) Long.MAX_VALUE + 1.0, Math.sqrt(Double.MAX_VALUE));
355 report("squareRoot for double", doubles.mapToObj(x ->
356 BigDecimal.valueOf(x).toBigInteger()).collect(Collectors.summingInt(f)));
357 }
358
359 public static void squareRootAndRemainder() {
360 ToIntFunction<BigInteger> g = (n) -> {
361 int failCount = 0;
362 BigInteger n2 = n.pow(2);
363
364 // square root of n^2 -> n
365 BigInteger[] actual = n2.sqrtAndRemainder();
366 failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");
367 failCount += checkResult(BigInteger.ZERO, actual[1],
368 "sqrtAndRemainder()[1]");
369
370 // square root of n^2 + 1 -> n
371 BigInteger n2up = n2.add(BigInteger.ONE);
372 actual = n2up.sqrtAndRemainder();
373 failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");
374 failCount += checkResult(BigInteger.ONE, actual[1],
375 "sqrtAndRemainder()[1]");
376
377 // square root of (n + 1)^2 - 1 -> n
378 BigInteger up =
379 n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
380 actual = up.sqrtAndRemainder();
381 failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");
382 BigInteger r = up.subtract(n2);
383 failCount += checkResult(r, actual[1], "sqrtAndRemainder()[1]");
384
385 return failCount;
386 };
387
388 IntStream bits = random.ints(SIZE, 3, Short.MAX_VALUE);
389 report("sqrtAndRemainder", bits.mapToObj(x ->
390 BigInteger.valueOf(x)).collect(Collectors.summingInt(g)));
391 }
392
393 public static void arithmetic(int order) {
394 int failCount = 0;
395
396 for (int i=0; i<SIZE; i++) {
397 BigInteger x = fetchNumber(order);
398 while(x.compareTo(BigInteger.ZERO) != 1)
399 x = fetchNumber(order);
400 BigInteger y = fetchNumber(order/2);
401 while(x.compareTo(y) == -1)
402 y = fetchNumber(order/2);
403 if (y.equals(BigInteger.ZERO))
404 y = y.add(BigInteger.ONE);
405
406 // Test identity ((x/y))*y + x%y - x == 0
407 // using separate divide() and remainder()
408 BigInteger baz = x.divide(y);
409 baz = baz.multiply(y);
410 baz = baz.add(x.remainder(y));
411 baz = baz.subtract(x);
412 if (!baz.equals(BigInteger.ZERO))
413 failCount++;
414 }
415 report("Arithmetic I for " + order + " bits", failCount);
416
417 failCount = 0;
418 for (int i=0; i<100; i++) {
419 BigInteger x = fetchNumber(order);
420 while(x.compareTo(BigInteger.ZERO) != 1)
421 x = fetchNumber(order);
422 BigInteger y = fetchNumber(order/2);
423 while(x.compareTo(y) == -1)
424 y = fetchNumber(order/2);
425 if (y.equals(BigInteger.ZERO))
426 y = y.add(BigInteger.ONE);
427
428 // Test identity ((x/y))*y + x%y - x == 0
429 // using divideAndRemainder()
430 BigInteger baz[] = x.divideAndRemainder(y);
431 baz[0] = baz[0].multiply(y);
432 baz[0] = baz[0].add(baz[1]);
433 baz[0] = baz[0].subtract(x);
434 if (!baz[0].equals(BigInteger.ZERO))
435 failCount++;
436 }
437 report("Arithmetic II for " + order + " bits", failCount);
438 }
439
440 /**
441 * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.
442 * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
443 * construct two factors each with a mag array one element shorter than the
444 * threshold, and with the most significant bit set and the rest of the bits
445 * random. Each of these numbers will therefore be below the threshold but
446 * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
447 * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
448 * identity
449 * <pre>
450 * (u << a)*(v << b) = (u*v) << (a + b)
451 * </pre>
452 * For Karatsuba multiplication, the right hand expression will be evaluated
453 * using the standard naive algorithm, and the left hand expression using
454 * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
455 * hand expression will be evaluated using Karatsuba multiplication, and the
456 * left hand expression using 3-way Toom-Cook multiplication.
457 */
458 public static void multiplyLarge() {
459 int failCount = 0;
460
461 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
462 for (int i=0; i<SIZE; i++) {
463 BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
464 BigInteger u = base.add(x);
465 int a = 1 + random.nextInt(31);
466 BigInteger w = u.shiftLeft(a);
467
468 BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
469 BigInteger v = base.add(y);
470 int b = 1 + random.nextInt(32);
471 BigInteger z = v.shiftLeft(b);
472
473 BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
474 BigInteger karatsubaMultiplyResult = w.multiply(z);
475
476 if (!multiplyResult.equals(karatsubaMultiplyResult)) {
477 failCount++;
478 }
479 }
480
481 report("multiplyLarge Karatsuba", failCount);
482
483 failCount = 0;
484 base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
485 for (int i=0; i<SIZE; i++) {
486 BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
487 BigInteger u = base.add(x);
488 BigInteger u2 = u.shiftLeft(1);
489 BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
490 BigInteger v = base.add(y);
491 BigInteger v2 = v.shiftLeft(1);
492
493 BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
494 BigInteger toomCookMultiplyResult = u2.multiply(v2);
495
496 if (!multiplyResult.equals(toomCookMultiplyResult)) {
497 failCount++;
498 }
499 }
500
501 report("multiplyLarge Toom-Cook", failCount);
502 }
503
504 /**
505 * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
506 * This test is analogous to {@link AbstractMethodError#multiplyLarge}
507 * with both factors being equal. The squaring methods will not be tested
508 * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
509 * the parameter is the same instance on which the method is being invoked
510 * and calls <code>square()</code> accordingly.
511 */
512 public static void squareLarge() {
513 int failCount = 0;
514
515 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
516 for (int i=0; i<SIZE; i++) {
517 BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
518 BigInteger u = base.add(x);
519 int a = 1 + random.nextInt(31);
520 BigInteger w = u.shiftLeft(a);
521
522 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
523 BigInteger karatsubaSquareResult = w.multiply(w);
524
525 if (!squareResult.equals(karatsubaSquareResult)) {
526 failCount++;
527 }
528 }
529
530 report("squareLarge Karatsuba", failCount);
531
532 failCount = 0;
533 base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
534 for (int i=0; i<SIZE; i++) {
535 BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
536 BigInteger u = base.add(x);
537 int a = 1 + random.nextInt(31);
538 BigInteger w = u.shiftLeft(a);
539
540 BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
541 BigInteger toomCookSquareResult = w.multiply(w);
542
543 if (!squareResult.equals(toomCookSquareResult)) {
544 failCount++;
545 }
546 }
547
548 report("squareLarge Toom-Cook", failCount);
549 }
550
551 /**
552 * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division
553 * algorithm is used when each of the dividend and the divisor has at least
554 * a specified number of ints in its representation. This test is based on
555 * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
556 * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
557 * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
558 * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test
559 * ensures that {@code v} is just under the B-Z threshold, that {@code z} is
560 * over the threshold and {@code w} is much larger than {@code z}. This
561 * implies that {@code u/v} uses the standard division algorithm and
562 * {@code w/z} uses the B-Z algorithm. The results of the two algorithms
563 * are then compared using the observation described in the foregoing and
564 * if they are not equal a failure is logged.
565 */
566 public static void divideLarge() {
567 int failCount = 0;
568
569 BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33);
570 for (int i=0; i<SIZE; i++) {
571 BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, random);
572 BigInteger v = base.add(addend);
573
574 BigInteger u = v.multiply(BigInteger.valueOf(2 + random.nextInt(Short.MAX_VALUE - 1)));
575
576 if(random.nextBoolean()) {
577 u = u.negate();
578 }
579 if(random.nextBoolean()) {
580 v = v.negate();
581 }
582
583 int a = BITS_BURNIKEL_ZIEGLER_OFFSET + random.nextInt(16);
584 int b = 1 + random.nextInt(16);
585 BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a));
586 BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b));
587
588 BigInteger[] divideResult = u.divideAndRemainder(v);
589 divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b));
590 divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b));
591 BigInteger[] bzResult = w.divideAndRemainder(z);
592
593 if (divideResult[0].compareTo(bzResult[0]) != 0 ||
594 divideResult[1].compareTo(bzResult[1]) != 0) {
595 failCount++;
596 }
597 }
598
599 report("divideLarge", failCount);
600 }
601
602 public static void bitCount() {
603 int failCount = 0;
604
605 for (int i=0; i<SIZE*10; i++) {
606 int x = random.nextInt();
607 BigInteger bigX = BigInteger.valueOf((long)x);
608 int bit = (x < 0 ? 0 : 1);
609 int tmp = x, bitCount = 0;
610 for (int j=0; j<32; j++) {
611 bitCount += ((tmp & 1) == bit ? 1 : 0);
612 tmp >>= 1;
613 }
614
615 if (bigX.bitCount() != bitCount) {
616 //System.err.println(x+": "+bitCount+", "+bigX.bitCount());
617 failCount++;
618 }
619 }
620 report("Bit Count", failCount);
621 }
622
623 public static void bitLength() {
624 int failCount = 0;
625
626 for (int i=0; i<SIZE*10; i++) {
627 int x = random.nextInt();
628 BigInteger bigX = BigInteger.valueOf((long)x);
629 int signBit = (x < 0 ? 0x80000000 : 0);
630 int tmp = x, bitLength, j;
631 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
632 tmp <<= 1;
633 bitLength = 32 - j;
634
635 if (bigX.bitLength() != bitLength) {
636 //System.err.println(x+": "+bitLength+", "+bigX.bitLength());
637 failCount++;
638 }
639 }
640
641 report("BitLength", failCount);
642 }
643
644 public static void bitOps(int order) {
645 int failCount1 = 0, failCount2 = 0, failCount3 = 0;
646
647 for (int i=0; i<SIZE*5; i++) {
648 BigInteger x = fetchNumber(order);
649 BigInteger y;
650
651 // Test setBit and clearBit (and testBit)
652 if (x.signum() < 0) {
653 y = BigInteger.valueOf(-1);
654 for (int j=0; j<x.bitLength(); j++)
655 if (!x.testBit(j))
656 y = y.clearBit(j);
657 } else {
658 y = BigInteger.ZERO;
659 for (int j=0; j<x.bitLength(); j++)
660 if (x.testBit(j))
661 y = y.setBit(j);
662 }
663 if (!x.equals(y))
664 failCount1++;
665
666 // Test flipBit (and testBit)
667 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
668 for (int j=0; j<x.bitLength(); j++)
669 if (x.signum()<0 ^ x.testBit(j))
670 y = y.flipBit(j);
671 if (!x.equals(y))
672 failCount2++;
673 }
674 report("clearBit/testBit for " + order + " bits", failCount1);
675 report("flipBit/testBit for " + order + " bits", failCount2);
676
677 for (int i=0; i<SIZE*5; i++) {
678 BigInteger x = fetchNumber(order);
679
680 // Test getLowestSetBit()
681 int k = x.getLowestSetBit();
682 if (x.signum() == 0) {
683 if (k != -1)
684 failCount3++;
685 } else {
686 BigInteger z = x.and(x.negate());
687 int j;
688 for (j=0; j<z.bitLength() && !z.testBit(j); j++)
689 ;
690 if (k != j)
691 failCount3++;
692 }
693 }
694 report("getLowestSetBit for " + order + " bits", failCount3);
695 }
696
697 public static void bitwise(int order) {
698
699 // Test identity x^y == x|y &~ x&y
700 int failCount = 0;
701 for (int i=0; i<SIZE; i++) {
702 BigInteger x = fetchNumber(order);
703 BigInteger y = fetchNumber(order);
704 BigInteger z = x.xor(y);
705 BigInteger w = x.or(y).andNot(x.and(y));
706 if (!z.equals(w))
707 failCount++;
708 }
709 report("Logic (^ | & ~) for " + order + " bits", failCount);
710
711 // Test identity x &~ y == ~(~x | y)
712 failCount = 0;
713 for (int i=0; i<SIZE; i++) {
714 BigInteger x = fetchNumber(order);
715 BigInteger y = fetchNumber(order);
716 BigInteger z = x.andNot(y);
717 BigInteger w = x.not().or(y).not();
718 if (!z.equals(w))
719 failCount++;
720 }
721 report("Logic (&~ | ~) for " + order + " bits", failCount);
722 }
723
724 public static void shift(int order) {
725 int failCount1 = 0;
726 int failCount2 = 0;
727 int failCount3 = 0;
728
729 for (int i=0; i<100; i++) {
730 BigInteger x = fetchNumber(order);
731 int n = Math.abs(random.nextInt()%200);
732
733 if (!x.shiftLeft(n).equals
734 (x.multiply(BigInteger.valueOf(2L).pow(n))))
735 failCount1++;
736
737 BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));
738 BigInteger z = (x.signum()<0 && y[1].signum()!=0
739 ? y[0].subtract(BigInteger.ONE)
740 : y[0]);
741
742 BigInteger b = x.shiftRight(n);
743
744 if (!b.equals(z)) {
745 System.err.println("Input is "+x.toString(2));
746 System.err.println("shift is "+n);
747
748 System.err.println("Divided "+z.toString(2));
749 System.err.println("Shifted is "+b.toString(2));
750 if (b.toString().equals(z.toString()))
751 System.err.println("Houston, we have a problem.");
752 failCount2++;
753 }
754
755 if (!x.shiftLeft(n).shiftRight(n).equals(x))
756 failCount3++;
757 }
758 report("baz shiftLeft for " + order + " bits", failCount1);
759 report("baz shiftRight for " + order + " bits", failCount2);
760 report("baz shiftLeft/Right for " + order + " bits", failCount3);
761 }
762
763 public static void divideAndRemainder(int order) {
764 int failCount1 = 0;
765
766 for (int i=0; i<SIZE; i++) {
767 BigInteger x = fetchNumber(order).abs();
768 while(x.compareTo(BigInteger.valueOf(3L)) != 1)
769 x = fetchNumber(order).abs();
770 BigInteger z = x.divide(BigInteger.valueOf(2L));
771 BigInteger y[] = x.divideAndRemainder(x);
772 if (!y[0].equals(BigInteger.ONE)) {
773 failCount1++;
774 System.err.println("fail1 x :"+x);
775 System.err.println(" y :"+y);
776 }
777 else if (!y[1].equals(BigInteger.ZERO)) {
778 failCount1++;
779 System.err.println("fail2 x :"+x);
780 System.err.println(" y :"+y);
781 }
782
783 y = x.divideAndRemainder(z);
784 if (!y[0].equals(BigInteger.valueOf(2))) {
785 failCount1++;
786 System.err.println("fail3 x :"+x);
787 System.err.println(" y :"+y);
788 }
789 }
790 report("divideAndRemainder for " + order + " bits", failCount1);
791 }
792
793 public static void stringConv() {
794 int failCount = 0;
795
796 // Generic string conversion.
797 for (int i=0; i<100; i++) {
798 byte xBytes[] = new byte[Math.abs(random.nextInt())%100+1];
799 random.nextBytes(xBytes);
800 BigInteger x = new BigInteger(xBytes);
801
802 for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
803 String result = x.toString(radix);
804 BigInteger test = new BigInteger(result, radix);
805 if (!test.equals(x)) {
806 failCount++;
807 System.err.println("BigInteger toString: "+x);
808 System.err.println("Test: "+test);
809 System.err.println(radix);
810 }
811 }
812 }
813
814 // String conversion straddling the Schoenhage algorithm crossover
815 // threshold, and at twice and four times the threshold.
816 for (int k = 0; k <= 2; k++) {
817 int factor = 1 << k;
818 int upper = factor * BITS_SCHOENHAGE_BASE + 33;
819 int lower = upper - 35;
820
821 for (int bits = upper; bits >= lower; bits--) {
822 for (int i = 0; i < 50; i++) {
823 BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, random));
824
825 for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
826 String result = x.toString(radix);
827 BigInteger test = new BigInteger(result, radix);
828 if (!test.equals(x)) {
829 failCount++;
830 System.err.println("BigInteger toString: " + x);
831 System.err.println("Test: " + test);
832 System.err.println(radix);
833 }
834 }
835 }
836 }
837 }
838
839 report("String Conversion", failCount);
840 }
841
842 public static void byteArrayConv(int order) {
843 int failCount = 0;
844
845 for (int i=0; i<SIZE; i++) {
846 BigInteger x = fetchNumber(order);
847 while (x.equals(BigInteger.ZERO))
848 x = fetchNumber(order);
849 BigInteger y = new BigInteger(x.toByteArray());
850 if (!x.equals(y)) {
851 failCount++;
852 System.err.println("orig is "+x);
853 System.err.println("new is "+y);
854 }
855 }
856 report("Array Conversion for " + order + " bits", failCount);
857 }
858
859 public static void modInv(int order) {
860 int failCount = 0, successCount = 0, nonInvCount = 0;
861
862 for (int i=0; i<SIZE; i++) {
863 BigInteger x = fetchNumber(order);
864 while(x.equals(BigInteger.ZERO))
865 x = fetchNumber(order);
866 BigInteger m = fetchNumber(order).abs();
867 while(m.compareTo(BigInteger.ONE) != 1)
868 m = fetchNumber(order).abs();
869
870 try {
871 BigInteger inv = x.modInverse(m);
872 BigInteger prod = inv.multiply(x).remainder(m);
873
874 if (prod.signum() == -1)
875 prod = prod.add(m);
876
877 if (prod.equals(BigInteger.ONE))
878 successCount++;
879 else
880 failCount++;
881 } catch(ArithmeticException e) {
882 nonInvCount++;
883 }
884 }
885 report("Modular Inverse for " + order + " bits", failCount);
886 }
887
888 public static void modExp(int order1, int order2) {
889 int failCount = 0;
890
891 for (int i=0; i<SIZE/10; i++) {
892 BigInteger m = fetchNumber(order1).abs();
893 while(m.compareTo(BigInteger.ONE) != 1)
894 m = fetchNumber(order1).abs();
895 BigInteger base = fetchNumber(order2);
896 BigInteger exp = fetchNumber(8).abs();
897
898 BigInteger z = base.modPow(exp, m);
899 BigInteger w = base.pow(exp.intValue()).mod(m);
900 if (!z.equals(w)) {
901 System.err.println("z is "+z);
902 System.err.println("w is "+w);
903 System.err.println("mod is "+m);
904 System.err.println("base is "+base);
905 System.err.println("exp is "+exp);
906 failCount++;
907 }
908 }
909 report("Exponentiation I for " + order1 + " and " +
910 order2 + " bits", failCount);
911 }
912
913 // This test is based on Fermat's theorem
914 // which is not ideal because base must not be multiple of modulus
915 // and modulus must be a prime or pseudoprime (Carmichael number)
916 public static void modExp2(int order) {
917 int failCount = 0;
918
919 for (int i=0; i<10; i++) {
920 BigInteger m = new BigInteger(100, 5, random);
921 while(m.compareTo(BigInteger.ONE) != 1)
922 m = new BigInteger(100, 5, random);
923 BigInteger exp = m.subtract(BigInteger.ONE);
924 BigInteger base = fetchNumber(order).abs();
925 while(base.compareTo(m) != -1)
926 base = fetchNumber(order).abs();
927 while(base.equals(BigInteger.ZERO))
928 base = fetchNumber(order).abs();
929
930 BigInteger one = base.modPow(exp, m);
931 if (!one.equals(BigInteger.ONE)) {
932 System.err.println("m is "+m);
933 System.err.println("base is "+base);
934 System.err.println("exp is "+exp);
935 failCount++;
936 }
937 }
938 report("Exponentiation II for " + order + " bits", failCount);
939 }
940
941 private static final int[] mersenne_powers = {
942 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
943 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
944 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };
945
946 private static final long[] carmichaels = {
947 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
948 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
949 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
950 225593397919L };
951
952 // Note: testing the larger ones takes too long.
953 private static final int NUM_MERSENNES_TO_TEST = 7;
954 // Note: this constant used for computed Carmichaels, not the array above
955 private static final int NUM_CARMICHAELS_TO_TEST = 5;
956
957 private static final String[] customer_primes = {
958 "120000000000000000000000000000000019",
959 "633825300114114700748351603131",
960 "1461501637330902918203684832716283019651637554291",
961 "779626057591079617852292862756047675913380626199",
962 "857591696176672809403750477631580323575362410491",
963 "910409242326391377348778281801166102059139832131",
964 "929857869954035706722619989283358182285540127919",
965 "961301750640481375785983980066592002055764391999",
966 "1267617700951005189537696547196156120148404630231",
967 "1326015641149969955786344600146607663033642528339" };
968
969 private static final BigInteger ZERO = BigInteger.ZERO;
970 private static final BigInteger ONE = BigInteger.ONE;
971 private static final BigInteger TWO = new BigInteger("2");
972 private static final BigInteger SIX = new BigInteger("6");
973 private static final BigInteger TWELVE = new BigInteger("12");
974 private static final BigInteger EIGHTEEN = new BigInteger("18");
975
976 public static void prime() {
977 BigInteger p1, p2, c1;
978 int failCount = 0;
979
980 // Test consistency
981 for(int i=0; i<10; i++) {
982 p1 = BigInteger.probablePrime(100, random);
983 if (!p1.isProbablePrime(100)) {
984 System.err.println("Consistency "+p1.toString(16));
985 failCount++;
986 }
987 }
988
989 // Test some known Mersenne primes (2^n)-1
990 // The array holds the exponents, not the numbers being tested
991 for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) {
992 p1 = new BigInteger("2");
993 p1 = p1.pow(mersenne_powers[i]);
994 p1 = p1.subtract(BigInteger.ONE);
995 if (!p1.isProbablePrime(100)) {
996 System.err.println("Mersenne prime "+i+ " failed.");
997 failCount++;
998 }
999 }
1000
1001 // Test some primes reported by customers as failing in the past
1002 for (int i=0; i<customer_primes.length; i++) {
1003 p1 = new BigInteger(customer_primes[i]);
1004 if (!p1.isProbablePrime(100)) {
1005 System.err.println("Customer prime "+i+ " failed.");
1006 failCount++;
1007 }
1008 }
1009
1010 // Test some known Carmichael numbers.
1011 for (int i=0; i<carmichaels.length; i++) {
1012 c1 = BigInteger.valueOf(carmichaels[i]);
1013 if(c1.isProbablePrime(100)) {
1014 System.err.println("Carmichael "+i+ " reported as prime.");
1015 failCount++;
1016 }
1017 }
1018
1019 // Test some computed Carmichael numbers.
1020 // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if
1021 // each of the factors is prime
1022 int found = 0;
1023 BigInteger f1 = new BigInteger(40, 100, random);
1024 while (found < NUM_CARMICHAELS_TO_TEST) {
1025 BigInteger k = null;
1026 BigInteger f2, f3;
1027 f1 = f1.nextProbablePrime();
1028 BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX);
1029 if (result[1].equals(ZERO)) {
1030 k = result[0];
1031 f2 = k.multiply(TWELVE).add(ONE);
1032 if (f2.isProbablePrime(100)) {
1033 f3 = k.multiply(EIGHTEEN).add(ONE);
1034 if (f3.isProbablePrime(100)) {
1035 c1 = f1.multiply(f2).multiply(f3);
1036 if (c1.isProbablePrime(100)) {
1037 System.err.println("Computed Carmichael "
1038 +c1.toString(16));
1039 failCount++;
1040 }
1041 found++;
1042 }
1043 }
1044 }
1045 f1 = f1.add(TWO);
1046 }
1047
1048 // Test some composites that are products of 2 primes
1049 for (int i=0; i<50; i++) {
1050 p1 = BigInteger.probablePrime(100, random);
1051 p2 = BigInteger.probablePrime(100, random);
1052 c1 = p1.multiply(p2);
1053 if (c1.isProbablePrime(100)) {
1054 System.err.println("Composite failed "+c1.toString(16));
1055 failCount++;
1056 }
1057 }
1058
1059 for (int i=0; i<4; i++) {
1060 p1 = BigInteger.probablePrime(600, random);
1061 p2 = BigInteger.probablePrime(600, random);
1062 c1 = p1.multiply(p2);
1063 if (c1.isProbablePrime(100)) {
1064 System.err.println("Composite failed "+c1.toString(16));
1065 failCount++;
1066 }
1067 }
1068
1069 report("Prime", failCount);
1070 }
1071
1072 private static final long[] primesTo100 = {
1073 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
1074 };
1075
1076 private static final long[] aPrimeSequence = {
1077 1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L,
1078 1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L,
1079 1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L,
1080 1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L,
1081 1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L,
1082 1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L,
1083 1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L,
1084 1999999853L, 1999999861L, 1999999871L, 1999999873
1085 };
1086
1087 public static void nextProbablePrime() throws Exception {
1088 int failCount = 0;
1089 BigInteger p1, p2, p3;
1090 p1 = p2 = p3 = ZERO;
1091
1092 // First test nextProbablePrime on the low range starting at zero
1093 for (int i=0; i<primesTo100.length; i++) {
1094 p1 = p1.nextProbablePrime();
1095 if (p1.longValue() != primesTo100[i]) {
1096 System.err.println("low range primes failed");
1097 System.err.println("p1 is "+p1);
1098 System.err.println("expected "+primesTo100[i]);
1099 failCount++;
1100 }
1101 }
1102
1103 // Test nextProbablePrime on a relatively small, known prime sequence
1104 p1 = BigInteger.valueOf(aPrimeSequence[0]);
1105 for (int i=1; i<aPrimeSequence.length; i++) {
1106 p1 = p1.nextProbablePrime();
1107 if (p1.longValue() != aPrimeSequence[i]) {
1108 System.err.println("prime sequence failed");
1109 failCount++;
1110 }
1111 }
1112
1113 // Next, pick some large primes, use nextProbablePrime to find the
1114 // next one, and make sure there are no primes in between
1115 for (int i=0; i<100; i+=10) {
1116 p1 = BigInteger.probablePrime(50 + i, random);
1117 p2 = p1.add(ONE);
1118 p3 = p1.nextProbablePrime();
1119 while(p2.compareTo(p3) < 0) {
1120 if (p2.isProbablePrime(100)){
1121 System.err.println("nextProbablePrime failed");
1122 System.err.println("along range "+p1.toString(16));
1123 System.err.println("to "+p3.toString(16));
1124 failCount++;
1125 break;
1126 }
1127 p2 = p2.add(ONE);
1128 }
1129 }
1130
1131 report("nextProbablePrime", failCount);
1132 }
1133
1134 public static void serialize() throws Exception {
1135 int failCount = 0;
1136
1137 String bitPatterns[] = {
1138 "ffffffff00000000ffffffff00000000ffffffff00000000",
1139 "ffffffffffffffffffffffff000000000000000000000000",
1140 "ffffffff0000000000000000000000000000000000000000",
1141 "10000000ffffffffffffffffffffffffffffffffffffffff",
1142 "100000000000000000000000000000000000000000000000",
1143 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
1144 "-ffffffff00000000ffffffff00000000ffffffff00000000",
1145 "-ffffffffffffffffffffffff000000000000000000000000",
1146 "-ffffffff0000000000000000000000000000000000000000",
1147 "-10000000ffffffffffffffffffffffffffffffffffffffff",
1148 "-100000000000000000000000000000000000000000000000",
1149 "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1150 };
1151
1152 for(int i = 0; i < bitPatterns.length; i++) {
1153 BigInteger b1 = new BigInteger(bitPatterns[i], 16);
1154 BigInteger b2 = null;
1155
1156 File f = new File("serialtest");
1157
1158 try (FileOutputStream fos = new FileOutputStream(f)) {
1159 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1160 oos.writeObject(b1);
1161 oos.flush();
1162 }
1163
1164 try (FileInputStream fis = new FileInputStream(f);
1165 ObjectInputStream ois = new ObjectInputStream(fis))
1166 {
1167 b2 = (BigInteger)ois.readObject();
1168 }
1169
1170 if (!b1.equals(b2) ||
1171 !b1.equals(b1.or(b2))) {
1172 failCount++;
1173 System.err.println("Serialized failed for hex " +
1174 b1.toString(16));
1175 }
1176 }
1177 f.delete();
1178 }
1179
1180 for(int i=0; i<10; i++) {
1181 BigInteger b1 = fetchNumber(random.nextInt(100));
1182 BigInteger b2 = null;
1183 File f = new File("serialtest");
1184 try (FileOutputStream fos = new FileOutputStream(f)) {
1185 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1186 oos.writeObject(b1);
1187 oos.flush();
1188 }
1189
1190 try (FileInputStream fis = new FileInputStream(f);
1191 ObjectInputStream ois = new ObjectInputStream(fis))
1192 {
1193 b2 = (BigInteger)ois.readObject();
1194 }
1195 }
1196
1197 if (!b1.equals(b2) ||
1198 !b1.equals(b1.or(b2)))
1199 failCount++;
1200 f.delete();
1201 }
1202
1203 report("Serialize", failCount);
1204 }
1205
1206 /**
1207 * Main to interpret arguments and run several tests.
1208 *
1209 * Up to three arguments may be given to specify the SIZE of BigIntegers
1210 * used for call parameters 1, 2, and 3. The SIZE is interpreted as
1211 * the maximum number of decimal digits that the parameters will have.
1212 *
1213 */
1214 public static void main(String[] args) throws Exception {
1215 // Some variables for sizing test numbers in bits
1216 int order1 = ORDER_MEDIUM;
1217 int order2 = ORDER_SMALL;
1218 int order3 = ORDER_KARATSUBA;
1219 int order4 = ORDER_TOOM_COOK;
1220
1221 if (args.length >0)
1222 order1 = (int)((Integer.parseInt(args[0]))* 3.333);
1223 if (args.length >1)
1224 order2 = (int)((Integer.parseInt(args[1]))* 3.333);
1225 if (args.length >2)
1226 order3 = (int)((Integer.parseInt(args[2]))* 3.333);
1227 if (args.length >3)
1228 order4 = (int)((Integer.parseInt(args[3]))* 3.333);
1229
1230 constructor();
1231
1232 prime();
1233 nextProbablePrime();
1234
1235 arithmetic(order1); // small numbers
1236 arithmetic(order3); // Karatsuba range
1237 arithmetic(order4); // Toom-Cook / Burnikel-Ziegler range
1238
1239 divideAndRemainder(order1); // small numbers
1240 divideAndRemainder(order3); // Karatsuba range
1241 divideAndRemainder(order4); // Toom-Cook / Burnikel-Ziegler range
1242
1243 pow(order1);
1244 pow(order3);
1245 pow(order4);
1246
1247 square(ORDER_MEDIUM);
1248 square(ORDER_KARATSUBA_SQUARE);
1249 square(ORDER_TOOM_COOK_SQUARE);
1250
1251 squareRoot();
1252 squareRootAndRemainder();
1253
1254 bitCount();
1255 bitLength();
1256 bitOps(order1);
1257 bitwise(order1);
1258
1259 shift(order1);
1260
1261 byteArrayConv(order1);
1262
1263 modInv(order1); // small numbers
1264 modInv(order3); // Karatsuba range
1265 modInv(order4); // Toom-Cook / Burnikel-Ziegler range
1266
1267 modExp(order1, order2);
1268 modExp2(order1);
1269
1270 stringConv();
1271 serialize();
1272
1273 multiplyLarge();
1274 squareLarge();
1275 divideLarge();
1276
1277 if (failure)
1278 throw new RuntimeException("Failure in BigIntegerTest.");
1279 }
1280
1281 /*
1282 * Get a random or boundary-case number. This is designed to provide
1283 * a lot of numbers that will find failure points, such as max sized
1284 * numbers, empty BigIntegers, etc.
1285 *
1286 * If order is less than 2, order is changed to 2.
1287 */
1288 private static BigInteger fetchNumber(int order) {
1289 boolean negative = random.nextBoolean();
1290 int numType = random.nextInt(7);
1291 BigInteger result = null;
1292 if (order < 2) order = 2;
1293
1294 switch (numType) {
1295 case 0: // Empty
1296 result = BigInteger.ZERO;
1297 break;
1298
1299 case 1: // One
1300 result = BigInteger.ONE;
1301 break;
1302
1303 case 2: // All bits set in number
1304 int numBytes = (order+7)/8;
1305 byte[] fullBits = new byte[numBytes];
1306 for(int i=0; i<numBytes; i++)
1307 fullBits[i] = (byte)0xff;
1308 int excessBits = 8*numBytes - order;
1309 fullBits[0] &= (1 << (8-excessBits)) - 1;
1310 result = new BigInteger(1, fullBits);
1311 break;
1312
1313 case 3: // One bit in number
1314 result = BigInteger.ONE.shiftLeft(random.nextInt(order));
1315 break;
1316
1317 case 4: // Random bit density
1318 byte[] val = new byte[(order+7)/8];
1319 int iterations = random.nextInt(order);
1320 for (int i=0; i<iterations; i++) {
1321 int bitIdx = random.nextInt(order);
1322 val[bitIdx/8] |= 1 << (bitIdx%8);
1323 }
1324 result = new BigInteger(1, val);
1325 break;
1326 case 5: // Runs of consecutive ones and zeros
1327 result = ZERO;
1328 int remaining = order;
1329 int bit = random.nextInt(2);
1330 while (remaining > 0) {
1331 int runLength = Math.min(remaining, random.nextInt(order));
1332 result = result.shiftLeft(runLength);
1333 if (bit > 0)
1334 result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
1335 remaining -= runLength;
1336 bit = 1 - bit;
1337 }
1338 break;
1339
1340 default: // random bits
1341 result = new BigInteger(order, random);
1342 }
1343
1344 if (negative)
1345 result = result.negate();
1346
1347 return result;
1348 }
1349
1350 static void report(String testName, int failCount) {
1351 System.err.println(testName+": " +
1352 (failCount==0 ? "Passed":"Failed("+failCount+")"));
1353 if (failCount > 0)
1354 failure = true;
1355 }
1356 }