1 /*
   2  * Copyright (c) 1998, 2019, 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 8229845
  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())%200+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         // Check value with many trailing zeros.
 840         String val = "123456789" + "0".repeat(200);
 841         BigInteger b = new BigInteger(val);
 842         String s = b.toString();
 843         if (!val.equals(s)) {
 844             System.err.format("Expected length %d but got %d%n",
 845                 val.length(), s.length());
 846             failCount++;
 847         }
 848 
 849         report("String Conversion", failCount);
 850     }
 851 
 852     public static void byteArrayConv(int order) {
 853         int failCount = 0;
 854 
 855         for (int i=0; i<SIZE; i++) {
 856             BigInteger x = fetchNumber(order);
 857             while (x.equals(BigInteger.ZERO))
 858                 x = fetchNumber(order);
 859             BigInteger y = new BigInteger(x.toByteArray());
 860             if (!x.equals(y)) {
 861                 failCount++;
 862                 System.err.println("orig is "+x);
 863                 System.err.println("new is "+y);
 864             }
 865         }
 866         report("Array Conversion for " + order + " bits", failCount);
 867     }
 868 
 869     public static void modInv(int order) {
 870         int failCount = 0, successCount = 0, nonInvCount = 0;
 871 
 872         for (int i=0; i<SIZE; i++) {
 873             BigInteger x = fetchNumber(order);
 874             while(x.equals(BigInteger.ZERO))
 875                 x = fetchNumber(order);
 876             BigInteger m = fetchNumber(order).abs();
 877             while(m.compareTo(BigInteger.ONE) != 1)
 878                 m = fetchNumber(order).abs();
 879 
 880             try {
 881                 BigInteger inv = x.modInverse(m);
 882                 BigInteger prod = inv.multiply(x).remainder(m);
 883 
 884                 if (prod.signum() == -1)
 885                     prod = prod.add(m);
 886 
 887                 if (prod.equals(BigInteger.ONE))
 888                     successCount++;
 889                 else
 890                     failCount++;
 891             } catch(ArithmeticException e) {
 892                 nonInvCount++;
 893             }
 894         }
 895         report("Modular Inverse for " + order + " bits", failCount);
 896     }
 897 
 898     public static void modExp(int order1, int order2) {
 899         int failCount = 0;
 900 
 901         for (int i=0; i<SIZE/10; i++) {
 902             BigInteger m = fetchNumber(order1).abs();
 903             while(m.compareTo(BigInteger.ONE) != 1)
 904                 m = fetchNumber(order1).abs();
 905             BigInteger base = fetchNumber(order2);
 906             BigInteger exp = fetchNumber(8).abs();
 907 
 908             BigInteger z = base.modPow(exp, m);
 909             BigInteger w = base.pow(exp.intValue()).mod(m);
 910             if (!z.equals(w)) {
 911                 System.err.println("z is "+z);
 912                 System.err.println("w is "+w);
 913                 System.err.println("mod is "+m);
 914                 System.err.println("base is "+base);
 915                 System.err.println("exp is "+exp);
 916                 failCount++;
 917             }
 918         }
 919         report("Exponentiation I for " + order1 + " and " +
 920                order2 + " bits", failCount);
 921     }
 922 
 923     // This test is based on Fermat's theorem
 924     // which is not ideal because base must not be multiple of modulus
 925     // and modulus must be a prime or pseudoprime (Carmichael number)
 926     public static void modExp2(int order) {
 927         int failCount = 0;
 928 
 929         for (int i=0; i<10; i++) {
 930             BigInteger m = new BigInteger(100, 5, random);
 931             while(m.compareTo(BigInteger.ONE) != 1)
 932                 m = new BigInteger(100, 5, random);
 933             BigInteger exp = m.subtract(BigInteger.ONE);
 934             BigInteger base = fetchNumber(order).abs();
 935             while(base.compareTo(m) != -1)
 936                 base = fetchNumber(order).abs();
 937             while(base.equals(BigInteger.ZERO))
 938                 base = fetchNumber(order).abs();
 939 
 940             BigInteger one = base.modPow(exp, m);
 941             if (!one.equals(BigInteger.ONE)) {
 942                 System.err.println("m is "+m);
 943                 System.err.println("base is "+base);
 944                 System.err.println("exp is "+exp);
 945                 failCount++;
 946             }
 947         }
 948         report("Exponentiation II for " + order + " bits", failCount);
 949     }
 950 
 951     private static final int[] mersenne_powers = {
 952         521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
 953         21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
 954         1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };
 955 
 956     private static final long[] carmichaels = {
 957       561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
 958       62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
 959       278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
 960       225593397919L };
 961 
 962     // Note: testing the larger ones takes too long.
 963     private static final int NUM_MERSENNES_TO_TEST = 7;
 964     // Note: this constant used for computed Carmichaels, not the array above
 965     private static final int NUM_CARMICHAELS_TO_TEST = 5;
 966 
 967     private static final String[] customer_primes = {
 968         "120000000000000000000000000000000019",
 969         "633825300114114700748351603131",
 970         "1461501637330902918203684832716283019651637554291",
 971         "779626057591079617852292862756047675913380626199",
 972         "857591696176672809403750477631580323575362410491",
 973         "910409242326391377348778281801166102059139832131",
 974         "929857869954035706722619989283358182285540127919",
 975         "961301750640481375785983980066592002055764391999",
 976         "1267617700951005189537696547196156120148404630231",
 977         "1326015641149969955786344600146607663033642528339" };
 978 
 979     private static final BigInteger ZERO = BigInteger.ZERO;
 980     private static final BigInteger ONE = BigInteger.ONE;
 981     private static final BigInteger TWO = new BigInteger("2");
 982     private static final BigInteger SIX = new BigInteger("6");
 983     private static final BigInteger TWELVE = new BigInteger("12");
 984     private static final BigInteger EIGHTEEN = new BigInteger("18");
 985 
 986     public static void prime() {
 987         BigInteger p1, p2, c1;
 988         int failCount = 0;
 989 
 990         // Test consistency
 991         for(int i=0; i<10; i++) {
 992             p1 = BigInteger.probablePrime(100, random);
 993             if (!p1.isProbablePrime(100)) {
 994                 System.err.println("Consistency "+p1.toString(16));
 995                 failCount++;
 996             }
 997         }
 998 
 999         // Test some known Mersenne primes (2^n)-1
1000         // The array holds the exponents, not the numbers being tested
1001         for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) {
1002             p1 = new BigInteger("2");
1003             p1 = p1.pow(mersenne_powers[i]);
1004             p1 = p1.subtract(BigInteger.ONE);
1005             if (!p1.isProbablePrime(100)) {
1006                 System.err.println("Mersenne prime "+i+ " failed.");
1007                 failCount++;
1008             }
1009         }
1010 
1011         // Test some primes reported by customers as failing in the past
1012         for (int i=0; i<customer_primes.length; i++) {
1013             p1 = new BigInteger(customer_primes[i]);
1014             if (!p1.isProbablePrime(100)) {
1015                 System.err.println("Customer prime "+i+ " failed.");
1016                 failCount++;
1017             }
1018         }
1019 
1020         // Test some known Carmichael numbers.
1021         for (int i=0; i<carmichaels.length; i++) {
1022             c1 = BigInteger.valueOf(carmichaels[i]);
1023             if(c1.isProbablePrime(100)) {
1024                 System.err.println("Carmichael "+i+ " reported as prime.");
1025                 failCount++;
1026             }
1027         }
1028 
1029         // Test some computed Carmichael numbers.
1030         // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if
1031         // each of the factors is prime
1032         int found = 0;
1033         BigInteger f1 = new BigInteger(40, 100, random);
1034         while (found < NUM_CARMICHAELS_TO_TEST) {
1035             BigInteger k = null;
1036             BigInteger f2, f3;
1037             f1 = f1.nextProbablePrime();
1038             BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX);
1039             if (result[1].equals(ZERO)) {
1040                 k = result[0];
1041                 f2 = k.multiply(TWELVE).add(ONE);
1042                 if (f2.isProbablePrime(100)) {
1043                     f3 = k.multiply(EIGHTEEN).add(ONE);
1044                     if (f3.isProbablePrime(100)) {
1045                         c1 = f1.multiply(f2).multiply(f3);
1046                         if (c1.isProbablePrime(100)) {
1047                             System.err.println("Computed Carmichael "
1048                                                +c1.toString(16));
1049                             failCount++;
1050                         }
1051                         found++;
1052                     }
1053                 }
1054             }
1055             f1 = f1.add(TWO);
1056         }
1057 
1058         // Test some composites that are products of 2 primes
1059         for (int i=0; i<50; i++) {
1060             p1 = BigInteger.probablePrime(100, random);
1061             p2 = BigInteger.probablePrime(100, 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         for (int i=0; i<4; i++) {
1070             p1 = BigInteger.probablePrime(600, random);
1071             p2 = BigInteger.probablePrime(600, random);
1072             c1 = p1.multiply(p2);
1073             if (c1.isProbablePrime(100)) {
1074                 System.err.println("Composite failed "+c1.toString(16));
1075                 failCount++;
1076             }
1077         }
1078 
1079         report("Prime", failCount);
1080     }
1081 
1082     private static final long[] primesTo100 = {
1083         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
1084     };
1085 
1086     private static final long[] aPrimeSequence = {
1087         1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L,
1088         1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L,
1089         1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L,
1090         1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L,
1091         1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L,
1092         1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L,
1093         1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L,
1094         1999999853L, 1999999861L, 1999999871L, 1999999873
1095     };
1096 
1097     public static void nextProbablePrime() throws Exception {
1098         int failCount = 0;
1099         BigInteger p1, p2, p3;
1100         p1 = p2 = p3 = ZERO;
1101 
1102         // First test nextProbablePrime on the low range starting at zero
1103         for (int i=0; i<primesTo100.length; i++) {
1104             p1 = p1.nextProbablePrime();
1105             if (p1.longValue() != primesTo100[i]) {
1106                 System.err.println("low range primes failed");
1107                 System.err.println("p1 is "+p1);
1108                 System.err.println("expected "+primesTo100[i]);
1109                 failCount++;
1110             }
1111         }
1112 
1113         // Test nextProbablePrime on a relatively small, known prime sequence
1114         p1 = BigInteger.valueOf(aPrimeSequence[0]);
1115         for (int i=1; i<aPrimeSequence.length; i++) {
1116             p1 = p1.nextProbablePrime();
1117             if (p1.longValue() != aPrimeSequence[i]) {
1118                 System.err.println("prime sequence failed");
1119                 failCount++;
1120             }
1121         }
1122 
1123         // Next, pick some large primes, use nextProbablePrime to find the
1124         // next one, and make sure there are no primes in between
1125         for (int i=0; i<100; i+=10) {
1126             p1 = BigInteger.probablePrime(50 + i, random);
1127             p2 = p1.add(ONE);
1128             p3 = p1.nextProbablePrime();
1129             while(p2.compareTo(p3) < 0) {
1130                 if (p2.isProbablePrime(100)){
1131                     System.err.println("nextProbablePrime failed");
1132                     System.err.println("along range "+p1.toString(16));
1133                     System.err.println("to "+p3.toString(16));
1134                     failCount++;
1135                     break;
1136                 }
1137                 p2 = p2.add(ONE);
1138             }
1139         }
1140 
1141         report("nextProbablePrime", failCount);
1142     }
1143 
1144     public static void serialize() throws Exception {
1145         int failCount = 0;
1146 
1147         String bitPatterns[] = {
1148              "ffffffff00000000ffffffff00000000ffffffff00000000",
1149              "ffffffffffffffffffffffff000000000000000000000000",
1150              "ffffffff0000000000000000000000000000000000000000",
1151              "10000000ffffffffffffffffffffffffffffffffffffffff",
1152              "100000000000000000000000000000000000000000000000",
1153              "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
1154             "-ffffffff00000000ffffffff00000000ffffffff00000000",
1155             "-ffffffffffffffffffffffff000000000000000000000000",
1156             "-ffffffff0000000000000000000000000000000000000000",
1157             "-10000000ffffffffffffffffffffffffffffffffffffffff",
1158             "-100000000000000000000000000000000000000000000000",
1159             "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
1160         };
1161 
1162         for(int i = 0; i < bitPatterns.length; i++) {
1163             BigInteger b1 = new BigInteger(bitPatterns[i], 16);
1164             BigInteger b2 = null;
1165 
1166             File f = new File("serialtest");
1167 
1168             try (FileOutputStream fos = new FileOutputStream(f)) {
1169                 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1170                     oos.writeObject(b1);
1171                     oos.flush();
1172                 }
1173 
1174                 try (FileInputStream fis = new FileInputStream(f);
1175                      ObjectInputStream ois = new ObjectInputStream(fis))
1176                 {
1177                     b2 = (BigInteger)ois.readObject();
1178                 }
1179 
1180                 if (!b1.equals(b2) ||
1181                     !b1.equals(b1.or(b2))) {
1182                     failCount++;
1183                     System.err.println("Serialized failed for hex " +
1184                                        b1.toString(16));
1185                 }
1186             }
1187             f.delete();
1188         }
1189 
1190         for(int i=0; i<10; i++) {
1191             BigInteger b1 = fetchNumber(random.nextInt(100));
1192             BigInteger b2 = null;
1193             File f = new File("serialtest");
1194             try (FileOutputStream fos = new FileOutputStream(f)) {
1195                 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
1196                     oos.writeObject(b1);
1197                     oos.flush();
1198                 }
1199 
1200                 try (FileInputStream fis = new FileInputStream(f);
1201                      ObjectInputStream ois = new ObjectInputStream(fis))
1202                 {
1203                     b2 = (BigInteger)ois.readObject();
1204                 }
1205             }
1206 
1207             if (!b1.equals(b2) ||
1208                 !b1.equals(b1.or(b2)))
1209                 failCount++;
1210             f.delete();
1211         }
1212 
1213         report("Serialize", failCount);
1214     }
1215 
1216     /**
1217      * Main to interpret arguments and run several tests.
1218      *
1219      * Up to three arguments may be given to specify the SIZE of BigIntegers
1220      * used for call parameters 1, 2, and 3. The SIZE is interpreted as
1221      * the maximum number of decimal digits that the parameters will have.
1222      *
1223      */
1224     public static void main(String[] args) throws Exception {
1225         // Some variables for sizing test numbers in bits
1226         int order1 = ORDER_MEDIUM;
1227         int order2 = ORDER_SMALL;
1228         int order3 = ORDER_KARATSUBA;
1229         int order4 = ORDER_TOOM_COOK;
1230 
1231         if (args.length >0)
1232             order1 = (int)((Integer.parseInt(args[0]))* 3.333);
1233         if (args.length >1)
1234             order2 = (int)((Integer.parseInt(args[1]))* 3.333);
1235         if (args.length >2)
1236             order3 = (int)((Integer.parseInt(args[2]))* 3.333);
1237         if (args.length >3)
1238             order4 = (int)((Integer.parseInt(args[3]))* 3.333);
1239 
1240         constructor();
1241 
1242         prime();
1243         nextProbablePrime();
1244 
1245         arithmetic(order1);   // small numbers
1246         arithmetic(order3);   // Karatsuba range
1247         arithmetic(order4);   // Toom-Cook / Burnikel-Ziegler range
1248 
1249         divideAndRemainder(order1);   // small numbers
1250         divideAndRemainder(order3);   // Karatsuba range
1251         divideAndRemainder(order4);   // Toom-Cook / Burnikel-Ziegler range
1252 
1253         pow(order1);
1254         pow(order3);
1255         pow(order4);
1256 
1257         square(ORDER_MEDIUM);
1258         square(ORDER_KARATSUBA_SQUARE);
1259         square(ORDER_TOOM_COOK_SQUARE);
1260 
1261         squareRoot();
1262         squareRootAndRemainder();
1263 
1264         bitCount();
1265         bitLength();
1266         bitOps(order1);
1267         bitwise(order1);
1268 
1269         shift(order1);
1270 
1271         byteArrayConv(order1);
1272 
1273         modInv(order1);   // small numbers
1274         modInv(order3);   // Karatsuba range
1275         modInv(order4);   // Toom-Cook / Burnikel-Ziegler range
1276 
1277         modExp(order1, order2);
1278         modExp2(order1);
1279 
1280         stringConv();
1281         serialize();
1282 
1283         multiplyLarge();
1284         squareLarge();
1285         divideLarge();
1286 
1287         if (failure)
1288             throw new RuntimeException("Failure in BigIntegerTest.");
1289     }
1290 
1291     /*
1292      * Get a random or boundary-case number. This is designed to provide
1293      * a lot of numbers that will find failure points, such as max sized
1294      * numbers, empty BigIntegers, etc.
1295      *
1296      * If order is less than 2, order is changed to 2.
1297      */
1298     private static BigInteger fetchNumber(int order) {
1299         boolean negative = random.nextBoolean();
1300         int numType = random.nextInt(7);
1301         BigInteger result = null;
1302         if (order < 2) order = 2;
1303 
1304         switch (numType) {
1305             case 0: // Empty
1306                 result = BigInteger.ZERO;
1307                 break;
1308 
1309             case 1: // One
1310                 result = BigInteger.ONE;
1311                 break;
1312 
1313             case 2: // All bits set in number
1314                 int numBytes = (order+7)/8;
1315                 byte[] fullBits = new byte[numBytes];
1316                 for(int i=0; i<numBytes; i++)
1317                     fullBits[i] = (byte)0xff;
1318                 int excessBits = 8*numBytes - order;
1319                 fullBits[0] &= (1 << (8-excessBits)) - 1;
1320                 result = new BigInteger(1, fullBits);
1321                 break;
1322 
1323             case 3: // One bit in number
1324                 result = BigInteger.ONE.shiftLeft(random.nextInt(order));
1325                 break;
1326 
1327             case 4: // Random bit density
1328                 byte[] val = new byte[(order+7)/8];
1329                 int iterations = random.nextInt(order);
1330                 for (int i=0; i<iterations; i++) {
1331                     int bitIdx = random.nextInt(order);
1332                     val[bitIdx/8] |= 1 << (bitIdx%8);
1333                 }
1334                 result = new BigInteger(1, val);
1335                 break;
1336             case 5: // Runs of consecutive ones and zeros
1337                 result = ZERO;
1338                 int remaining = order;
1339                 int bit = random.nextInt(2);
1340                 while (remaining > 0) {
1341                     int runLength = Math.min(remaining, random.nextInt(order));
1342                     result = result.shiftLeft(runLength);
1343                     if (bit > 0)
1344                         result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
1345                     remaining -= runLength;
1346                     bit = 1 - bit;
1347                 }
1348                 break;
1349 
1350             default: // random bits
1351                 result = new BigInteger(order, random);
1352         }
1353 
1354         if (negative)
1355             result = result.negate();
1356 
1357         return result;
1358     }
1359 
1360     static void report(String testName, int failCount) {
1361         System.err.println(testName+": " +
1362                            (failCount==0 ? "Passed":"Failed("+failCount+")"));
1363         if (failCount > 0)
1364             failure = true;
1365     }
1366 }