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())%100+1]; 799 random.nextBytes(xBytes); 800 BigInteger x = new BigInteger(xBytes); 801 802 for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { 803 String result = x.toString(radix); 804 BigInteger test = new BigInteger(result, radix); 805 if (!test.equals(x)) { 806 failCount++; 807 System.err.println("BigInteger toString: "+x); 808 System.err.println("Test: "+test); 809 System.err.println(radix); 810 } 811 } 812 } 813 814 // String conversion straddling the Schoenhage algorithm crossover 815 // threshold, and at twice and four times the threshold. 816 for (int k = 0; k <= 2; k++) { 817 int factor = 1 << k; 818 int upper = factor * BITS_SCHOENHAGE_BASE + 33; 819 int lower = upper - 35; 820 821 for (int bits = upper; bits >= lower; bits--) { 822 for (int i = 0; i < 50; i++) { 823 BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, random)); 824 825 for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { 826 String result = x.toString(radix); 827 BigInteger test = new BigInteger(result, radix); 828 if (!test.equals(x)) { 829 failCount++; 830 System.err.println("BigInteger toString: " + x); 831 System.err.println("Test: " + test); 832 System.err.println(radix); 833 } 834 } 835 } 836 } 837 } 838 839 // 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 }