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