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