1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package tests.api.java.math; 19 20import java.math.BigInteger; 21import java.util.Random; 22 23public class BigIntegerTest extends junit.framework.TestCase { 24 25 BigInteger minusTwo = new BigInteger("-2", 10); 26 27 BigInteger minusOne = new BigInteger("-1", 10); 28 29 BigInteger zero = new BigInteger("0", 10); 30 31 BigInteger one = new BigInteger("1", 10); 32 33 BigInteger two = new BigInteger("2", 10); 34 35 BigInteger ten = new BigInteger("10", 10); 36 37 BigInteger sixteen = new BigInteger("16", 10); 38 39 BigInteger oneThousand = new BigInteger("1000", 10); 40 41 BigInteger aZillion = new BigInteger( 42 "100000000000000000000000000000000000000000000000000", 10); 43 44 BigInteger twoToTheTen = new BigInteger("1024", 10); 45 46 BigInteger twoToTheSeventy = two.pow(70); 47 48 Random rand = new Random(); 49 50 BigInteger bi; 51 52 BigInteger bi1; 53 54 BigInteger bi2; 55 56 BigInteger bi3; 57 58 BigInteger bi11; 59 60 BigInteger bi22; 61 62 BigInteger bi33; 63 64 BigInteger bi12; 65 66 BigInteger bi23; 67 68 BigInteger bi13; 69 70 BigInteger largePos; 71 72 BigInteger smallPos; 73 74 BigInteger largeNeg; 75 76 BigInteger smallNeg; 77 78 BigInteger[][] booleanPairs; 79 80 /** 81 * java.math.BigInteger#BigInteger(int, java.util.Random) 82 */ 83 public void test_ConstructorILjava_util_Random() { 84 // regression test for HARMONY-1047 85 try { 86 new BigInteger(Integer.MAX_VALUE, (Random)null); 87 fail("NegativeArraySizeException expected"); 88 } catch (NegativeArraySizeException e) { 89 // PASSED 90 } 91 92 bi = new BigInteger(70, rand); 93 bi2 = new BigInteger(70, rand); 94 assertTrue("Random number is negative", bi.compareTo(zero) >= 0); 95 assertTrue("Random number is too big", 96 bi.compareTo(twoToTheSeventy) < 0); 97 assertTrue( 98 "Two random numbers in a row are the same (might not be a bug but it very likely is)", 99 !bi.equals(bi2)); 100 assertTrue("Not zero", new BigInteger(0, rand).equals(BigInteger.ZERO)); 101 102 try { 103 new BigInteger(-1, (Random)null); 104 fail("IllegalArgumentException expected"); 105 } catch (IllegalArgumentException e) { 106 // PASSED 107 } 108 } 109 110 /** 111 * java.math.BigInteger#BigInteger(int, int, java.util.Random) 112 */ 113 // BIGNUM returns no Primes smaller than 16 bits. 114 public void test_ConstructorIILjava_util_Random() { 115 bi = new BigInteger(10, 5, rand); 116 bi2 = new BigInteger(10, 5, rand); 117 assertTrue("Random number one is negative", bi.compareTo(zero) >= 0); 118 assertTrue("Random number one is too big", 119 bi.compareTo(twoToTheTen) < 0); 120 assertTrue("Random number two is negative", bi2.compareTo(zero) >= 0); 121 assertTrue("Random number two is too big", 122 bi2.compareTo(twoToTheTen) < 0); 123 124 Random rand = new Random(); 125 BigInteger bi; 126 int certainty[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 127 Integer.MIN_VALUE, Integer.MIN_VALUE + 1, -2, -1 }; 128 for (int i = 2; i <= 20; i++) { 129 for (int c = 0; c < certainty.length; c++) { 130 bi = new BigInteger(i, c, rand); // Create BigInteger 131 assertTrue("Bit length incorrect", bi.bitLength() == i); 132 } 133 } 134 135 try { 136 new BigInteger(1, 80, (Random)null); 137 fail("ArithmeticException expected"); 138 } catch (ArithmeticException e) { 139 // PASSED 140 } 141 142 try { 143 new BigInteger(-1, (Random)null); 144 fail("IllegalArgumentException expected"); 145 } catch (IllegalArgumentException e) { 146 // PASSED 147 } 148 } 149 150 /** 151 * java.math.BigInteger#BigInteger(byte[]) 152 */ 153 public void test_Constructor$B() { 154 byte[] myByteArray; 155 myByteArray = new byte[] { (byte) 0x00, (byte) 0xFF, (byte) 0xFE }; 156 bi = new BigInteger(myByteArray); 157 assertTrue("Incorrect value for pos number", bi.equals(BigInteger.ZERO 158 .setBit(16).subtract(two))); 159 myByteArray = new byte[] { (byte) 0xFF, (byte) 0xFE }; 160 bi = new BigInteger(myByteArray); 161 assertTrue("Incorrect value for neg number", bi.equals(minusTwo)); 162 } 163 164 /** 165 * java.math.BigInteger#BigInteger(int, byte[]) 166 */ 167 public void test_ConstructorI$B() { 168 byte[] myByteArray; 169 myByteArray = new byte[] { (byte) 0xFF, (byte) 0xFE }; 170 bi = new BigInteger(1, myByteArray); 171 assertTrue("Incorrect value for pos number", bi.equals(BigInteger.ZERO 172 .setBit(16).subtract(two))); 173 bi = new BigInteger(-1, myByteArray); 174 assertTrue("Incorrect value for neg number", bi.equals(BigInteger.ZERO 175 .setBit(16).subtract(two).negate())); 176 myByteArray = new byte[] { (byte) 0, (byte) 0 }; 177 bi = new BigInteger(0, myByteArray); 178 assertTrue("Incorrect value for zero", bi.equals(zero)); 179 myByteArray = new byte[] { (byte) 1 }; 180 try { 181 new BigInteger(0, myByteArray); 182 fail("Failed to throw NumberFormatException"); 183 } catch (NumberFormatException e) { 184 // correct 185 } 186 } 187 188 /** 189 * java.math.BigInteger#BigInteger(java.lang.String) 190 */ 191 public void test_constructor_String_empty() { 192 try { 193 new BigInteger(""); 194 fail("Expected NumberFormatException for new BigInteger(\"\")"); 195 } catch (NumberFormatException e) { 196 } 197 } 198 199 /** 200 * java.math.BigInteger#toByteArray() 201 */ 202 public void test_toByteArray() { 203 byte[] myByteArray, anotherByteArray; 204 myByteArray = new byte[] { 97, 33, 120, 124, 50, 2, 0, 0, 0, 12, 124, 205 42 }; 206 anotherByteArray = new BigInteger(myByteArray).toByteArray(); 207 assertTrue("Incorrect byte array returned", 208 myByteArray.length == anotherByteArray.length); 209 for (int counter = myByteArray.length - 1; counter >= 0; counter--) { 210 assertTrue("Incorrect values in returned byte array", 211 myByteArray[counter] == anotherByteArray[counter]); 212 } 213 } 214 215// public void test_SpecialPrimes() { 216// System.out.println("test_SpecialPrimes"); 217// final BigInteger TWO = BigInteger.valueOf(2); 218// BigInteger p, q; 219// for (;;) { 220// p = new BigInteger(1024, 23, new Random()); 221// q = p.subtract(BigInteger.ONE).divide(TWO); 222// if (q.isProbablePrime(20)) { 223// System.out.println(q); 224// System.out.println(p); 225// break; 226// } 227// System.out.print("."); 228// } 229// fail("isProbablePrime failed for: " + bi); 230// } 231 232 /** 233 * java.math.BigInteger#isProbablePrime(int) 234 */ 235 public void test_isProbablePrimeI() { 236 int fails = 0; 237 bi = new BigInteger(20, 20, rand); 238 if (!bi.isProbablePrime(17)) { 239 fails++; 240 } 241 bi = new BigInteger("4", 10); 242 if (bi.isProbablePrime(17)) { 243 fail("isProbablePrime failed for: " + bi); 244 } 245 bi = BigInteger.valueOf(17L * 13L); 246 if (bi.isProbablePrime(17)) { 247 fail("isProbablePrime failed for: " + bi); 248 } 249 for (long a = 2; a < 1000; a++) { 250 if (isPrime(a)) { 251 assertTrue("false negative on prime number <1000", BigInteger 252 .valueOf(a).isProbablePrime(5)); 253 } else if (BigInteger.valueOf(a).isProbablePrime(17)) { 254 System.out.println("isProbablePrime failed for: " + a); 255 fails++; 256 } 257 } 258 for (int a = 0; a < 1000; a++) { 259 bi = BigInteger.valueOf(rand.nextInt(1000000)).multiply( 260 BigInteger.valueOf(rand.nextInt(1000000))); 261 if (bi.isProbablePrime(17)) { 262 System.out.println("isProbablePrime failed for: " + bi); 263 fails++; 264 } 265 } 266 for (int a = 0; a < 200; a++) { 267 bi = new BigInteger(70, rand).multiply(new BigInteger(70, rand)); 268 if (bi.isProbablePrime(17)) { 269 System.out.println("isProbablePrime failed for: " + bi); 270 fails++; 271 } 272 } 273 assertTrue("Too many false positives - may indicate a problem", 274 fails <= 1); 275 276 // 277 // And now some tests on real big integers: 278 // 279 bi = new BigInteger("153890972191202256150310830154922163807316525358455215516067727076235016932726922093888770552128767458882963869421440585369743", 10); 280 if (!bi.isProbablePrime(80)) { 281 fail("isProbablePrime failed for: " + bi); 282 } 283 bi = new BigInteger("2090575416269141767246491983797422123741252476560371649798066134123893524014911825188890458270426076468664046568752890122415061377308817346303546688282957897504000216241497550243010257911214329646877810655164658470278901030511157372440751259674247310396158238588463284702737181653", 10); 284 if (!bi.isProbablePrime(80)) { 285 fail("isProbablePrime failed for: " + bi); 286 } 287 // 288 for (int bitLength = 100; bitLength <= 600; bitLength += 100) { 289 BigInteger a = BigInteger.probablePrime(bitLength, rand); 290 BigInteger b = BigInteger.probablePrime(bitLength, rand); 291 BigInteger c = a.multiply(b); 292 assertFalse("isProbablePrime failed for product of two large primes" + 293 a + " * " + b + " = " + c + 294 " (bitLength = " + bitLength + ")", 295 c.isProbablePrime(80) ); 296 } 297 } 298 299 /** 300 * java.math.BigInteger#nextProbablePrime() 301 */ 302 public void test_nextProbablePrime() { 303 largePrimesProduct( 304 new BigInteger("2537895984043447429238717358455377929009126353874925049325287329295635198252046158619999217453233889378619619008359011789"), 305 new BigInteger("1711501451602688337873833423534849678524059393231999670806585630179374689152366029939952735718718709436427337762082614710093"), 306 "4343612660706993434504106787562106084038357258130862545477481433639575850237346784798851102536616749334772541987502120552264920040629526028540204698334741815536099373917351194423681128374184971846099257056996626343051832131340568120612204287123" 307 ); 308 309 largePrimesProduct( 310 new BigInteger("4617974730611208463200675282934641082129817404749925308887287017217158545765190433369842932770197341032031682222405074564586462802072184047198214312142847809259437477387527466762251087500170588962277514858557309036550499896961735701485020851"), 311 new BigInteger("4313158964405728158057980867015758419530142215799386331265837224051830838583266274443105715022196238165196727467066901495701708590167750818040112544031694506528759169669442493029999154074962566165293254671176670719518898684698255068313216294333"), 312 "19918059106734861363335842730108905466210762564765297409619920041621379008685530738918145604092111306972524565803236031571858280032420140331838737621152630780261815015157696362550138161774466814661069892975003440654998880587960037013294137372709096788892473385003457361736563927256562678181177287998121131179907762285048659075843995525830945659905573174849006768920618442371027575308854641789533211132313916836205357976988977849024687805212304038260207820679964201211309384057458137851" 313 ); 314 } 315 316 static void largePrimesProduct(BigInteger a, BigInteger b, String c) { 317 BigInteger wp = a.multiply(b); 318 assertFalse("isProbablePrime failed for product of two large primes" + 319 a + " * " + b + " = " + c, 320 wp.isProbablePrime(80) ); 321 BigInteger wpMinusOne = wp.subtract(BigInteger.ONE); 322 BigInteger next = wpMinusOne.nextProbablePrime(); 323// System.out.println(c); 324// System.out.println(next); 325 assertTrue("nextProbablePrime returns wrong number: " + next + 326 "instead of expected: " + c, 327 next.toString().equals(c) ); 328 } 329 330 /** 331 * java.math.BigInteger#probablePrime(int, java.util.Random) 332 */ 333 public void test_probablePrime() { 334 for (int bitLength = 50; bitLength <= 1050; bitLength += 100) { 335 BigInteger a = BigInteger.probablePrime(bitLength, rand); 336 assertTrue("isProbablePrime(probablePrime()) failed for: " + bi, 337 a.isProbablePrime(80)); 338// System.out.println(a); 339// BigInteger prime = a.nextProbablePrime(); 340// System.out.print("Next Probable Prime is "); 341// System.out.println(prime); 342 } 343 } 344 345// BEGIN android-added 346// public void testModPowPerformance() { 347// Random rnd = new Random(); 348// for (int i = 0; i < 10; i++) { 349// BigInteger a = new BigInteger(512, rnd); 350// BigInteger m = new BigInteger(1024, rnd); 351// BigInteger p = new BigInteger(256, rnd); 352// BigInteger mp = a.modPow(p, m); 353// System.out.println(mp); 354// } 355// } 356 357// shows factor 20 speed up (BIGNUM to Harmony Java): 358// public void testNextProbablePrime() { 359// Random rnd = new Random(); 360// rnd.setSeed(0); 361// for (int i = 1; i <= 32; i += 1) { 362// BigInteger a = new BigInteger(i, rnd); 363// System.out.println(a); 364// BigInteger prime = a.nextProbablePrime(); 365// System.out.print("Next Probable Prime is "); 366// System.out.println(prime); 367// } 368// for (int i = 1; i <= 32; i += 4) { 369// BigInteger a = new BigInteger(32 * i, rnd); 370// System.out.println(a); 371// BigInteger prime = a.nextProbablePrime(); 372// System.out.print("Next Probable Prime is "); 373// System.out.println(prime); 374// } 375// } 376 377// shows factor 20 speed up (BIGNUM to Harmony Java): 378// shows that certainty 80 is "practically aquivalent" to certainty 100 379// public void testPrimeGenPerformance() { 380// Random rnd = new Random(); 381// rnd.setSeed(0); 382// for (int i = 1; i <= 32; i +=8 ) { 383// BigInteger a = new BigInteger(32 * i, 80, rnd); 384// System.out.println(a); 385// System.out.println("Now testing it again:"); 386// if (a.isProbablePrime(100)) { 387// System.out.println("************************ PASSED! **************************"); 388// } else { 389// System.out.println("************************ FAILED!!! **************************"); 390// System.out.println("************************ FAILED!!! **************************"); 391// System.out.println("************************ FAILED!!! **************************"); 392// System.out.println("************************ FAILED!!! **************************"); 393// System.out.println("************************ FAILED!!! **************************"); 394// System.out.println("************************ FAILED!!! **************************"); 395// } 396// } 397// } 398// END android-added 399 400 401 402 /** 403 * java.math.BigInteger#equals(java.lang.Object) 404 */ 405 public void test_equalsLjava_lang_Object() { 406 assertTrue("0=0", zero.equals(BigInteger.valueOf(0))); 407 assertTrue("-123=-123", BigInteger.valueOf(-123).equals( 408 BigInteger.valueOf(-123))); 409 assertTrue("0=1", !zero.equals(one)); 410 assertTrue("0=-1", !zero.equals(minusOne)); 411 assertTrue("1=-1", !one.equals(minusOne)); 412 assertTrue("bi3=bi3", bi3.equals(bi3)); 413 assertTrue("bi3=copy of bi3", bi3.equals(bi3.negate().negate())); 414 assertTrue("bi3=bi2", !bi3.equals(bi2)); 415 } 416 417 /** 418 * java.math.BigInteger#compareTo(java.math.BigInteger) 419 */ 420 public void test_compareToLjava_math_BigInteger() { 421 assertTrue("Smaller number returned >= 0", one.compareTo(two) < 0); 422 assertTrue("Larger number returned >= 0", two.compareTo(one) > 0); 423 assertTrue("Equal numbers did not return 0", one.compareTo(one) == 0); 424 assertTrue("Neg number messed things up", 425 two.negate().compareTo(one) < 0); 426 } 427 428 /** 429 * java.math.BigInteger#intValue() 430 */ 431 public void test_intValue() { 432 assertTrue("Incorrect intValue for 2**70", 433 twoToTheSeventy.intValue() == 0); 434 assertTrue("Incorrect intValue for 2", two.intValue() == 2); 435 } 436 437 /** 438 * java.math.BigInteger#longValue() 439 */ 440 public void test_longValue() { 441 assertTrue("Incorrect longValue for 2**70", 442 twoToTheSeventy.longValue() == 0); 443 assertTrue("Incorrect longValue for 2", two.longValue() == 2); 444 } 445 446 /** 447 * java.math.BigInteger#valueOf(long) 448 */ 449 public void test_valueOfJ() { 450 assertTrue("Incurred number returned for 2", BigInteger.valueOf(2L) 451 .equals(two)); 452 assertTrue("Incurred number returned for 200", BigInteger.valueOf(200L) 453 .equals(BigInteger.valueOf(139).add(BigInteger.valueOf(61)))); 454 } 455 456 /** 457 * java.math.BigInteger#add(java.math.BigInteger) 458 */ 459 public void test_addLjava_math_BigInteger() { 460 assertTrue("Incorrect sum--wanted a zillion", aZillion.add(aZillion) 461 .add(aZillion.negate()).equals(aZillion)); 462 assertTrue("0+0", zero.add(zero).equals(zero)); 463 assertTrue("0+1", zero.add(one).equals(one)); 464 assertTrue("1+0", one.add(zero).equals(one)); 465 assertTrue("1+1", one.add(one).equals(two)); 466 assertTrue("0+(-1)", zero.add(minusOne).equals(minusOne)); 467 assertTrue("(-1)+0", minusOne.add(zero).equals(minusOne)); 468 assertTrue("(-1)+(-1)", minusOne.add(minusOne).equals(minusTwo)); 469 assertTrue("1+(-1)", one.add(minusOne).equals(zero)); 470 assertTrue("(-1)+1", minusOne.add(one).equals(zero)); 471 472 for (int i = 0; i < 200; i++) { 473 BigInteger midbit = zero.setBit(i); 474 assertTrue("add fails to carry on bit " + i, midbit.add(midbit) 475 .equals(zero.setBit(i + 1))); 476 } 477 BigInteger bi2p3 = bi2.add(bi3); 478 BigInteger bi3p2 = bi3.add(bi2); 479 assertTrue("bi2p3=bi3p2", bi2p3.equals(bi3p2)); 480 481 482 // BESSER UEBERGREIFENDE TESTS MACHEN IN FORM VON STRESS TEST. 483 // add large positive + small positive 484 BigInteger sum = aZillion; 485 BigInteger increment = one; 486 for (int i = 0; i < 20; i++) { 487 488 } 489 490 // add large positive + small negative 491 492 // add large negative + small positive 493 494 // add large negative + small negative 495 } 496 497 /** 498 * java.math.BigInteger#negate() 499 */ 500 public void test_negate() { 501 assertTrue("Single negation of zero did not result in zero", zero 502 .negate().equals(zero)); 503 assertTrue("Single negation resulted in original nonzero number", 504 !aZillion.negate().equals(aZillion)); 505 assertTrue("Double negation did not result in original number", 506 aZillion.negate().negate().equals(aZillion)); 507 508 assertTrue("0.neg", zero.negate().equals(zero)); 509 assertTrue("1.neg", one.negate().equals(minusOne)); 510 assertTrue("2.neg", two.negate().equals(minusTwo)); 511 assertTrue("-1.neg", minusOne.negate().equals(one)); 512 assertTrue("-2.neg", minusTwo.negate().equals(two)); 513 assertTrue("0x62EB40FEF85AA9EBL*2.neg", BigInteger.valueOf( 514 0x62EB40FEF85AA9EBL * 2).negate().equals( 515 BigInteger.valueOf(-0x62EB40FEF85AA9EBL * 2))); 516 for (int i = 0; i < 200; i++) { 517 BigInteger midbit = zero.setBit(i); 518 BigInteger negate = midbit.negate(); 519 assertTrue("negate negate", negate.negate().equals(midbit)); 520 assertTrue("neg fails on bit " + i, midbit.negate().add(midbit) 521 .equals(zero)); 522 } 523 } 524 525 /** 526 * java.math.BigInteger#signum() 527 */ 528 public void test_signum() { 529 assertTrue("Wrong positive signum", two.signum() == 1); 530 assertTrue("Wrong zero signum", zero.signum() == 0); 531 assertTrue("Wrong neg zero signum", zero.negate().signum() == 0); 532 assertTrue("Wrong neg signum", two.negate().signum() == -1); 533 } 534 535 /** 536 * java.math.BigInteger#abs() 537 */ 538 public void test_abs() { 539 assertTrue("Invalid number returned for zillion", aZillion.negate() 540 .abs().equals(aZillion.abs())); 541 assertTrue("Invalid number returned for zero neg", zero.negate().abs() 542 .equals(zero)); 543 assertTrue("Invalid number returned for zero", zero.abs().equals(zero)); 544 assertTrue("Invalid number returned for two", two.negate().abs() 545 .equals(two)); 546 } 547 548 /** 549 * java.math.BigInteger#pow(int) 550 */ 551 public void test_powI() { 552 assertTrue("Incorrect exponent returned for 2**10", two.pow(10).equals( 553 twoToTheTen)); 554 assertTrue("Incorrect exponent returned for 2**70", two.pow(30) 555 .multiply(two.pow(40)).equals(twoToTheSeventy)); 556 assertTrue("Incorrect exponent returned for 10**50", ten.pow(50) 557 .equals(aZillion)); 558 } 559 560 /** 561 * java.math.BigInteger#modInverse(java.math.BigInteger) 562 */ 563 public void test_modInverseLjava_math_BigInteger() { 564 BigInteger a = zero, mod, inv; 565 for (int j = 3; j < 50; j++) { 566 mod = BigInteger.valueOf(j); 567 for (int i = -j + 1; i < j; i++) { 568 try { 569 a = BigInteger.valueOf(i); 570 inv = a.modInverse(mod); 571 assertTrue("bad inverse: " + a + " inv mod " + mod 572 + " equals " + inv, one.equals(a.multiply(inv).mod( 573 mod))); 574 assertTrue("inverse greater than modulo: " + a 575 + " inv mod " + mod + " equals " + inv, inv 576 .compareTo(mod) < 0); 577 assertTrue("inverse less than zero: " + a + " inv mod " 578 + mod + " equals " + inv, inv 579 .compareTo(BigInteger.ZERO) >= 0); 580 } catch (ArithmeticException e) { 581 assertTrue("should have found inverse for " + a + " mod " 582 + mod, !one.equals(a.gcd(mod))); 583 } 584 } 585 } 586 for (int j = 1; j < 10; j++) { 587 mod = bi2.add(BigInteger.valueOf(j)); 588 for (int i = 0; i < 20; i++) { 589 try { 590 a = bi3.add(BigInteger.valueOf(i)); 591 inv = a.modInverse(mod); 592 assertTrue("bad inverse: " + a + " inv mod " + mod 593 + " equals " + inv, one.equals(a.multiply(inv).mod( 594 mod))); 595 assertTrue("inverse greater than modulo: " + a 596 + " inv mod " + mod + " equals " + inv, inv 597 .compareTo(mod) < 0); 598 assertTrue("inverse less than zero: " + a + " inv mod " 599 + mod + " equals " + inv, inv 600 .compareTo(BigInteger.ZERO) >= 0); 601 } catch (ArithmeticException e) { 602 assertTrue("should have found inverse for " + a + " mod " 603 + mod, !one.equals(a.gcd(mod))); 604 } 605 } 606 } 607 } 608 609 /** 610 * java.math.BigInteger#shiftRight(int) 611 */ 612 public void test_shiftRightI() { 613 assertTrue("1 >> 0", BigInteger.valueOf(1).shiftRight(0).equals( 614 BigInteger.ONE)); 615 assertTrue("1 >> 1", BigInteger.valueOf(1).shiftRight(1).equals( 616 BigInteger.ZERO)); 617 assertTrue("1 >> 63", BigInteger.valueOf(1).shiftRight(63).equals( 618 BigInteger.ZERO)); 619 assertTrue("1 >> 64", BigInteger.valueOf(1).shiftRight(64).equals( 620 BigInteger.ZERO)); 621 assertTrue("1 >> 65", BigInteger.valueOf(1).shiftRight(65).equals( 622 BigInteger.ZERO)); 623 assertTrue("1 >> 1000", BigInteger.valueOf(1).shiftRight(1000).equals( 624 BigInteger.ZERO)); 625 assertTrue("-1 >> 0", BigInteger.valueOf(-1).shiftRight(0).equals( 626 minusOne)); 627 assertTrue("-1 >> 1", BigInteger.valueOf(-1).shiftRight(1).equals( 628 minusOne)); 629 assertTrue("-1 >> 63", BigInteger.valueOf(-1).shiftRight(63).equals( 630 minusOne)); 631 assertTrue("-1 >> 64", BigInteger.valueOf(-1).shiftRight(64).equals( 632 minusOne)); 633 assertTrue("-1 >> 65", BigInteger.valueOf(-1).shiftRight(65).equals( 634 minusOne)); 635 assertTrue("-1 >> 1000", BigInteger.valueOf(-1).shiftRight(1000) 636 .equals(minusOne)); 637 638 BigInteger a = BigInteger.ONE; 639 BigInteger c = bi3; 640 BigInteger E = bi3.negate(); 641 BigInteger e = E; 642 for (int i = 0; i < 200; i++) { 643 BigInteger b = BigInteger.ZERO.setBit(i); 644 assertTrue("a==b", a.equals(b)); 645 a = a.shiftLeft(1); 646 assertTrue("a non-neg", a.signum() >= 0); 647 648 BigInteger d = bi3.shiftRight(i); 649 assertTrue("c==d", c.equals(d)); 650 c = c.shiftRight(1); 651 assertTrue(">>1 == /2", d.divide(two).equals(c)); 652 assertTrue("c non-neg", c.signum() >= 0); 653 654 BigInteger f = E.shiftRight(i); 655 assertTrue("e==f", e.equals(f)); 656 e = e.shiftRight(1); 657 assertTrue(">>1 == /2", f.subtract(one).divide(two).equals(e)); 658 assertTrue("e negative", e.signum() == -1); 659 660 assertTrue("b >> i", b.shiftRight(i).equals(one)); 661 assertTrue("b >> i+1", b.shiftRight(i + 1).equals(zero)); 662 assertTrue("b >> i-1", b.shiftRight(i - 1).equals(two)); 663 } 664 } 665 666 /** 667 * java.math.BigInteger#shiftLeft(int) 668 */ 669 public void test_shiftLeftI() { 670 assertTrue("1 << 0", one.shiftLeft(0).equals(one)); 671 assertTrue("1 << 1", one.shiftLeft(1).equals(two)); 672 assertTrue("1 << 63", one.shiftLeft(63).equals( 673 new BigInteger("8000000000000000", 16))); 674 assertTrue("1 << 64", one.shiftLeft(64).equals( 675 new BigInteger("10000000000000000", 16))); 676 assertTrue("1 << 65", one.shiftLeft(65).equals( 677 new BigInteger("20000000000000000", 16))); 678 assertTrue("-1 << 0", minusOne.shiftLeft(0).equals(minusOne)); 679 assertTrue("-1 << 1", minusOne.shiftLeft(1).equals(minusTwo)); 680 assertTrue("-1 << 63", minusOne.shiftLeft(63).equals( 681 new BigInteger("-9223372036854775808"))); 682 assertTrue("-1 << 64", minusOne.shiftLeft(64).equals( 683 new BigInteger("-18446744073709551616"))); 684 assertTrue("-1 << 65", minusOne.shiftLeft(65).equals( 685 new BigInteger("-36893488147419103232"))); 686 687 BigInteger a = bi3; 688 BigInteger c = minusOne; 689 for (int i = 0; i < 200; i++) { 690 BigInteger b = bi3.shiftLeft(i); 691 assertTrue("a==b", a.equals(b)); 692 assertTrue("a >> i == bi3", a.shiftRight(i).equals(bi3)); 693 a = a.shiftLeft(1); 694 assertTrue("<<1 == *2", b.multiply(two).equals(a)); 695 assertTrue("a non-neg", a.signum() >= 0); 696 assertTrue("a.bitCount==b.bitCount", a.bitCount() == b.bitCount()); 697 698 BigInteger d = minusOne.shiftLeft(i); 699 assertTrue("c==d", c.equals(d)); 700 c = c.shiftLeft(1); 701 assertTrue("<<1 == *2 negative", d.multiply(two).equals(c)); 702 assertTrue("c negative", c.signum() == -1); 703 assertTrue("d >> i == minusOne", d.shiftRight(i).equals(minusOne)); 704 } 705 } 706 707 /** 708 * java.math.BigInteger#multiply(java.math.BigInteger) 709 */ 710 public void test_multiplyLjava_math_BigInteger() { 711 assertTrue("Incorrect sum--wanted three zillion", aZillion 712 .add(aZillion).add(aZillion).equals( 713 aZillion.multiply(new BigInteger("3", 10)))); 714 715 assertTrue("0*0", zero.multiply(zero).equals(zero)); 716 assertTrue("0*1", zero.multiply(one).equals(zero)); 717 assertTrue("1*0", one.multiply(zero).equals(zero)); 718 assertTrue("1*1", one.multiply(one).equals(one)); 719 assertTrue("0*(-1)", zero.multiply(minusOne).equals(zero)); 720 assertTrue("(-1)*0", minusOne.multiply(zero).equals(zero)); 721 assertTrue("(-1)*(-1)", minusOne.multiply(minusOne).equals(one)); 722 assertTrue("1*(-1)", one.multiply(minusOne).equals(minusOne)); 723 assertTrue("(-1)*1", minusOne.multiply(one).equals(minusOne)); 724 725 testAllMults(bi1, bi1, bi11); 726 testAllMults(bi2, bi2, bi22); 727 testAllMults(bi3, bi3, bi33); 728 testAllMults(bi1, bi2, bi12); 729 testAllMults(bi1, bi3, bi13); 730 testAllMults(bi2, bi3, bi23); 731 } 732 733 /** 734 * java.math.BigInteger#divide(java.math.BigInteger) 735 */ 736 public void test_divideLjava_math_BigInteger() { 737 testAllDivs(bi33, bi3); 738 testAllDivs(bi22, bi2); 739 testAllDivs(bi11, bi1); 740 testAllDivs(bi13, bi1); 741 testAllDivs(bi13, bi3); 742 testAllDivs(bi12, bi1); 743 testAllDivs(bi12, bi2); 744 testAllDivs(bi23, bi2); 745 testAllDivs(bi23, bi3); 746 testAllDivs(largePos, bi1); 747 testAllDivs(largePos, bi2); 748 testAllDivs(largePos, bi3); 749 testAllDivs(largeNeg, bi1); 750 testAllDivs(largeNeg, bi2); 751 testAllDivs(largeNeg, bi3); 752 testAllDivs(largeNeg, largePos); 753 testAllDivs(largePos, largeNeg); 754 testAllDivs(bi3, bi3); 755 testAllDivs(bi2, bi2); 756 testAllDivs(bi1, bi1); 757 testDivRanges(bi1); 758 testDivRanges(bi2); 759 testDivRanges(bi3); 760 testDivRanges(smallPos); 761 testDivRanges(largePos); 762 testDivRanges(new BigInteger("62EB40FEF85AA9EB", 16)); 763 testAllDivs(BigInteger.valueOf(0xCC0225953CL), BigInteger 764 .valueOf(0x1B937B765L)); 765 766 try { 767 largePos.divide(zero); 768 fail("ArithmeticException expected"); 769 } catch (ArithmeticException e) { 770 } 771 772 try { 773 bi1.divide(zero); 774 fail("ArithmeticException expected"); 775 } catch (ArithmeticException e) { 776 } 777 778 try { 779 bi3.negate().divide(zero); 780 fail("ArithmeticException expected"); 781 } catch (ArithmeticException e) { 782 } 783 784 try { 785 zero.divide(zero); 786 fail("ArithmeticException expected"); 787 } catch (ArithmeticException e) { 788 } 789 } 790 791 /** 792 * java.math.BigInteger#remainder(java.math.BigInteger) 793 */ 794 public void test_remainderLjava_math_BigInteger() { 795 try { 796 largePos.remainder(zero); 797 fail("ArithmeticException expected"); 798 } catch (ArithmeticException e) { 799 } 800 801 try { 802 bi1.remainder(zero); 803 fail("ArithmeticException expected"); 804 } catch (ArithmeticException e) { 805 } 806 807 try { 808 bi3.negate().remainder(zero); 809 fail("ArithmeticException expected"); 810 } catch (ArithmeticException e) { 811 } 812 813 try { 814 zero.remainder(zero); 815 fail("ArithmeticException expected"); 816 } catch (ArithmeticException e) { 817 } 818 } 819 820 /** 821 * java.math.BigInteger#mod(java.math.BigInteger) 822 */ 823 public void test_modLjava_math_BigInteger() { 824 try { 825 largePos.mod(zero); 826 fail("ArithmeticException expected"); 827 } catch (ArithmeticException e) { 828 } 829 830 try { 831 bi1.mod(zero); 832 fail("ArithmeticException expected"); 833 } catch (ArithmeticException e) { 834 } 835 836 try { 837 bi3.negate().mod(zero); 838 fail("ArithmeticException expected"); 839 } catch (ArithmeticException e) { 840 } 841 842 try { 843 zero.mod(zero); 844 fail("ArithmeticException expected"); 845 } catch (ArithmeticException e) { 846 } 847 } 848 849 /** 850 * java.math.BigInteger#divideAndRemainder(java.math.BigInteger) 851 */ 852 public void test_divideAndRemainderLjava_math_BigInteger() { 853 try { 854 largePos.divideAndRemainder(zero); 855 fail("ArithmeticException expected"); 856 } catch (ArithmeticException e) { 857 } 858 859 try { 860 bi1.divideAndRemainder(zero); 861 fail("ArithmeticException expected"); 862 } catch (ArithmeticException e) { 863 } 864 865 try { 866 bi3.negate().divideAndRemainder(zero); 867 fail("ArithmeticException expected"); 868 } catch (ArithmeticException e) { 869 } 870 871 try { 872 zero.divideAndRemainder(zero); 873 fail("ArithmeticException expected"); 874 } catch (ArithmeticException e) { 875 } 876 } 877 878 /** 879 * java.math.BigInteger#BigInteger(java.lang.String) 880 */ 881 public void test_ConstructorLjava_lang_String() { 882 assertTrue("new(0)", new BigInteger("0").equals(BigInteger.valueOf(0))); 883 assertTrue("new(1)", new BigInteger("1").equals(BigInteger.valueOf(1))); 884 assertTrue("new(12345678901234)", new BigInteger("12345678901234") 885 .equals(BigInteger.valueOf(12345678901234L))); 886 assertTrue("new(-1)", new BigInteger("-1").equals(BigInteger 887 .valueOf(-1))); 888 assertTrue("new(-12345678901234)", new BigInteger("-12345678901234") 889 .equals(BigInteger.valueOf(-12345678901234L))); 890 } 891 892 /** 893 * java.math.BigInteger#BigInteger(java.lang.String, int) 894 */ 895 public void test_ConstructorLjava_lang_StringI() { 896 assertTrue("new(0,16)", new BigInteger("0", 16).equals(BigInteger 897 .valueOf(0))); 898 assertTrue("new(1,16)", new BigInteger("1", 16).equals(BigInteger 899 .valueOf(1))); 900 assertTrue("new(ABF345678901234,16)", new BigInteger("ABF345678901234", 901 16).equals(BigInteger.valueOf(0xABF345678901234L))); 902 assertTrue("new(abf345678901234,16)", new BigInteger("abf345678901234", 903 16).equals(BigInteger.valueOf(0xABF345678901234L))); 904 assertTrue("new(-1,16)", new BigInteger("-1", 16).equals(BigInteger 905 .valueOf(-1))); 906 assertTrue("new(-ABF345678901234,16)", new BigInteger( 907 "-ABF345678901234", 16).equals(BigInteger 908 .valueOf(-0xABF345678901234L))); 909 assertTrue("new(-abf345678901234,16)", new BigInteger( 910 "-abf345678901234", 16).equals(BigInteger 911 .valueOf(-0xABF345678901234L))); 912 assertTrue("new(-101010101,2)", new BigInteger("-101010101", 2) 913 .equals(BigInteger.valueOf(-341))); 914 } 915 916 /** 917 * java.math.BigInteger#toString() 918 */ 919 public void test_toString() { 920 assertTrue("0.toString", "0".equals(BigInteger.valueOf(0).toString())); 921 assertTrue("1.toString", "1".equals(BigInteger.valueOf(1).toString())); 922 assertTrue("12345678901234.toString", "12345678901234" 923 .equals(BigInteger.valueOf(12345678901234L).toString())); 924 assertTrue("-1.toString", "-1" 925 .equals(BigInteger.valueOf(-1).toString())); 926 assertTrue("-12345678901234.toString", "-12345678901234" 927 .equals(BigInteger.valueOf(-12345678901234L).toString())); 928 } 929 930 /** 931 * java.math.BigInteger#toString(int) 932 */ 933 public void test_toStringI() { 934 assertTrue("0.toString(16)", "0".equals(BigInteger.valueOf(0).toString( 935 16))); 936 assertTrue("1.toString(16)", "1".equals(BigInteger.valueOf(1).toString( 937 16))); 938 assertTrue("ABF345678901234.toString(16)", "abf345678901234" 939 .equals(BigInteger.valueOf(0xABF345678901234L).toString(16))); 940 assertTrue("-1.toString(16)", "-1".equals(BigInteger.valueOf(-1) 941 .toString(16))); 942 assertTrue("-ABF345678901234.toString(16)", "-abf345678901234" 943 .equals(BigInteger.valueOf(-0xABF345678901234L).toString(16))); 944 assertTrue("-101010101.toString(2)", "-101010101".equals(BigInteger 945 .valueOf(-341).toString(2))); 946 } 947 948 /** 949 * java.math.BigInteger#and(java.math.BigInteger) 950 */ 951 public void test_andLjava_math_BigInteger() { 952 for (BigInteger[] element : booleanPairs) { 953 BigInteger i1 = element[0], i2 = element[1]; 954 BigInteger res = i1.and(i2); 955 assertTrue("symmetry of and", res.equals(i2.and(i1))); 956 int len = Math.max(i1.bitLength(), i2.bitLength()) + 66; 957 for (int i = 0; i < len; i++) { 958 assertTrue("and", (i1.testBit(i) && i2.testBit(i)) == res 959 .testBit(i)); 960 } 961 } 962 } 963 964 /** 965 * java.math.BigInteger#or(java.math.BigInteger) 966 */ 967 public void test_orLjava_math_BigInteger() { 968 for (BigInteger[] element : booleanPairs) { 969 BigInteger i1 = element[0], i2 = element[1]; 970 BigInteger res = i1.or(i2); 971 assertTrue("symmetry of or", res.equals(i2.or(i1))); 972 int len = Math.max(i1.bitLength(), i2.bitLength()) + 66; 973 for (int i = 0; i < len; i++) { 974 assertTrue("or", (i1.testBit(i) || i2.testBit(i)) == res 975 .testBit(i)); 976 } 977 } 978 } 979 980 /** 981 * java.math.BigInteger#xor(java.math.BigInteger) 982 */ 983 public void test_xorLjava_math_BigInteger() { 984 for (BigInteger[] element : booleanPairs) { 985 BigInteger i1 = element[0], i2 = element[1]; 986 BigInteger res = i1.xor(i2); 987 assertTrue("symmetry of xor", res.equals(i2.xor(i1))); 988 int len = Math.max(i1.bitLength(), i2.bitLength()) + 66; 989 for (int i = 0; i < len; i++) { 990 assertTrue("xor", (i1.testBit(i) ^ i2.testBit(i)) == res 991 .testBit(i)); 992 } 993 } 994 } 995 996 /** 997 * java.math.BigInteger#not() 998 */ 999 public void test_not() { 1000 for (BigInteger[] element : booleanPairs) { 1001 BigInteger i1 = element[0]; 1002 BigInteger res = i1.not(); 1003 int len = i1.bitLength() + 66; 1004 for (int i = 0; i < len; i++) { 1005 assertTrue("not", !i1.testBit(i) == res.testBit(i)); 1006 } 1007 } 1008 } 1009 1010 /** 1011 * java.math.BigInteger#andNot(java.math.BigInteger) 1012 */ 1013 public void test_andNotLjava_math_BigInteger() { 1014 for (BigInteger[] element : booleanPairs) { 1015 BigInteger i1 = element[0], i2 = element[1]; 1016 BigInteger res = i1.andNot(i2); 1017 int len = Math.max(i1.bitLength(), i2.bitLength()) + 66; 1018 for (int i = 0; i < len; i++) { 1019 assertTrue("andNot", (i1.testBit(i) && !i2.testBit(i)) == res 1020 .testBit(i)); 1021 } 1022 // asymmetrical 1023 i1 = element[1]; 1024 i2 = element[0]; 1025 res = i1.andNot(i2); 1026 for (int i = 0; i < len; i++) { 1027 assertTrue("andNot reversed", 1028 (i1.testBit(i) && !i2.testBit(i)) == res.testBit(i)); 1029 } 1030 } 1031 1032 //regression for HARMONY-4653 1033 try{ 1034 BigInteger.ZERO.andNot(null); 1035 fail("should throw NPE"); 1036 }catch(Exception e){ 1037 //expected 1038 } 1039 BigInteger bi = new BigInteger(0, new byte[]{}); 1040 assertEquals(BigInteger.ZERO, bi.andNot(BigInteger.ZERO)); 1041 } 1042 1043 1044 public void testClone() { 1045 // Regression test for HARMONY-1770 1046 MyBigInteger myBigInteger = new MyBigInteger("12345"); 1047 myBigInteger = (MyBigInteger) myBigInteger.clone(); 1048 } 1049 1050 static class MyBigInteger extends BigInteger implements Cloneable { 1051 public MyBigInteger(String val) { 1052 super(val); 1053 } 1054 public Object clone() { 1055 try { 1056 return super.clone(); 1057 } catch (CloneNotSupportedException e) { 1058 throw new AssertionError(e); // android-changed 1059 } 1060 } 1061 } 1062 1063 @Override 1064 protected void setUp() { 1065 bi1 = new BigInteger("2436798324768978", 16); 1066 bi2 = new BigInteger("4576829475724387584378543764555", 16); 1067 bi3 = new BigInteger("43987298363278574365732645872643587624387563245", 1068 16); 1069 1070 bi33 = new BigInteger( 1071 "10730846694701319120609898625733976090865327544790136667944805934175543888691400559249041094474885347922769807001", 1072 10); 1073 bi22 = new BigInteger( 1074 "33301606932171509517158059487795669025817912852219962782230629632224456249", 1075 10); 1076 bi11 = new BigInteger("6809003003832961306048761258711296064", 10); 1077 bi23 = new BigInteger( 1078 "597791300268191573513888045771594235932809890963138840086083595706565695943160293610527214057", 1079 10); 1080 bi13 = new BigInteger( 1081 "270307912162948508387666703213038600031041043966215279482940731158968434008", 1082 10); 1083 bi12 = new BigInteger( 1084 "15058244971895641717453176477697767050482947161656458456", 10); 1085 1086 largePos = new BigInteger( 1087 "834759814379857314986743298675687569845986736578576375675678998612743867438632986243982098437620983476924376", 1088 16); 1089 smallPos = new BigInteger("48753269875973284765874598630960986276", 16); 1090 largeNeg = new BigInteger( 1091 "-878824397432651481891353247987891423768534321387864361143548364457698487264387568743568743265873246576467643756437657436587436", 1092 16); 1093 smallNeg = new BigInteger("-567863254343798609857456273458769843", 16); 1094 booleanPairs = new BigInteger[][] { { largePos, smallPos }, 1095 { largePos, smallNeg }, { largeNeg, smallPos }, 1096 { largeNeg, smallNeg } }; 1097 } 1098 1099 private void testDiv(BigInteger i1, BigInteger i2) { 1100 BigInteger q = i1.divide(i2); 1101 BigInteger r = i1.remainder(i2); 1102 BigInteger[] temp = i1.divideAndRemainder(i2); 1103 1104 assertTrue("divide and divideAndRemainder do not agree", q 1105 .equals(temp[0])); 1106 assertTrue("remainder and divideAndRemainder do not agree", r 1107 .equals(temp[1])); 1108 assertTrue("signum and equals(zero) do not agree on quotient", q 1109 .signum() != 0 1110 || q.equals(zero)); 1111 assertTrue("signum and equals(zero) do not agree on remainder", r 1112 .signum() != 0 1113 || r.equals(zero)); 1114 assertTrue("wrong sign on quotient", q.signum() == 0 1115 || q.signum() == i1.signum() * i2.signum()); 1116 assertTrue("wrong sign on remainder", r.signum() == 0 1117 || r.signum() == i1.signum()); 1118 assertTrue("remainder out of range", r.abs().compareTo(i2.abs()) < 0); 1119 assertTrue("quotient too small", q.abs().add(one).multiply(i2.abs()) 1120 .compareTo(i1.abs()) > 0); 1121 assertTrue("quotient too large", q.abs().multiply(i2.abs()).compareTo( 1122 i1.abs()) <= 0); 1123 BigInteger p = q.multiply(i2); 1124 BigInteger a = p.add(r); 1125 assertTrue("(a/b)*b+(a%b) != a", a.equals(i1)); 1126 try { 1127 BigInteger mod = i1.mod(i2); 1128 assertTrue("mod is negative", mod.signum() >= 0); 1129 assertTrue("mod out of range", mod.abs().compareTo(i2.abs()) < 0); 1130 assertTrue("positive remainder == mod", r.signum() < 0 1131 || r.equals(mod)); 1132 assertTrue("negative remainder == mod - divisor", r.signum() >= 0 1133 || r.equals(mod.subtract(i2))); 1134 } catch (ArithmeticException e) { 1135 assertTrue("mod fails on negative divisor only", i2.signum() <= 0); 1136 } 1137 } 1138 1139 private void testDivRanges(BigInteger i) { 1140 BigInteger bound = i.multiply(two); 1141 for (BigInteger j = bound.negate(); j.compareTo(bound) <= 0; j = j 1142 .add(i)) { 1143 BigInteger innerbound = j.add(two); 1144 BigInteger k = j.subtract(two); 1145 for (; k.compareTo(innerbound) <= 0; k = k.add(one)) { 1146 testDiv(k, i); 1147 } 1148 } 1149 } 1150 1151 private boolean isPrime(long b) { 1152 if (b == 2) { 1153 return true; 1154 } 1155 // check for div by 2 1156 if ((b & 1L) == 0) { 1157 return false; 1158 } 1159 long maxlen = ((long) Math.sqrt(b)) + 2; 1160 for (long x = 3; x < maxlen; x += 2) { 1161 if (b % x == 0) { 1162 return false; 1163 } 1164 } 1165 return true; 1166 } 1167 1168 private void testAllMults(BigInteger i1, BigInteger i2, BigInteger ans) { 1169 assertTrue("i1*i2=ans", i1.multiply(i2).equals(ans)); 1170 assertTrue("i2*i1=ans", i2.multiply(i1).equals(ans)); 1171 assertTrue("-i1*i2=-ans", i1.negate().multiply(i2).equals(ans.negate())); 1172 assertTrue("-i2*i1=-ans", i2.negate().multiply(i1).equals(ans.negate())); 1173 assertTrue("i1*-i2=-ans", i1.multiply(i2.negate()).equals(ans.negate())); 1174 assertTrue("i2*-i1=-ans", i2.multiply(i1.negate()).equals(ans.negate())); 1175 assertTrue("-i1*-i2=ans", i1.negate().multiply(i2.negate()).equals(ans)); 1176 assertTrue("-i2*-i1=ans", i2.negate().multiply(i1.negate()).equals(ans)); 1177 } 1178 1179 private void testAllDivs(BigInteger i1, BigInteger i2) { 1180 testDiv(i1, i2); 1181 testDiv(i1.negate(), i2); 1182 testDiv(i1, i2.negate()); 1183 testDiv(i1.negate(), i2.negate()); 1184 } 1185} 1186