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