1 /* 2 * Copyright (c) 1996, 2013, 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 /* 27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved. 28 */ 29 30 package java.math; 31 32 import java.io.IOException; 33 import java.io.ObjectInputStream; 34 import java.io.ObjectOutputStream; 35 import java.io.ObjectStreamField; 36 import java.util.Arrays; 37 import java.util.Random; 38 39 /** 40 * Immutable arbitrary-precision integers. All operations behave as if 41 * BigIntegers were represented in two's-complement notation (like Java's 42 * primitive integer types). BigInteger provides analogues to all of Java's 43 * primitive integer operators, and all relevant methods from java.lang.Math. 44 * Additionally, BigInteger provides operations for modular arithmetic, GCD 45 * calculation, primality testing, prime generation, bit manipulation, 46 * and a few other miscellaneous operations. 47 * 48 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer 49 * arithmetic operators, as defined in <i>The Java Language Specification</i>. 50 * For example, division by zero throws an {@code ArithmeticException}, and 51 * division of a negative by a positive yields a negative (or zero) remainder. 52 * All of the details in the Spec concerning overflow are ignored, as 53 * BigIntegers are made as large as necessary to accommodate the results of an 54 * operation. 55 * 56 * <p>Semantics of shift operations extend those of Java's shift operators 57 * to allow for negative shift distances. A right-shift with a negative 58 * shift distance results in a left shift, and vice-versa. The unsigned 59 * right shift operator ({@code >>>}) is omitted, as this operation makes 60 * little sense in combination with the "infinite word size" abstraction 61 * provided by this class. 62 * 63 * <p>Semantics of bitwise logical operations exactly mimic those of Java's 64 * bitwise integer operators. The binary operators ({@code and}, 65 * {@code or}, {@code xor}) implicitly perform sign extension on the shorter 66 * of the two operands prior to performing the operation. 67 * 68 * <p>Comparison operations perform signed integer comparisons, analogous to 69 * those performed by Java's relational and equality operators. 70 * 71 * <p>Modular arithmetic operations are provided to compute residues, perform 72 * exponentiation, and compute multiplicative inverses. These methods always 73 * return a non-negative result, between {@code 0} and {@code (modulus - 1)}, 74 * inclusive. 75 * 76 * <p>Bit operations operate on a single bit of the two's-complement 77 * representation of their operand. If necessary, the operand is sign- 78 * extended so that it contains the designated bit. None of the single-bit 79 * operations can produce a BigInteger with a different sign from the 80 * BigInteger being operated on, as they affect only a single bit, and the 81 * "infinite word size" abstraction provided by this class ensures that there 82 * are infinitely many "virtual sign bits" preceding each BigInteger. 83 * 84 * <p>For the sake of brevity and clarity, pseudo-code is used throughout the 85 * descriptions of BigInteger methods. The pseudo-code expression 86 * {@code (i + j)} is shorthand for "a BigInteger whose value is 87 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}." 88 * The pseudo-code expression {@code (i == j)} is shorthand for 89 * "{@code true} if and only if the BigInteger {@code i} represents the same 90 * value as the BigInteger {@code j}." Other pseudo-code expressions are 91 * interpreted similarly. 92 * 93 * <p>All methods and constructors in this class throw 94 * {@code NullPointerException} when passed 95 * a null object reference for any input parameter. 96 * 97 * @see BigDecimal 98 * @author Josh Bloch 99 * @author Michael McCloskey 100 * @author Alan Eliasen 101 * @since JDK1.1 102 */ 103 104 public class BigInteger extends Number implements Comparable<BigInteger> { 105 /** 106 * The signum of this BigInteger: -1 for negative, 0 for zero, or 107 * 1 for positive. Note that the BigInteger zero <i>must</i> have 108 * a signum of 0. This is necessary to ensures that there is exactly one 109 * representation for each BigInteger value. 110 * 111 * @serial 112 */ 113 final int signum; 114 115 /** 116 * The magnitude of this BigInteger, in <i>big-endian</i> order: the 117 * zeroth element of this array is the most-significant int of the 118 * magnitude. The magnitude must be "minimal" in that the most-significant 119 * int ({@code mag[0]}) must be non-zero. This is necessary to 120 * ensure that there is exactly one representation for each BigInteger 121 * value. Note that this implies that the BigInteger zero has a 122 * zero-length mag array. 123 */ 124 final int[] mag; 125 126 // These "redundant fields" are initialized with recognizable nonsense 127 // values, and cached the first time they are needed (or never, if they 128 // aren't needed). 129 130 /** 131 * One plus the bitCount of this BigInteger. Zeros means unitialized. 132 * 133 * @serial 134 * @see #bitCount 135 * @deprecated Deprecated since logical value is offset from stored 136 * value and correction factor is applied in accessor method. 137 */ 138 @Deprecated 139 private int bitCount; 140 141 /** 142 * One plus the bitLength of this BigInteger. Zeros means unitialized. 143 * (either value is acceptable). 144 * 145 * @serial 146 * @see #bitLength() 147 * @deprecated Deprecated since logical value is offset from stored 148 * value and correction factor is applied in accessor method. 149 */ 150 @Deprecated 151 private int bitLength; 152 153 /** 154 * Two plus the lowest set bit of this BigInteger, as returned by 155 * getLowestSetBit(). 156 * 157 * @serial 158 * @see #getLowestSetBit 159 * @deprecated Deprecated since logical value is offset from stored 160 * value and correction factor is applied in accessor method. 161 */ 162 @Deprecated 163 private int lowestSetBit; 164 165 /** 166 * Two plus the index of the lowest-order int in the magnitude of this 167 * BigInteger that contains a nonzero int, or -2 (either value is acceptable). 168 * The least significant int has int-number 0, the next int in order of 169 * increasing significance has int-number 1, and so forth. 170 * @deprecated Deprecated since logical value is offset from stored 171 * value and correction factor is applied in accessor method. 172 */ 173 @Deprecated 174 private int firstNonzeroIntNum; 175 176 /** 177 * This mask is used to obtain the value of an int as if it were unsigned. 178 */ 179 final static long LONG_MASK = 0xffffffffL; 180 181 /** 182 * The threshold value for using Karatsuba multiplication. If the number 183 * of ints in both mag arrays are greater than this number, then 184 * Karatsuba multiplication will be used. This value is found 185 * experimentally to work well. 186 */ 187 private static final int KARATSUBA_THRESHOLD = 50; 188 189 /** 190 * The threshold value for using 3-way Toom-Cook multiplication. 191 * If the number of ints in each mag array is greater than the 192 * Karatsuba threshold, and the number of ints in at least one of 193 * the mag arrays is greater than this threshold, then Toom-Cook 194 * multiplication will be used. 195 */ 196 private static final int TOOM_COOK_THRESHOLD = 75; 197 198 /** 199 * The threshold value for using Karatsuba squaring. If the number 200 * of ints in the number are larger than this value, 201 * Karatsuba squaring will be used. This value is found 202 * experimentally to work well. 203 */ 204 private static final int KARATSUBA_SQUARE_THRESHOLD = 90; 205 206 /** 207 * The threshold value for using Toom-Cook squaring. If the number 208 * of ints in the number are larger than this value, 209 * Toom-Cook squaring will be used. This value is found 210 * experimentally to work well. 211 */ 212 private static final int TOOM_COOK_SQUARE_THRESHOLD = 140; 213 214 //Constructors 215 216 /** 217 * Translates a byte array containing the two's-complement binary 218 * representation of a BigInteger into a BigInteger. The input array is 219 * assumed to be in <i>big-endian</i> byte-order: the most significant 220 * byte is in the zeroth element. 221 * 222 * @param val big-endian two's-complement binary representation of 223 * BigInteger. 224 * @throws NumberFormatException {@code val} is zero bytes long. 225 */ 226 public BigInteger(byte[] val) { 227 if (val.length == 0) 228 throw new NumberFormatException("Zero length BigInteger"); 229 230 if (val[0] < 0) { 231 mag = makePositive(val); 232 signum = -1; 233 } else { 234 mag = stripLeadingZeroBytes(val); 235 signum = (mag.length == 0 ? 0 : 1); 236 } 237 } 238 239 /** 240 * This private constructor translates an int array containing the 241 * two's-complement binary representation of a BigInteger into a 242 * BigInteger. The input array is assumed to be in <i>big-endian</i> 243 * int-order: the most significant int is in the zeroth element. 244 */ 245 private BigInteger(int[] val) { 246 if (val.length == 0) 247 throw new NumberFormatException("Zero length BigInteger"); 248 249 if (val[0] < 0) { 250 mag = makePositive(val); 251 signum = -1; 252 } else { 253 mag = trustedStripLeadingZeroInts(val); 254 signum = (mag.length == 0 ? 0 : 1); 255 } 256 } 257 258 /** 259 * Translates the sign-magnitude representation of a BigInteger into a 260 * BigInteger. The sign is represented as an integer signum value: -1 for 261 * negative, 0 for zero, or 1 for positive. The magnitude is a byte array 262 * in <i>big-endian</i> byte-order: the most significant byte is in the 263 * zeroth element. A zero-length magnitude array is permissible, and will 264 * result in a BigInteger value of 0, whether signum is -1, 0 or 1. 265 * 266 * @param signum signum of the number (-1 for negative, 0 for zero, 1 267 * for positive). 268 * @param magnitude big-endian binary representation of the magnitude of 269 * the number. 270 * @throws NumberFormatException {@code signum} is not one of the three 271 * legal values (-1, 0, and 1), or {@code signum} is 0 and 272 * {@code magnitude} contains one or more non-zero bytes. 273 */ 274 public BigInteger(int signum, byte[] magnitude) { 275 this.mag = stripLeadingZeroBytes(magnitude); 276 277 if (signum < -1 || signum > 1) 278 throw(new NumberFormatException("Invalid signum value")); 279 280 if (this.mag.length==0) { 281 this.signum = 0; 282 } else { 283 if (signum == 0) 284 throw(new NumberFormatException("signum-magnitude mismatch")); 285 this.signum = signum; 286 } 287 } 288 289 /** 290 * A constructor for internal use that translates the sign-magnitude 291 * representation of a BigInteger into a BigInteger. It checks the 292 * arguments and copies the magnitude so this constructor would be 293 * safe for external use. 294 */ 295 private BigInteger(int signum, int[] magnitude) { 296 this.mag = stripLeadingZeroInts(magnitude); 297 298 if (signum < -1 || signum > 1) 299 throw(new NumberFormatException("Invalid signum value")); 300 301 if (this.mag.length==0) { 302 this.signum = 0; 303 } else { 304 if (signum == 0) 305 throw(new NumberFormatException("signum-magnitude mismatch")); 306 this.signum = signum; 307 } 308 } 309 310 /** 311 * Translates the String representation of a BigInteger in the 312 * specified radix into a BigInteger. The String representation 313 * consists of an optional minus or plus sign followed by a 314 * sequence of one or more digits in the specified radix. The 315 * character-to-digit mapping is provided by {@code 316 * Character.digit}. The String may not contain any extraneous 317 * characters (whitespace, for example). 318 * 319 * @param val String representation of BigInteger. 320 * @param radix radix to be used in interpreting {@code val}. 321 * @throws NumberFormatException {@code val} is not a valid representation 322 * of a BigInteger in the specified radix, or {@code radix} is 323 * outside the range from {@link Character#MIN_RADIX} to 324 * {@link Character#MAX_RADIX}, inclusive. 325 * @see Character#digit 326 */ 327 public BigInteger(String val, int radix) { 328 int cursor = 0, numDigits; 329 final int len = val.length(); 330 331 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) 332 throw new NumberFormatException("Radix out of range"); 333 if (len == 0) 334 throw new NumberFormatException("Zero length BigInteger"); 335 336 // Check for at most one leading sign 337 int sign = 1; 338 int index1 = val.lastIndexOf('-'); 339 int index2 = val.lastIndexOf('+'); 340 if ((index1 + index2) <= -1) { 341 // No leading sign character or at most one leading sign character 342 if (index1 == 0 || index2 == 0) { 343 cursor = 1; 344 if (len == 1) 345 throw new NumberFormatException("Zero length BigInteger"); 346 } 347 if (index1 == 0) 348 sign = -1; 349 } else 350 throw new NumberFormatException("Illegal embedded sign character"); 351 352 // Skip leading zeros and compute number of digits in magnitude 353 while (cursor < len && 354 Character.digit(val.charAt(cursor), radix) == 0) 355 cursor++; 356 if (cursor == len) { 357 signum = 0; 358 mag = ZERO.mag; 359 return; 360 } 361 362 numDigits = len - cursor; 363 signum = sign; 364 365 // Pre-allocate array of expected size. May be too large but can 366 // never be too small. Typically exact. 367 int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1); 368 int numWords = (numBits + 31) >>> 5; 369 int[] magnitude = new int[numWords]; 370 371 // Process first (potentially short) digit group 372 int firstGroupLen = numDigits % digitsPerInt[radix]; 373 if (firstGroupLen == 0) 374 firstGroupLen = digitsPerInt[radix]; 375 String group = val.substring(cursor, cursor += firstGroupLen); 376 magnitude[numWords - 1] = Integer.parseInt(group, radix); 377 if (magnitude[numWords - 1] < 0) 378 throw new NumberFormatException("Illegal digit"); 379 380 // Process remaining digit groups 381 int superRadix = intRadix[radix]; 382 int groupVal = 0; 383 while (cursor < len) { 384 group = val.substring(cursor, cursor += digitsPerInt[radix]); 385 groupVal = Integer.parseInt(group, radix); 386 if (groupVal < 0) 387 throw new NumberFormatException("Illegal digit"); 388 destructiveMulAdd(magnitude, superRadix, groupVal); 389 } 390 // Required for cases where the array was overallocated. 391 mag = trustedStripLeadingZeroInts(magnitude); 392 } 393 394 /* 395 * Constructs a new BigInteger using a char array with radix=10. 396 * Sign is precalculated outside and not allowed in the val. 397 */ 398 BigInteger(char[] val, int sign, int len) { 399 int cursor = 0, numDigits; 400 401 // Skip leading zeros and compute number of digits in magnitude 402 while (cursor < len && Character.digit(val[cursor], 10) == 0) { 403 cursor++; 404 } 405 if (cursor == len) { 406 signum = 0; 407 mag = ZERO.mag; 408 return; 409 } 410 411 numDigits = len - cursor; 412 signum = sign; 413 // Pre-allocate array of expected size 414 int numWords; 415 if (len < 10) { 416 numWords = 1; 417 } else { 418 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1); 419 numWords = (numBits + 31) >>> 5; 420 } 421 int[] magnitude = new int[numWords]; 422 423 // Process first (potentially short) digit group 424 int firstGroupLen = numDigits % digitsPerInt[10]; 425 if (firstGroupLen == 0) 426 firstGroupLen = digitsPerInt[10]; 427 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen); 428 429 // Process remaining digit groups 430 while (cursor < len) { 431 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]); 432 destructiveMulAdd(magnitude, intRadix[10], groupVal); 433 } 434 mag = trustedStripLeadingZeroInts(magnitude); 435 } 436 437 // Create an integer with the digits between the two indexes 438 // Assumes start < end. The result may be negative, but it 439 // is to be treated as an unsigned value. 440 private int parseInt(char[] source, int start, int end) { 441 int result = Character.digit(source[start++], 10); 442 if (result == -1) 443 throw new NumberFormatException(new String(source)); 444 445 for (int index = start; index<end; index++) { 446 int nextVal = Character.digit(source[index], 10); 447 if (nextVal == -1) 448 throw new NumberFormatException(new String(source)); 449 result = 10*result + nextVal; 450 } 451 452 return result; 453 } 454 455 // bitsPerDigit in the given radix times 1024 456 // Rounded up to avoid underallocation. 457 private static long bitsPerDigit[] = { 0, 0, 458 1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672, 459 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633, 460 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210, 461 5253, 5295}; 462 463 // Multiply x array times word y in place, and add word z 464 private static void destructiveMulAdd(int[] x, int y, int z) { 465 // Perform the multiplication word by word 466 long ylong = y & LONG_MASK; 467 long zlong = z & LONG_MASK; 468 int len = x.length; 469 470 long product = 0; 471 long carry = 0; 472 for (int i = len-1; i >= 0; i--) { 473 product = ylong * (x[i] & LONG_MASK) + carry; 474 x[i] = (int)product; 475 carry = product >>> 32; 476 } 477 478 // Perform the addition 479 long sum = (x[len-1] & LONG_MASK) + zlong; 480 x[len-1] = (int)sum; 481 carry = sum >>> 32; 482 for (int i = len-2; i >= 0; i--) { 483 sum = (x[i] & LONG_MASK) + carry; 484 x[i] = (int)sum; 485 carry = sum >>> 32; 486 } 487 } 488 489 /** 490 * Translates the decimal String representation of a BigInteger into a 491 * BigInteger. The String representation consists of an optional minus 492 * sign followed by a sequence of one or more decimal digits. The 493 * character-to-digit mapping is provided by {@code Character.digit}. 494 * The String may not contain any extraneous characters (whitespace, for 495 * example). 496 * 497 * @param val decimal String representation of BigInteger. 498 * @throws NumberFormatException {@code val} is not a valid representation 499 * of a BigInteger. 500 * @see Character#digit 501 */ 502 public BigInteger(String val) { 503 this(val, 10); 504 } 505 506 /** 507 * Constructs a randomly generated BigInteger, uniformly distributed over 508 * the range 0 to (2<sup>{@code numBits}</sup> - 1), inclusive. 509 * The uniformity of the distribution assumes that a fair source of random 510 * bits is provided in {@code rnd}. Note that this constructor always 511 * constructs a non-negative BigInteger. 512 * 513 * @param numBits maximum bitLength of the new BigInteger. 514 * @param rnd source of randomness to be used in computing the new 515 * BigInteger. 516 * @throws IllegalArgumentException {@code numBits} is negative. 517 * @see #bitLength() 518 */ 519 public BigInteger(int numBits, Random rnd) { 520 this(1, randomBits(numBits, rnd)); 521 } 522 523 private static byte[] randomBits(int numBits, Random rnd) { 524 if (numBits < 0) 525 throw new IllegalArgumentException("numBits must be non-negative"); 526 int numBytes = (int)(((long)numBits+7)/8); // avoid overflow 527 byte[] randomBits = new byte[numBytes]; 528 529 // Generate random bytes and mask out any excess bits 530 if (numBytes > 0) { 531 rnd.nextBytes(randomBits); 532 int excessBits = 8*numBytes - numBits; 533 randomBits[0] &= (1 << (8-excessBits)) - 1; 534 } 535 return randomBits; 536 } 537 538 /** 539 * Constructs a randomly generated positive BigInteger that is probably 540 * prime, with the specified bitLength. 541 * 542 * <p>It is recommended that the {@link #probablePrime probablePrime} 543 * method be used in preference to this constructor unless there 544 * is a compelling need to specify a certainty. 545 * 546 * @param bitLength bitLength of the returned BigInteger. 547 * @param certainty a measure of the uncertainty that the caller is 548 * willing to tolerate. The probability that the new BigInteger 549 * represents a prime number will exceed 550 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of 551 * this constructor is proportional to the value of this parameter. 552 * @param rnd source of random bits used to select candidates to be 553 * tested for primality. 554 * @throws ArithmeticException {@code bitLength < 2}. 555 * @see #bitLength() 556 */ 557 public BigInteger(int bitLength, int certainty, Random rnd) { 558 BigInteger prime; 559 560 if (bitLength < 2) 561 throw new ArithmeticException("bitLength < 2"); 562 prime = (bitLength < SMALL_PRIME_THRESHOLD 563 ? smallPrime(bitLength, certainty, rnd) 564 : largePrime(bitLength, certainty, rnd)); 565 signum = 1; 566 mag = prime.mag; 567 } 568 569 // Minimum size in bits that the requested prime number has 570 // before we use the large prime number generating algorithms. 571 // The cutoff of 95 was chosen empirically for best performance. 572 private static final int SMALL_PRIME_THRESHOLD = 95; 573 574 // Certainty required to meet the spec of probablePrime 575 private static final int DEFAULT_PRIME_CERTAINTY = 100; 576 577 /** 578 * Returns a positive BigInteger that is probably prime, with the 579 * specified bitLength. The probability that a BigInteger returned 580 * by this method is composite does not exceed 2<sup>-100</sup>. 581 * 582 * @param bitLength bitLength of the returned BigInteger. 583 * @param rnd source of random bits used to select candidates to be 584 * tested for primality. 585 * @return a BigInteger of {@code bitLength} bits that is probably prime 586 * @throws ArithmeticException {@code bitLength < 2}. 587 * @see #bitLength() 588 * @since 1.4 589 */ 590 public static BigInteger probablePrime(int bitLength, Random rnd) { 591 if (bitLength < 2) 592 throw new ArithmeticException("bitLength < 2"); 593 594 return (bitLength < SMALL_PRIME_THRESHOLD ? 595 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) : 596 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd)); 597 } 598 599 /** 600 * Find a random number of the specified bitLength that is probably prime. 601 * This method is used for smaller primes, its performance degrades on 602 * larger bitlengths. 603 * 604 * This method assumes bitLength > 1. 605 */ 606 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) { 607 int magLen = (bitLength + 31) >>> 5; 608 int temp[] = new int[magLen]; 609 int highBit = 1 << ((bitLength+31) & 0x1f); // High bit of high int 610 int highMask = (highBit << 1) - 1; // Bits to keep in high int 611 612 while(true) { 613 // Construct a candidate 614 for (int i=0; i<magLen; i++) 615 temp[i] = rnd.nextInt(); 616 temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length 617 if (bitLength > 2) 618 temp[magLen-1] |= 1; // Make odd if bitlen > 2 619 620 BigInteger p = new BigInteger(temp, 1); 621 622 // Do cheap "pre-test" if applicable 623 if (bitLength > 6) { 624 long r = p.remainder(SMALL_PRIME_PRODUCT).longValue(); 625 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) || 626 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 627 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) 628 continue; // Candidate is composite; try another 629 } 630 631 // All candidates of bitLength 2 and 3 are prime by this point 632 if (bitLength < 4) 633 return p; 634 635 // Do expensive test if we survive pre-test (or it's inapplicable) 636 if (p.primeToCertainty(certainty, rnd)) 637 return p; 638 } 639 } 640 641 private static final BigInteger SMALL_PRIME_PRODUCT 642 = valueOf(3L*5*7*11*13*17*19*23*29*31*37*41); 643 644 /** 645 * Find a random number of the specified bitLength that is probably prime. 646 * This method is more appropriate for larger bitlengths since it uses 647 * a sieve to eliminate most composites before using a more expensive 648 * test. 649 */ 650 private static BigInteger largePrime(int bitLength, int certainty, Random rnd) { 651 BigInteger p; 652 p = new BigInteger(bitLength, rnd).setBit(bitLength-1); 653 p.mag[p.mag.length-1] &= 0xfffffffe; 654 655 // Use a sieve length likely to contain the next prime number 656 int searchLen = (bitLength / 20) * 64; 657 BitSieve searchSieve = new BitSieve(p, searchLen); 658 BigInteger candidate = searchSieve.retrieve(p, certainty, rnd); 659 660 while ((candidate == null) || (candidate.bitLength() != bitLength)) { 661 p = p.add(BigInteger.valueOf(2*searchLen)); 662 if (p.bitLength() != bitLength) 663 p = new BigInteger(bitLength, rnd).setBit(bitLength-1); 664 p.mag[p.mag.length-1] &= 0xfffffffe; 665 searchSieve = new BitSieve(p, searchLen); 666 candidate = searchSieve.retrieve(p, certainty, rnd); 667 } 668 return candidate; 669 } 670 671 /** 672 * Returns the first integer greater than this {@code BigInteger} that 673 * is probably prime. The probability that the number returned by this 674 * method is composite does not exceed 2<sup>-100</sup>. This method will 675 * never skip over a prime when searching: if it returns {@code p}, there 676 * is no prime {@code q} such that {@code this < q < p}. 677 * 678 * @return the first integer greater than this {@code BigInteger} that 679 * is probably prime. 680 * @throws ArithmeticException {@code this < 0}. 681 * @since 1.5 682 */ 683 public BigInteger nextProbablePrime() { 684 if (this.signum < 0) 685 throw new ArithmeticException("start < 0: " + this); 686 687 // Handle trivial cases 688 if ((this.signum == 0) || this.equals(ONE)) 689 return TWO; 690 691 BigInteger result = this.add(ONE); 692 693 // Fastpath for small numbers 694 if (result.bitLength() < SMALL_PRIME_THRESHOLD) { 695 696 // Ensure an odd number 697 if (!result.testBit(0)) 698 result = result.add(ONE); 699 700 while(true) { 701 // Do cheap "pre-test" if applicable 702 if (result.bitLength() > 6) { 703 long r = result.remainder(SMALL_PRIME_PRODUCT).longValue(); 704 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) || 705 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 706 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) { 707 result = result.add(TWO); 708 continue; // Candidate is composite; try another 709 } 710 } 711 712 // All candidates of bitLength 2 and 3 are prime by this point 713 if (result.bitLength() < 4) 714 return result; 715 716 // The expensive test 717 if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null)) 718 return result; 719 720 result = result.add(TWO); 721 } 722 } 723 724 // Start at previous even number 725 if (result.testBit(0)) 726 result = result.subtract(ONE); 727 728 // Looking for the next large prime 729 int searchLen = (result.bitLength() / 20) * 64; 730 731 while(true) { 732 BitSieve searchSieve = new BitSieve(result, searchLen); 733 BigInteger candidate = searchSieve.retrieve(result, 734 DEFAULT_PRIME_CERTAINTY, null); 735 if (candidate != null) 736 return candidate; 737 result = result.add(BigInteger.valueOf(2 * searchLen)); 738 } 739 } 740 741 /** 742 * Returns {@code true} if this BigInteger is probably prime, 743 * {@code false} if it's definitely composite. 744 * 745 * This method assumes bitLength > 2. 746 * 747 * @param certainty a measure of the uncertainty that the caller is 748 * willing to tolerate: if the call returns {@code true} 749 * the probability that this BigInteger is prime exceeds 750 * {@code (1 - 1/2<sup>certainty</sup>)}. The execution time of 751 * this method is proportional to the value of this parameter. 752 * @return {@code true} if this BigInteger is probably prime, 753 * {@code false} if it's definitely composite. 754 */ 755 boolean primeToCertainty(int certainty, Random random) { 756 int rounds = 0; 757 int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2; 758 759 // The relationship between the certainty and the number of rounds 760 // we perform is given in the draft standard ANSI X9.80, "PRIME 761 // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES". 762 int sizeInBits = this.bitLength(); 763 if (sizeInBits < 100) { 764 rounds = 50; 765 rounds = n < rounds ? n : rounds; 766 return passesMillerRabin(rounds, random); 767 } 768 769 if (sizeInBits < 256) { 770 rounds = 27; 771 } else if (sizeInBits < 512) { 772 rounds = 15; 773 } else if (sizeInBits < 768) { 774 rounds = 8; 775 } else if (sizeInBits < 1024) { 776 rounds = 4; 777 } else { 778 rounds = 2; 779 } 780 rounds = n < rounds ? n : rounds; 781 782 return passesMillerRabin(rounds, random) && passesLucasLehmer(); 783 } 784 785 /** 786 * Returns true iff this BigInteger is a Lucas-Lehmer probable prime. 787 * 788 * The following assumptions are made: 789 * This BigInteger is a positive, odd number. 790 */ 791 private boolean passesLucasLehmer() { 792 BigInteger thisPlusOne = this.add(ONE); 793 794 // Step 1 795 int d = 5; 796 while (jacobiSymbol(d, this) != -1) { 797 // 5, -7, 9, -11, ... 798 d = (d<0) ? Math.abs(d)+2 : -(d+2); 799 } 800 801 // Step 2 802 BigInteger u = lucasLehmerSequence(d, thisPlusOne, this); 803 804 // Step 3 805 return u.mod(this).equals(ZERO); 806 } 807 808 /** 809 * Computes Jacobi(p,n). 810 * Assumes n positive, odd, n>=3. 811 */ 812 private static int jacobiSymbol(int p, BigInteger n) { 813 if (p == 0) 814 return 0; 815 816 // Algorithm and comments adapted from Colin Plumb's C library. 817 int j = 1; 818 int u = n.mag[n.mag.length-1]; 819 820 // Make p positive 821 if (p < 0) { 822 p = -p; 823 int n8 = u & 7; 824 if ((n8 == 3) || (n8 == 7)) 825 j = -j; // 3 (011) or 7 (111) mod 8 826 } 827 828 // Get rid of factors of 2 in p 829 while ((p & 3) == 0) 830 p >>= 2; 831 if ((p & 1) == 0) { 832 p >>= 1; 833 if (((u ^ (u>>1)) & 2) != 0) 834 j = -j; // 3 (011) or 5 (101) mod 8 835 } 836 if (p == 1) 837 return j; 838 // Then, apply quadratic reciprocity 839 if ((p & u & 2) != 0) // p = u = 3 (mod 4)? 840 j = -j; 841 // And reduce u mod p 842 u = n.mod(BigInteger.valueOf(p)).intValue(); 843 844 // Now compute Jacobi(u,p), u < p 845 while (u != 0) { 846 while ((u & 3) == 0) 847 u >>= 2; 848 if ((u & 1) == 0) { 849 u >>= 1; 850 if (((p ^ (p>>1)) & 2) != 0) 851 j = -j; // 3 (011) or 5 (101) mod 8 852 } 853 if (u == 1) 854 return j; 855 // Now both u and p are odd, so use quadratic reciprocity 856 assert (u < p); 857 int t = u; u = p; p = t; 858 if ((u & p & 2) != 0) // u = p = 3 (mod 4)? 859 j = -j; 860 // Now u >= p, so it can be reduced 861 u %= p; 862 } 863 return 0; 864 } 865 866 private static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) { 867 BigInteger d = BigInteger.valueOf(z); 868 BigInteger u = ONE; BigInteger u2; 869 BigInteger v = ONE; BigInteger v2; 870 871 for (int i=k.bitLength()-2; i>=0; i--) { 872 u2 = u.multiply(v).mod(n); 873 874 v2 = v.square().add(d.multiply(u.square())).mod(n); 875 if (v2.testBit(0)) 876 v2 = v2.subtract(n); 877 878 v2 = v2.shiftRight(1); 879 880 u = u2; v = v2; 881 if (k.testBit(i)) { 882 u2 = u.add(v).mod(n); 883 if (u2.testBit(0)) 884 u2 = u2.subtract(n); 885 886 u2 = u2.shiftRight(1); 887 v2 = v.add(d.multiply(u)).mod(n); 888 if (v2.testBit(0)) 889 v2 = v2.subtract(n); 890 v2 = v2.shiftRight(1); 891 892 u = u2; v = v2; 893 } 894 } 895 return u; 896 } 897 898 private static volatile Random staticRandom; 899 900 private static Random getSecureRandom() { 901 if (staticRandom == null) { 902 staticRandom = new java.security.SecureRandom(); 903 } 904 return staticRandom; 905 } 906 907 /** 908 * Returns true iff this BigInteger passes the specified number of 909 * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS 910 * 186-2). 911 * 912 * The following assumptions are made: 913 * This BigInteger is a positive, odd number greater than 2. 914 * iterations<=50. 915 */ 916 private boolean passesMillerRabin(int iterations, Random rnd) { 917 // Find a and m such that m is odd and this == 1 + 2**a * m 918 BigInteger thisMinusOne = this.subtract(ONE); 919 BigInteger m = thisMinusOne; 920 int a = m.getLowestSetBit(); 921 m = m.shiftRight(a); 922 923 // Do the tests 924 if (rnd == null) { 925 rnd = getSecureRandom(); 926 } 927 for (int i=0; i<iterations; i++) { 928 // Generate a uniform random on (1, this) 929 BigInteger b; 930 do { 931 b = new BigInteger(this.bitLength(), rnd); 932 } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0); 933 934 int j = 0; 935 BigInteger z = b.modPow(m, this); 936 while(!((j==0 && z.equals(ONE)) || z.equals(thisMinusOne))) { 937 if (j>0 && z.equals(ONE) || ++j==a) 938 return false; 939 z = z.modPow(TWO, this); 940 } 941 } 942 return true; 943 } 944 945 /** 946 * This internal constructor differs from its public cousin 947 * with the arguments reversed in two ways: it assumes that its 948 * arguments are correct, and it doesn't copy the magnitude array. 949 */ 950 BigInteger(int[] magnitude, int signum) { 951 this.signum = (magnitude.length==0 ? 0 : signum); 952 this.mag = magnitude; 953 } 954 955 /** 956 * This private constructor is for internal use and assumes that its 957 * arguments are correct. 958 */ 959 private BigInteger(byte[] magnitude, int signum) { 960 this.signum = (magnitude.length==0 ? 0 : signum); 961 this.mag = stripLeadingZeroBytes(magnitude); 962 } 963 964 //Static Factory Methods 965 966 /** 967 * Returns a BigInteger whose value is equal to that of the 968 * specified {@code long}. This "static factory method" is 969 * provided in preference to a ({@code long}) constructor 970 * because it allows for reuse of frequently used BigIntegers. 971 * 972 * @param val value of the BigInteger to return. 973 * @return a BigInteger with the specified value. 974 */ 975 public static BigInteger valueOf(long val) { 976 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant 977 if (val == 0) 978 return ZERO; 979 if (val > 0 && val <= MAX_CONSTANT) 980 return posConst[(int) val]; 981 else if (val < 0 && val >= -MAX_CONSTANT) 982 return negConst[(int) -val]; 983 984 return new BigInteger(val); 985 } 986 987 /** 988 * Constructs a BigInteger with the specified value, which may not be zero. 989 */ 990 private BigInteger(long val) { 991 if (val < 0) { 992 val = -val; 993 signum = -1; 994 } else { 995 signum = 1; 996 } 997 998 int highWord = (int)(val >>> 32); 999 if (highWord==0) { 1000 mag = new int[1]; 1001 mag[0] = (int)val; 1002 } else { 1003 mag = new int[2]; 1004 mag[0] = highWord; 1005 mag[1] = (int)val; 1006 } 1007 } 1008 1009 /** 1010 * Returns a BigInteger with the given two's complement representation. 1011 * Assumes that the input array will not be modified (the returned 1012 * BigInteger will reference the input array if feasible). 1013 */ 1014 private static BigInteger valueOf(int val[]) { 1015 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val)); 1016 } 1017 1018 // Constants 1019 1020 /** 1021 * Initialize static constant array when class is loaded. 1022 */ 1023 private final static int MAX_CONSTANT = 16; 1024 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1]; 1025 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1]; 1026 1027 static { 1028 for (int i = 1; i <= MAX_CONSTANT; i++) { 1029 int[] magnitude = new int[1]; 1030 magnitude[0] = i; 1031 posConst[i] = new BigInteger(magnitude, 1); 1032 negConst[i] = new BigInteger(magnitude, -1); 1033 } 1034 } 1035 1036 /** 1037 * The BigInteger constant zero. 1038 * 1039 * @since 1.2 1040 */ 1041 public static final BigInteger ZERO = new BigInteger(new int[0], 0); 1042 1043 /** 1044 * The BigInteger constant one. 1045 * 1046 * @since 1.2 1047 */ 1048 public static final BigInteger ONE = valueOf(1); 1049 1050 /** 1051 * The BigInteger constant two. (Not exported.) 1052 */ 1053 private static final BigInteger TWO = valueOf(2); 1054 1055 /** 1056 * The BigInteger constant -1. (Not exported.) 1057 */ 1058 private static final BigInteger NEGATIVE_ONE = valueOf(-1); 1059 1060 /** 1061 * The BigInteger constant ten. 1062 * 1063 * @since 1.5 1064 */ 1065 public static final BigInteger TEN = valueOf(10); 1066 1067 // Arithmetic Operations 1068 1069 /** 1070 * Returns a BigInteger whose value is {@code (this + val)}. 1071 * 1072 * @param val value to be added to this BigInteger. 1073 * @return {@code this + val} 1074 */ 1075 public BigInteger add(BigInteger val) { 1076 if (val.signum == 0) 1077 return this; 1078 if (signum == 0) 1079 return val; 1080 if (val.signum == signum) 1081 return new BigInteger(add(mag, val.mag), signum); 1082 1083 int cmp = compareMagnitude(val); 1084 if (cmp == 0) 1085 return ZERO; 1086 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag) 1087 : subtract(val.mag, mag)); 1088 resultMag = trustedStripLeadingZeroInts(resultMag); 1089 1090 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1091 } 1092 1093 /** 1094 * Package private methods used by BigDecimal code to add a BigInteger 1095 * with a long. Assumes val is not equal to INFLATED. 1096 */ 1097 BigInteger add(long val) { 1098 if (val == 0) 1099 return this; 1100 if (signum == 0) 1101 return valueOf(val); 1102 if (Long.signum(val) == signum) 1103 return new BigInteger(add(mag, Math.abs(val)), signum); 1104 int cmp = compareMagnitude(val); 1105 if (cmp == 0) 1106 return ZERO; 1107 int[] resultMag = (cmp > 0 ? subtract(mag, Math.abs(val)) : subtract(Math.abs(val), mag)); 1108 resultMag = trustedStripLeadingZeroInts(resultMag); 1109 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1110 } 1111 1112 /** 1113 * Adds the contents of the int array x and long value val. This 1114 * method allocates a new int array to hold the answer and returns 1115 * a reference to that array. Assumes x.length > 0 and val is 1116 * non-negative 1117 */ 1118 private static int[] add(int[] x, long val) { 1119 int[] y; 1120 long sum = 0; 1121 int xIndex = x.length; 1122 int[] result; 1123 int highWord = (int)(val >>> 32); 1124 if (highWord==0) { 1125 result = new int[xIndex]; 1126 sum = (x[--xIndex] & LONG_MASK) + val; 1127 result[xIndex] = (int)sum; 1128 } else { 1129 if (xIndex == 1) { 1130 result = new int[2]; 1131 sum = val + (x[0] & LONG_MASK); 1132 result[1] = (int)sum; 1133 result[0] = (int)(sum >>> 32); 1134 return result; 1135 } else { 1136 result = new int[xIndex]; 1137 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK); 1138 result[xIndex] = (int)sum; 1139 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32); 1140 result[xIndex] = (int)sum; 1141 } 1142 } 1143 // Copy remainder of longer number while carry propagation is required 1144 boolean carry = (sum >>> 32 != 0); 1145 while (xIndex > 0 && carry) 1146 carry = ((result[--xIndex] = x[xIndex] + 1) == 0); 1147 // Copy remainder of longer number 1148 while (xIndex > 0) 1149 result[--xIndex] = x[xIndex]; 1150 // Grow result if necessary 1151 if (carry) { 1152 int bigger[] = new int[result.length + 1]; 1153 System.arraycopy(result, 0, bigger, 1, result.length); 1154 bigger[0] = 0x01; 1155 return bigger; 1156 } 1157 return result; 1158 } 1159 1160 /** 1161 * Adds the contents of the int arrays x and y. This method allocates 1162 * a new int array to hold the answer and returns a reference to that 1163 * array. 1164 */ 1165 private static int[] add(int[] x, int[] y) { 1166 // If x is shorter, swap the two arrays 1167 if (x.length < y.length) { 1168 int[] tmp = x; 1169 x = y; 1170 y = tmp; 1171 } 1172 1173 int xIndex = x.length; 1174 int yIndex = y.length; 1175 int result[] = new int[xIndex]; 1176 long sum = 0; 1177 if(yIndex==1) { 1178 sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ; 1179 result[xIndex] = (int)sum; 1180 } else { 1181 // Add common parts of both numbers 1182 while(yIndex > 0) { 1183 sum = (x[--xIndex] & LONG_MASK) + 1184 (y[--yIndex] & LONG_MASK) + (sum >>> 32); 1185 result[xIndex] = (int)sum; 1186 } 1187 } 1188 // Copy remainder of longer number while carry propagation is required 1189 boolean carry = (sum >>> 32 != 0); 1190 while (xIndex > 0 && carry) 1191 carry = ((result[--xIndex] = x[xIndex] + 1) == 0); 1192 1193 // Copy remainder of longer number 1194 while (xIndex > 0) 1195 result[--xIndex] = x[xIndex]; 1196 1197 // Grow result if necessary 1198 if (carry) { 1199 int bigger[] = new int[result.length + 1]; 1200 System.arraycopy(result, 0, bigger, 1, result.length); 1201 bigger[0] = 0x01; 1202 return bigger; 1203 } 1204 return result; 1205 } 1206 1207 private static int[] subtract(long val, int[] little) { 1208 int highWord = (int)(val >>> 32); 1209 if (highWord==0) { 1210 int result[] = new int[1]; 1211 result[0] = (int)(val - (little[0] & LONG_MASK)); 1212 return result; 1213 } else { 1214 int result[] = new int[2]; 1215 if(little.length==1) { 1216 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK); 1217 result[1] = (int)difference; 1218 // Subtract remainder of longer number while borrow propagates 1219 boolean borrow = (difference >> 32 != 0); 1220 if(borrow) { 1221 result[0] = highWord - 1; 1222 } else { // Copy remainder of longer number 1223 result[0] = highWord; 1224 } 1225 return result; 1226 } else { // little.length==2 1227 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK); 1228 result[1] = (int)difference; 1229 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32); 1230 result[0] = (int)difference; 1231 return result; 1232 } 1233 } 1234 } 1235 1236 /** 1237 * Subtracts the contents of the second argument (val) from the 1238 * first (big). The first int array (big) must represent a larger number 1239 * than the second. This method allocates the space necessary to hold the 1240 * answer. 1241 * assumes val >= 0 1242 */ 1243 private static int[] subtract(int[] big, long val) { 1244 int highWord = (int)(val >>> 32); 1245 int bigIndex = big.length; 1246 int result[] = new int[bigIndex]; 1247 long difference = 0; 1248 1249 if (highWord==0) { 1250 difference = (big[--bigIndex] & LONG_MASK) - val; 1251 result[bigIndex] = (int)difference; 1252 } else { 1253 difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK); 1254 result[bigIndex] = (int)difference; 1255 difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32); 1256 result[bigIndex] = (int)difference; 1257 } 1258 1259 1260 // Subtract remainder of longer number while borrow propagates 1261 boolean borrow = (difference >> 32 != 0); 1262 while (bigIndex > 0 && borrow) 1263 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1); 1264 1265 // Copy remainder of longer number 1266 while (bigIndex > 0) 1267 result[--bigIndex] = big[bigIndex]; 1268 1269 return result; 1270 } 1271 1272 /** 1273 * Returns a BigInteger whose value is {@code (this - val)}. 1274 * 1275 * @param val value to be subtracted from this BigInteger. 1276 * @return {@code this - val} 1277 */ 1278 public BigInteger subtract(BigInteger val) { 1279 if (val.signum == 0) 1280 return this; 1281 if (signum == 0) 1282 return val.negate(); 1283 if (val.signum != signum) 1284 return new BigInteger(add(mag, val.mag), signum); 1285 1286 int cmp = compareMagnitude(val); 1287 if (cmp == 0) 1288 return ZERO; 1289 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag) 1290 : subtract(val.mag, mag)); 1291 resultMag = trustedStripLeadingZeroInts(resultMag); 1292 return new BigInteger(resultMag, cmp == signum ? 1 : -1); 1293 } 1294 1295 /** 1296 * Subtracts the contents of the second int arrays (little) from the 1297 * first (big). The first int array (big) must represent a larger number 1298 * than the second. This method allocates the space necessary to hold the 1299 * answer. 1300 */ 1301 private static int[] subtract(int[] big, int[] little) { 1302 int bigIndex = big.length; 1303 int result[] = new int[bigIndex]; 1304 int littleIndex = little.length; 1305 long difference = 0; 1306 1307 // Subtract common parts of both numbers 1308 while(littleIndex > 0) { 1309 difference = (big[--bigIndex] & LONG_MASK) - 1310 (little[--littleIndex] & LONG_MASK) + 1311 (difference >> 32); 1312 result[bigIndex] = (int)difference; 1313 } 1314 1315 // Subtract remainder of longer number while borrow propagates 1316 boolean borrow = (difference >> 32 != 0); 1317 while (bigIndex > 0 && borrow) 1318 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1); 1319 1320 // Copy remainder of longer number 1321 while (bigIndex > 0) 1322 result[--bigIndex] = big[bigIndex]; 1323 1324 return result; 1325 } 1326 1327 /** 1328 * Returns a BigInteger whose value is {@code (this * val)}. 1329 * 1330 * @param val value to be multiplied by this BigInteger. 1331 * @return {@code this * val} 1332 */ 1333 public BigInteger multiply(BigInteger val) { 1334 if (val.signum == 0 || signum == 0) 1335 return ZERO; 1336 1337 int xlen = mag.length; 1338 int ylen = val.mag.length; 1339 1340 if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) 1341 { 1342 int resultSign = signum == val.signum ? 1 : -1; 1343 if (val.mag.length == 1) { 1344 return multiplyByInt(mag,val.mag[0], resultSign); 1345 } 1346 if(mag.length == 1) { 1347 return multiplyByInt(val.mag,mag[0], resultSign); 1348 } 1349 int[] result = multiplyToLen(mag, xlen, 1350 val.mag, ylen, null); 1351 result = trustedStripLeadingZeroInts(result); 1352 return new BigInteger(result, resultSign); 1353 } 1354 else 1355 if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) 1356 return multiplyKaratsuba(this, val); 1357 else 1358 return multiplyToomCook3(this, val); 1359 } 1360 1361 private static BigInteger multiplyByInt(int[] x, int y, int sign) { 1362 if(Integer.bitCount(y)==1) { 1363 return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign); 1364 } 1365 int xlen = x.length; 1366 int[] rmag = new int[xlen + 1]; 1367 long carry = 0; 1368 long yl = y & LONG_MASK; 1369 int rstart = rmag.length - 1; 1370 for (int i = xlen - 1; i >= 0; i--) { 1371 long product = (x[i] & LONG_MASK) * yl + carry; 1372 rmag[rstart--] = (int)product; 1373 carry = product >>> 32; 1374 } 1375 if (carry == 0L) { 1376 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length); 1377 } else { 1378 rmag[rstart] = (int)carry; 1379 } 1380 return new BigInteger(rmag, sign); 1381 } 1382 1383 /** 1384 * Package private methods used by BigDecimal code to multiply a BigInteger 1385 * with a long. Assumes v is not equal to INFLATED. 1386 */ 1387 BigInteger multiply(long v) { 1388 if (v == 0 || signum == 0) 1389 return ZERO; 1390 if (v == BigDecimal.INFLATED) 1391 return multiply(BigInteger.valueOf(v)); 1392 int rsign = (v > 0 ? signum : -signum); 1393 if (v < 0) 1394 v = -v; 1395 long dh = v >>> 32; // higher order bits 1396 long dl = v & LONG_MASK; // lower order bits 1397 1398 int xlen = mag.length; 1399 int[] value = mag; 1400 int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]); 1401 long carry = 0; 1402 int rstart = rmag.length - 1; 1403 for (int i = xlen - 1; i >= 0; i--) { 1404 long product = (value[i] & LONG_MASK) * dl + carry; 1405 rmag[rstart--] = (int)product; 1406 carry = product >>> 32; 1407 } 1408 rmag[rstart] = (int)carry; 1409 if (dh != 0L) { 1410 carry = 0; 1411 rstart = rmag.length - 2; 1412 for (int i = xlen - 1; i >= 0; i--) { 1413 long product = (value[i] & LONG_MASK) * dh + 1414 (rmag[rstart] & LONG_MASK) + carry; 1415 rmag[rstart--] = (int)product; 1416 carry = product >>> 32; 1417 } 1418 rmag[0] = (int)carry; 1419 } 1420 if (carry == 0L) 1421 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length); 1422 return new BigInteger(rmag, rsign); 1423 } 1424 1425 /** 1426 * Multiplies int arrays x and y to the specified lengths and places 1427 * the result into z. There will be no leading zeros in the resultant array. 1428 */ 1429 private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) { 1430 int xstart = xlen - 1; 1431 int ystart = ylen - 1; 1432 1433 if (z == null || z.length < (xlen+ ylen)) 1434 z = new int[xlen+ylen]; 1435 1436 long carry = 0; 1437 for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) { 1438 long product = (y[j] & LONG_MASK) * 1439 (x[xstart] & LONG_MASK) + carry; 1440 z[k] = (int)product; 1441 carry = product >>> 32; 1442 } 1443 z[xstart] = (int)carry; 1444 1445 for (int i = xstart-1; i >= 0; i--) { 1446 carry = 0; 1447 for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) { 1448 long product = (y[j] & LONG_MASK) * 1449 (x[i] & LONG_MASK) + 1450 (z[k] & LONG_MASK) + carry; 1451 z[k] = (int)product; 1452 carry = product >>> 32; 1453 } 1454 z[i] = (int)carry; 1455 } 1456 return z; 1457 } 1458 1459 /** 1460 * Multiplies two BigIntegers using the Karatsuba multiplication 1461 * algorithm. This is a recursive divide-and-conquer algorithm which is 1462 * more efficient for large numbers than what is commonly called the 1463 * "grade-school" algorithm used in multiplyToLen. If the numbers to be 1464 * multiplied have length n, the "grade-school" algorithm has an 1465 * asymptotic complexity of O(n^2). In contrast, the Karatsuba algorithm 1466 * has complexity of O(n^(log2(3))), or O(n^1.585). It achieves this 1467 * increased performance by doing 3 multiplies instead of 4 when 1468 * evaluating the product. As it has some overhead, should be used when 1469 * both numbers are larger than a certain threshold (found 1470 * experimentally). 1471 * 1472 * See: http://en.wikipedia.org/wiki/Karatsuba_algorithm 1473 */ 1474 private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) 1475 { 1476 int xlen = x.mag.length; 1477 int ylen = y.mag.length; 1478 1479 // The number of ints in each half of the number. 1480 int half = (Math.max(xlen, ylen)+1) / 2; 1481 1482 // xl and yl are the lower halves of x and y respectively, 1483 // xh and yh are the upper halves. 1484 BigInteger xl = x.getLower(half); 1485 BigInteger xh = x.getUpper(half); 1486 BigInteger yl = y.getLower(half); 1487 BigInteger yh = y.getUpper(half); 1488 1489 BigInteger p1 = xh.multiply(yh); // p1 = xh*yh 1490 BigInteger p2 = xl.multiply(yl); // p2 = xl*yl 1491 1492 // p3=(xh+xl)*(yh+yl) 1493 BigInteger p3 = xh.add(xl).multiply(yh.add(yl)); 1494 1495 // result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2 1496 BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2); 1497 1498 if (x.signum != y.signum) 1499 return result.negate(); 1500 else 1501 return result; 1502 } 1503 1504 /** 1505 * Multiplies two BigIntegers using a 3-way Toom-Cook multiplication 1506 * algorithm. This is a recursive divide-and-conquer algorithm which is 1507 * more efficient for large numbers than what is commonly called the 1508 * "grade-school" algorithm used in multiplyToLen. If the numbers to be 1509 * multiplied have length n, the "grade-school" algorithm has an 1510 * asymptotic complexity of O(n^2). In contrast, 3-way Toom-Cook has a 1511 * complexity of about O(n^1.465). It achieves this increased asymptotic 1512 * performance by breaking each number into three parts and by doing 5 1513 * multiplies instead of 9 when evaluating the product. Due to overhead 1514 * (additions, shifts, and one division) in the Toom-Cook algorithm, it 1515 * should only be used when both numbers are larger than a certain 1516 * threshold (found experimentally). This threshold is generally larger 1517 * than that for Karatsuba multiplication, so this algorithm is generally 1518 * only used when numbers become significantly larger. 1519 * 1520 * The algorithm used is the "optimal" 3-way Toom-Cook algorithm outlined 1521 * by Marco Bodrato. 1522 * 1523 * See: http://bodrato.it/toom-cook/ 1524 * http://bodrato.it/papers/#WAIFI2007 1525 * 1526 * "Towards Optimal Toom-Cook Multiplication for Univariate and 1527 * Multivariate Polynomials in Characteristic 2 and 0." by Marco BODRATO; 1528 * In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133, 1529 * LNCS #4547. Springer, Madrid, Spain, June 21-22, 2007. 1530 * 1531 */ 1532 private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b) 1533 { 1534 int alen = a.mag.length; 1535 int blen = b.mag.length; 1536 1537 int largest = Math.max(alen, blen); 1538 1539 // k is the size (in ints) of the lower-order slices. 1540 int k = (largest+2)/3; // Equal to ceil(largest/3) 1541 1542 // r is the size (in ints) of the highest-order slice. 1543 int r = largest - 2*k; 1544 1545 // Obtain slices of the numbers. a2 and b2 are the most significant 1546 // bits of the numbers a and b, and a0 and b0 the least significant. 1547 BigInteger a0, a1, a2, b0, b1, b2; 1548 a2 = a.getToomSlice(k, r, 0, largest); 1549 a1 = a.getToomSlice(k, r, 1, largest); 1550 a0 = a.getToomSlice(k, r, 2, largest); 1551 b2 = b.getToomSlice(k, r, 0, largest); 1552 b1 = b.getToomSlice(k, r, 1, largest); 1553 b0 = b.getToomSlice(k, r, 2, largest); 1554 1555 BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1; 1556 1557 v0 = a0.multiply(b0); 1558 da1 = a2.add(a0); 1559 db1 = b2.add(b0); 1560 vm1 = da1.subtract(a1).multiply(db1.subtract(b1)); 1561 da1 = da1.add(a1); 1562 db1 = db1.add(b1); 1563 v1 = da1.multiply(db1); 1564 v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply( 1565 db1.add(b2).shiftLeft(1).subtract(b0)); 1566 vinf = a2.multiply(b2); 1567 1568 /* The algorithm requires two divisions by 2 and one by 3. 1569 All divisions are known to be exact, that is, they do not produce 1570 remainders, and all results are positive. The divisions by 2 are 1571 implemented as right shifts which are relatively efficient, leaving 1572 only an exact division by 3, which is done by a specialized 1573 linear-time algorithm. */ 1574 t2 = v2.subtract(vm1).exactDivideBy3(); 1575 tm1 = v1.subtract(vm1).shiftRight(1); 1576 t1 = v1.subtract(v0); 1577 t2 = t2.subtract(t1).shiftRight(1); 1578 t1 = t1.subtract(tm1).subtract(vinf); 1579 t2 = t2.subtract(vinf.shiftLeft(1)); 1580 tm1 = tm1.subtract(t2); 1581 1582 // Number of bits to shift left. 1583 int ss = k*32; 1584 1585 BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0); 1586 1587 if (a.signum != b.signum) 1588 return result.negate(); 1589 else 1590 return result; 1591 } 1592 1593 1594 /** 1595 * Returns a slice of a BigInteger for use in Toom-Cook multiplication. 1596 * 1597 * @param lowerSize The size of the lower-order bit slices. 1598 * @param upperSize The size of the higher-order bit slices. 1599 * @param slice The index of which slice is requested, which must be a 1600 * number from 0 to size-1. Slice 0 is the highest-order bits, and slice 1601 * size-1 are the lowest-order bits. Slice 0 may be of different size than 1602 * the other slices. 1603 * @param fullsize The size of the larger integer array, used to align 1604 * slices to the appropriate position when multiplying different-sized 1605 * numbers. 1606 */ 1607 private BigInteger getToomSlice(int lowerSize, int upperSize, int slice, 1608 int fullsize) 1609 { 1610 int start, end, sliceSize, len, offset; 1611 1612 len = mag.length; 1613 offset = fullsize - len; 1614 1615 if (slice == 0) 1616 { 1617 start = 0 - offset; 1618 end = upperSize - 1 - offset; 1619 } 1620 else 1621 { 1622 start = upperSize + (slice-1)*lowerSize - offset; 1623 end = start + lowerSize - 1; 1624 } 1625 1626 if (start < 0) 1627 start = 0; 1628 if (end < 0) 1629 return ZERO; 1630 1631 sliceSize = (end-start) + 1; 1632 1633 if (sliceSize <= 0) 1634 return ZERO; 1635 1636 // While performing Toom-Cook, all slices are positive and 1637 // the sign is adjusted when the final number is composed. 1638 if (start==0 && sliceSize >= len) 1639 return this.abs(); 1640 1641 int intSlice[] = new int[sliceSize]; 1642 System.arraycopy(mag, start, intSlice, 0, sliceSize); 1643 1644 return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1); 1645 } 1646 1647 /** 1648 * Does an exact division (that is, the remainder is known to be zero) 1649 * of the specified number by 3. This is used in Toom-Cook 1650 * multiplication. This is an efficient algorithm that runs in linear 1651 * time. If the argument is not exactly divisible by 3, results are 1652 * undefined. Note that this is expected to be called with positive 1653 * arguments only. 1654 */ 1655 private BigInteger exactDivideBy3() 1656 { 1657 int len = mag.length; 1658 int[] result = new int[len]; 1659 long x, w, q, borrow; 1660 borrow = 0L; 1661 for (int i=len-1; i>=0; i--) 1662 { 1663 x = (mag[i] & LONG_MASK); 1664 w = x - borrow; 1665 if (borrow > x) // Did we make the number go negative? 1666 borrow = 1L; 1667 else 1668 borrow = 0L; 1669 1670 // 0xAAAAAAAB is the modular inverse of 3 (mod 2^32). Thus, 1671 // the effect of this is to divide by 3 (mod 2^32). 1672 // This is much faster than division on most architectures. 1673 q = (w * 0xAAAAAAABL) & LONG_MASK; 1674 result[i] = (int) q; 1675 1676 // Now check the borrow. The second check can of course be 1677 // eliminated if the first fails. 1678 if (q >= 0x55555556L) 1679 { 1680 borrow++; 1681 if (q >= 0xAAAAAAABL) 1682 borrow++; 1683 } 1684 } 1685 result = trustedStripLeadingZeroInts(result); 1686 return new BigInteger(result, signum); 1687 } 1688 1689 /** 1690 * Returns a new BigInteger representing n lower ints of the number. 1691 * This is used by Karatsuba multiplication and Karatsuba squaring. 1692 */ 1693 private BigInteger getLower(int n) { 1694 int len = mag.length; 1695 1696 if (len <= n) 1697 return this; 1698 1699 int lowerInts[] = new int[n]; 1700 System.arraycopy(mag, len-n, lowerInts, 0, n); 1701 1702 return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1); 1703 } 1704 1705 /** 1706 * Returns a new BigInteger representing mag.length-n upper 1707 * ints of the number. This is used by Karatsuba multiplication and 1708 * Karatsuba squaring. 1709 */ 1710 private BigInteger getUpper(int n) { 1711 int len = mag.length; 1712 1713 if (len <= n) 1714 return ZERO; 1715 1716 int upperLen = len - n; 1717 int upperInts[] = new int[upperLen]; 1718 System.arraycopy(mag, 0, upperInts, 0, upperLen); 1719 1720 return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1); 1721 } 1722 1723 // Squaring 1724 1725 /** 1726 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}. 1727 * 1728 * @return {@code this<sup>2</sup>} 1729 */ 1730 private BigInteger square() { 1731 if (signum == 0) 1732 return ZERO; 1733 int len = mag.length; 1734 1735 if (len < KARATSUBA_SQUARE_THRESHOLD) 1736 { 1737 int[] z = squareToLen(mag, len, null); 1738 return new BigInteger(trustedStripLeadingZeroInts(z), 1); 1739 } 1740 else 1741 if (len < TOOM_COOK_SQUARE_THRESHOLD) 1742 return squareKaratsuba(); 1743 else 1744 return squareToomCook3(); 1745 } 1746 1747 /** 1748 * Squares the contents of the int array x. The result is placed into the 1749 * int array z. The contents of x are not changed. 1750 */ 1751 private static final int[] squareToLen(int[] x, int len, int[] z) { 1752 /* 1753 * The algorithm used here is adapted from Colin Plumb's C library. 1754 * Technique: Consider the partial products in the multiplication 1755 * of "abcde" by itself: 1756 * 1757 * a b c d e 1758 * * a b c d e 1759 * ================== 1760 * ae be ce de ee 1761 * ad bd cd dd de 1762 * ac bc cc cd ce 1763 * ab bb bc bd be 1764 * aa ab ac ad ae 1765 * 1766 * Note that everything above the main diagonal: 1767 * ae be ce de = (abcd) * e 1768 * ad bd cd = (abc) * d 1769 * ac bc = (ab) * c 1770 * ab = (a) * b 1771 * 1772 * is a copy of everything below the main diagonal: 1773 * de 1774 * cd ce 1775 * bc bd be 1776 * ab ac ad ae 1777 * 1778 * Thus, the sum is 2 * (off the diagonal) + diagonal. 1779 * 1780 * This is accumulated beginning with the diagonal (which 1781 * consist of the squares of the digits of the input), which is then 1782 * divided by two, the off-diagonal added, and multiplied by two 1783 * again. The low bit is simply a copy of the low bit of the 1784 * input, so it doesn't need special care. 1785 */ 1786 int zlen = len << 1; 1787 if (z == null || z.length < zlen) 1788 z = new int[zlen]; 1789 1790 // Store the squares, right shifted one bit (i.e., divided by 2) 1791 int lastProductLowWord = 0; 1792 for (int j=0, i=0; j<len; j++) { 1793 long piece = (x[j] & LONG_MASK); 1794 long product = piece * piece; 1795 z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33); 1796 z[i++] = (int)(product >>> 1); 1797 lastProductLowWord = (int)product; 1798 } 1799 1800 // Add in off-diagonal sums 1801 for (int i=len, offset=1; i>0; i--, offset+=2) { 1802 int t = x[i-1]; 1803 t = mulAdd(z, x, offset, i-1, t); 1804 addOne(z, offset-1, i, t); 1805 } 1806 1807 // Shift back up and set low bit 1808 primitiveLeftShift(z, zlen, 1); 1809 z[zlen-1] |= x[len-1] & 1; 1810 1811 return z; 1812 } 1813 1814 /** 1815 * Squares a BigInteger using the Karatsuba squaring algorithm. It should 1816 * be used when both numbers are larger than a certain threshold (found 1817 * experimentally). It is a recursive divide-and-conquer algorithm that 1818 * has better asymptotic performance than the algorithm used in 1819 * squareToLen. 1820 */ 1821 private BigInteger squareKaratsuba() 1822 { 1823 int half = (mag.length+1) / 2; 1824 1825 BigInteger xl = getLower(half); 1826 BigInteger xh = getUpper(half); 1827 1828 BigInteger xhs = xh.square(); // xhs = xh^2 1829 BigInteger xls = xl.square(); // xls = xl^2 1830 1831 // xh^2 << 64 + (((xl+xh)^2 - (xh^2 + xl^2)) << 32) + xl^2 1832 return xhs.shiftLeft(half*32).add(xl.add(xh).square().subtract(xhs.add(xls))).shiftLeft(half*32).add(xls); 1833 } 1834 1835 /** 1836 * Squares a BigInteger using the 3-way Toom-Cook squaring algorithm. It 1837 * should be used when both numbers are larger than a certain threshold 1838 * (found experimentally). It is a recursive divide-and-conquer algorithm 1839 * that has better asymptotic performance than the algorithm used in 1840 * squareToLen or squareKaratsuba. 1841 */ 1842 private BigInteger squareToomCook3() 1843 { 1844 int len = mag.length; 1845 1846 // k is the size (in ints) of the lower-order slices. 1847 int k = (len+2)/3; // Equal to ceil(largest/3) 1848 1849 // r is the size (in ints) of the highest-order slice. 1850 int r = len - 2*k; 1851 1852 // Obtain slices of the numbers. a2 is the most significant 1853 // bits of the number, and a0 the least significant. 1854 BigInteger a0, a1, a2; 1855 a2 = getToomSlice(k, r, 0, len); 1856 a1 = getToomSlice(k, r, 1, len); 1857 a0 = getToomSlice(k, r, 2, len); 1858 BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1; 1859 1860 v0 = a0.square(); 1861 da1 = a2.add(a0); 1862 vm1 = da1.subtract(a1).square(); 1863 da1 = da1.add(a1); 1864 v1 = da1.square(); 1865 vinf = a2.square(); 1866 v2 = da1.add(a2).shiftLeft(1).subtract(a0).square(); 1867 1868 /* The algorithm requires two divisions by 2 and one by 3. 1869 All divisions are known to be exact, that is, they do not produce 1870 remainders, and all results are positive. The divisions by 2 are 1871 implemented as right shifts which are relatively efficient, leaving 1872 only a division by 3. 1873 The division by 3 is done by an optimized algorithm for this case. 1874 */ 1875 t2 = v2.subtract(vm1).exactDivideBy3(); 1876 tm1 = v1.subtract(vm1).shiftRight(1); 1877 t1 = v1.subtract(v0); 1878 t2 = t2.subtract(t1).shiftRight(1); 1879 t1 = t1.subtract(tm1).subtract(vinf); 1880 t2 = t2.subtract(vinf.shiftLeft(1)); 1881 tm1 = tm1.subtract(t2); 1882 1883 // Number of bits to shift left. 1884 int ss = k*32; 1885 1886 return vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0); 1887 } 1888 1889 // Division 1890 1891 /** 1892 * Returns a BigInteger whose value is {@code (this / val)}. 1893 * 1894 * @param val value by which this BigInteger is to be divided. 1895 * @return {@code this / val} 1896 * @throws ArithmeticException if {@code val} is zero. 1897 */ 1898 public BigInteger divide(BigInteger val) { 1899 MutableBigInteger q = new MutableBigInteger(), 1900 a = new MutableBigInteger(this.mag), 1901 b = new MutableBigInteger(val.mag); 1902 1903 a.divide(b, q, false); 1904 return q.toBigInteger(this.signum * val.signum); 1905 } 1906 1907 /** 1908 * Returns an array of two BigIntegers containing {@code (this / val)} 1909 * followed by {@code (this % val)}. 1910 * 1911 * @param val value by which this BigInteger is to be divided, and the 1912 * remainder computed. 1913 * @return an array of two BigIntegers: the quotient {@code (this / val)} 1914 * is the initial element, and the remainder {@code (this % val)} 1915 * is the final element. 1916 * @throws ArithmeticException if {@code val} is zero. 1917 */ 1918 public BigInteger[] divideAndRemainder(BigInteger val) { 1919 BigInteger[] result = new BigInteger[2]; 1920 MutableBigInteger q = new MutableBigInteger(), 1921 a = new MutableBigInteger(this.mag), 1922 b = new MutableBigInteger(val.mag); 1923 MutableBigInteger r = a.divide(b, q); 1924 result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1); 1925 result[1] = r.toBigInteger(this.signum); 1926 return result; 1927 } 1928 1929 /** 1930 * Returns a BigInteger whose value is {@code (this % val)}. 1931 * 1932 * @param val value by which this BigInteger is to be divided, and the 1933 * remainder computed. 1934 * @return {@code this % val} 1935 * @throws ArithmeticException if {@code val} is zero. 1936 */ 1937 public BigInteger remainder(BigInteger val) { 1938 MutableBigInteger q = new MutableBigInteger(), 1939 a = new MutableBigInteger(this.mag), 1940 b = new MutableBigInteger(val.mag); 1941 1942 return a.divide(b, q).toBigInteger(this.signum); 1943 } 1944 1945 /** 1946 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>. 1947 * Note that {@code exponent} is an integer rather than a BigInteger. 1948 * 1949 * @param exponent exponent to which this BigInteger is to be raised. 1950 * @return <tt>this<sup>exponent</sup></tt> 1951 * @throws ArithmeticException {@code exponent} is negative. (This would 1952 * cause the operation to yield a non-integer value.) 1953 */ 1954 public BigInteger pow(int exponent) { 1955 if (exponent < 0) 1956 throw new ArithmeticException("Negative exponent"); 1957 if (signum==0) 1958 return (exponent==0 ? ONE : this); 1959 1960 BigInteger partToSquare = this.abs(); 1961 1962 // Factor out powers of two from the base, as the exponentiation of 1963 // these can be done by left shifts only. 1964 // The remaining part can then be exponentiated faster. The 1965 // powers of two will be multiplied back at the end. 1966 int powersOfTwo = partToSquare.getLowestSetBit(); 1967 1968 int remainingBits; 1969 1970 // Factor the powers of two out quickly by shifting right, if needed. 1971 if (powersOfTwo > 0) 1972 { 1973 partToSquare = partToSquare.shiftRight(powersOfTwo); 1974 remainingBits = partToSquare.bitLength(); 1975 if (remainingBits == 1) // Nothing left but +/- 1? 1976 if (signum<0 && (exponent&1)==1) 1977 return NEGATIVE_ONE.shiftLeft(powersOfTwo*exponent); 1978 else 1979 return ONE.shiftLeft(powersOfTwo*exponent); 1980 } 1981 else 1982 { 1983 remainingBits = partToSquare.bitLength(); 1984 if (remainingBits == 1) // Nothing left but +/- 1? 1985 if (signum<0 && (exponent&1)==1) 1986 return NEGATIVE_ONE; 1987 else 1988 return ONE; 1989 } 1990 1991 // This is a quick way to approximate the size of the result, 1992 // similar to doing log2[n] * exponent. This will give an upper bound 1993 // of how big the result can be, and which algorithm to use. 1994 int scaleFactor = remainingBits * exponent; 1995 1996 // Use slightly different algorithms for small and large operands. 1997 // See if the result will safely fit into a long. (Largest 2^63-1) 1998 if (partToSquare.mag.length==1 && scaleFactor <= 62) 1999 { 2000 // Small number algorithm. Everything fits into a long. 2001 int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 2002 long result = 1; 2003 long baseToPow2 = partToSquare.mag[0] & LONG_MASK; 2004 2005 int workingExponent = exponent; 2006 2007 // Perform exponentiation using repeated squaring trick 2008 while (workingExponent != 0) { 2009 if ((workingExponent & 1)==1) 2010 result = result * baseToPow2; 2011 2012 if ((workingExponent >>>= 1) != 0) 2013 baseToPow2 = baseToPow2 * baseToPow2; 2014 } 2015 2016 // Multiply back the powers of two (quickly, by shifting left) 2017 if (powersOfTwo > 0) 2018 { 2019 int bitsToShift = powersOfTwo*exponent; 2020 if (bitsToShift + scaleFactor <= 62) // Fits in long? 2021 return valueOf((result << bitsToShift) * newSign); 2022 else 2023 return valueOf(result*newSign).shiftLeft(bitsToShift); 2024 } 2025 else 2026 return valueOf(result*newSign); 2027 } 2028 else 2029 { 2030 // Large number algorithm. This is basically identical to 2031 // the algorithm above, but calls multiply() and square() 2032 // which may use more efficient algorithms for large numbers. 2033 BigInteger answer = ONE; 2034 2035 int workingExponent = exponent; 2036 // Perform exponentiation using repeated squaring trick 2037 while (workingExponent != 0) { 2038 if ((workingExponent & 1)==1) 2039 answer = answer.multiply(partToSquare); 2040 2041 if ((workingExponent >>>= 1) != 0) 2042 partToSquare = partToSquare.square(); 2043 } 2044 // Multiply back the (exponentiated) powers of two (quickly, 2045 // by shifting left) 2046 if (powersOfTwo > 0) 2047 answer = answer.shiftLeft(powersOfTwo*exponent); 2048 2049 if (signum<0 && (exponent&1)==1) 2050 return answer.negate(); 2051 else 2052 return answer; 2053 } 2054 } 2055 2056 /** 2057 * Returns a BigInteger whose value is the greatest common divisor of 2058 * {@code abs(this)} and {@code abs(val)}. Returns 0 if 2059 * {@code this==0 && val==0}. 2060 * 2061 * @param val value with which the GCD is to be computed. 2062 * @return {@code GCD(abs(this), abs(val))} 2063 */ 2064 public BigInteger gcd(BigInteger val) { 2065 if (val.signum == 0) 2066 return this.abs(); 2067 else if (this.signum == 0) 2068 return val.abs(); 2069 2070 MutableBigInteger a = new MutableBigInteger(this); 2071 MutableBigInteger b = new MutableBigInteger(val); 2072 2073 MutableBigInteger result = a.hybridGCD(b); 2074 2075 return result.toBigInteger(1); 2076 } 2077 2078 /** 2079 * Package private method to return bit length for an integer. 2080 */ 2081 static int bitLengthForInt(int n) { 2082 return 32 - Integer.numberOfLeadingZeros(n); 2083 } 2084 2085 /** 2086 * Left shift int array a up to len by n bits. Returns the array that 2087 * results from the shift since space may have to be reallocated. 2088 */ 2089 private static int[] leftShift(int[] a, int len, int n) { 2090 int nInts = n >>> 5; 2091 int nBits = n&0x1F; 2092 int bitsInHighWord = bitLengthForInt(a[0]); 2093 2094 // If shift can be done without recopy, do so 2095 if (n <= (32-bitsInHighWord)) { 2096 primitiveLeftShift(a, len, nBits); 2097 return a; 2098 } else { // Array must be resized 2099 if (nBits <= (32-bitsInHighWord)) { 2100 int result[] = new int[nInts+len]; 2101 System.arraycopy(a, 0, result, 0, len); 2102 primitiveLeftShift(result, result.length, nBits); 2103 return result; 2104 } else { 2105 int result[] = new int[nInts+len+1]; 2106 System.arraycopy(a, 0, result, 0, len); 2107 primitiveRightShift(result, result.length, 32 - nBits); 2108 return result; 2109 } 2110 } 2111 } 2112 2113 // shifts a up to len right n bits assumes no leading zeros, 0<n<32 2114 static void primitiveRightShift(int[] a, int len, int n) { 2115 int n2 = 32 - n; 2116 for (int i=len-1, c=a[i]; i>0; i--) { 2117 int b = c; 2118 c = a[i-1]; 2119 a[i] = (c << n2) | (b >>> n); 2120 } 2121 a[0] >>>= n; 2122 } 2123 2124 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32 2125 static void primitiveLeftShift(int[] a, int len, int n) { 2126 if (len == 0 || n == 0) 2127 return; 2128 2129 int n2 = 32 - n; 2130 for (int i=0, c=a[i], m=i+len-1; i<m; i++) { 2131 int b = c; 2132 c = a[i+1]; 2133 a[i] = (b << n) | (c >>> n2); 2134 } 2135 a[len-1] <<= n; 2136 } 2137 2138 /** 2139 * Calculate bitlength of contents of the first len elements an int array, 2140 * assuming there are no leading zero ints. 2141 */ 2142 private static int bitLength(int[] val, int len) { 2143 if (len == 0) 2144 return 0; 2145 return ((len - 1) << 5) + bitLengthForInt(val[0]); 2146 } 2147 2148 /** 2149 * Returns a BigInteger whose value is the absolute value of this 2150 * BigInteger. 2151 * 2152 * @return {@code abs(this)} 2153 */ 2154 public BigInteger abs() { 2155 return (signum >= 0 ? this : this.negate()); 2156 } 2157 2158 /** 2159 * Returns a BigInteger whose value is {@code (-this)}. 2160 * 2161 * @return {@code -this} 2162 */ 2163 public BigInteger negate() { 2164 return new BigInteger(this.mag, -this.signum); 2165 } 2166 2167 /** 2168 * Returns the signum function of this BigInteger. 2169 * 2170 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or 2171 * positive. 2172 */ 2173 public int signum() { 2174 return this.signum; 2175 } 2176 2177 // Modular Arithmetic Operations 2178 2179 /** 2180 * Returns a BigInteger whose value is {@code (this mod m}). This method 2181 * differs from {@code remainder} in that it always returns a 2182 * <i>non-negative</i> BigInteger. 2183 * 2184 * @param m the modulus. 2185 * @return {@code this mod m} 2186 * @throws ArithmeticException {@code m} ≤ 0 2187 * @see #remainder 2188 */ 2189 public BigInteger mod(BigInteger m) { 2190 if (m.signum <= 0) 2191 throw new ArithmeticException("BigInteger: modulus not positive"); 2192 2193 BigInteger result = this.remainder(m); 2194 return (result.signum >= 0 ? result : result.add(m)); 2195 } 2196 2197 /** 2198 * Returns a BigInteger whose value is 2199 * <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike {@code pow}, this 2200 * method permits negative exponents.) 2201 * 2202 * @param exponent the exponent. 2203 * @param m the modulus. 2204 * @return <tt>this<sup>exponent</sup> mod m</tt> 2205 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is 2206 * negative and this BigInteger is not <i>relatively 2207 * prime</i> to {@code m}. 2208 * @see #modInverse 2209 */ 2210 public BigInteger modPow(BigInteger exponent, BigInteger m) { 2211 if (m.signum <= 0) 2212 throw new ArithmeticException("BigInteger: modulus not positive"); 2213 2214 // Trivial cases 2215 if (exponent.signum == 0) 2216 return (m.equals(ONE) ? ZERO : ONE); 2217 2218 if (this.equals(ONE)) 2219 return (m.equals(ONE) ? ZERO : ONE); 2220 2221 if (this.equals(ZERO) && exponent.signum >= 0) 2222 return ZERO; 2223 2224 if (this.equals(negConst[1]) && (!exponent.testBit(0))) 2225 return (m.equals(ONE) ? ZERO : ONE); 2226 2227 boolean invertResult; 2228 if ((invertResult = (exponent.signum < 0))) 2229 exponent = exponent.negate(); 2230 2231 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0 2232 ? this.mod(m) : this); 2233 BigInteger result; 2234 if (m.testBit(0)) { // odd modulus 2235 result = base.oddModPow(exponent, m); 2236 } else { 2237 /* 2238 * Even modulus. Tear it into an "odd part" (m1) and power of two 2239 * (m2), exponentiate mod m1, manually exponentiate mod m2, and 2240 * use Chinese Remainder Theorem to combine results. 2241 */ 2242 2243 // Tear m apart into odd part (m1) and power of 2 (m2) 2244 int p = m.getLowestSetBit(); // Max pow of 2 that divides m 2245 2246 BigInteger m1 = m.shiftRight(p); // m/2**p 2247 BigInteger m2 = ONE.shiftLeft(p); // 2**p 2248 2249 // Calculate new base from m1 2250 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0 2251 ? this.mod(m1) : this); 2252 2253 // Caculate (base ** exponent) mod m1. 2254 BigInteger a1 = (m1.equals(ONE) ? ZERO : 2255 base2.oddModPow(exponent, m1)); 2256 2257 // Calculate (this ** exponent) mod m2 2258 BigInteger a2 = base.modPow2(exponent, p); 2259 2260 // Combine results using Chinese Remainder Theorem 2261 BigInteger y1 = m2.modInverse(m1); 2262 BigInteger y2 = m1.modInverse(m2); 2263 2264 result = a1.multiply(m2).multiply(y1).add 2265 (a2.multiply(m1).multiply(y2)).mod(m); 2266 } 2267 2268 return (invertResult ? result.modInverse(m) : result); 2269 } 2270 2271 static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793, 2272 Integer.MAX_VALUE}; // Sentinel 2273 2274 /** 2275 * Returns a BigInteger whose value is x to the power of y mod z. 2276 * Assumes: z is odd && x < z. 2277 */ 2278 private BigInteger oddModPow(BigInteger y, BigInteger z) { 2279 /* 2280 * The algorithm is adapted from Colin Plumb's C library. 2281 * 2282 * The window algorithm: 2283 * The idea is to keep a running product of b1 = n^(high-order bits of exp) 2284 * and then keep appending exponent bits to it. The following patterns 2285 * apply to a 3-bit window (k = 3): 2286 * To append 0: square 2287 * To append 1: square, multiply by n^1 2288 * To append 10: square, multiply by n^1, square 2289 * To append 11: square, square, multiply by n^3 2290 * To append 100: square, multiply by n^1, square, square 2291 * To append 101: square, square, square, multiply by n^5 2292 * To append 110: square, square, multiply by n^3, square 2293 * To append 111: square, square, square, multiply by n^7 2294 * 2295 * Since each pattern involves only one multiply, the longer the pattern 2296 * the better, except that a 0 (no multiplies) can be appended directly. 2297 * We precompute a table of odd powers of n, up to 2^k, and can then 2298 * multiply k bits of exponent at a time. Actually, assuming random 2299 * exponents, there is on average one zero bit between needs to 2300 * multiply (1/2 of the time there's none, 1/4 of the time there's 1, 2301 * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so 2302 * you have to do one multiply per k+1 bits of exponent. 2303 * 2304 * The loop walks down the exponent, squaring the result buffer as 2305 * it goes. There is a wbits+1 bit lookahead buffer, buf, that is 2306 * filled with the upcoming exponent bits. (What is read after the 2307 * end of the exponent is unimportant, but it is filled with zero here.) 2308 * When the most-significant bit of this buffer becomes set, i.e. 2309 * (buf & tblmask) != 0, we have to decide what pattern to multiply 2310 * by, and when to do it. We decide, remember to do it in future 2311 * after a suitable number of squarings have passed (e.g. a pattern 2312 * of "100" in the buffer requires that we multiply by n^1 immediately; 2313 * a pattern of "110" calls for multiplying by n^3 after one more 2314 * squaring), clear the buffer, and continue. 2315 * 2316 * When we start, there is one more optimization: the result buffer 2317 * is implcitly one, so squaring it or multiplying by it can be 2318 * optimized away. Further, if we start with a pattern like "100" 2319 * in the lookahead window, rather than placing n into the buffer 2320 * and then starting to square it, we have already computed n^2 2321 * to compute the odd-powers table, so we can place that into 2322 * the buffer and save a squaring. 2323 * 2324 * This means that if you have a k-bit window, to compute n^z, 2325 * where z is the high k bits of the exponent, 1/2 of the time 2326 * it requires no squarings. 1/4 of the time, it requires 1 2327 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings. 2328 * And the remaining 1/2^(k-1) of the time, the top k bits are a 2329 * 1 followed by k-1 0 bits, so it again only requires k-2 2330 * squarings, not k-1. The average of these is 1. Add that 2331 * to the one squaring we have to do to compute the table, 2332 * and you'll see that a k-bit window saves k-2 squarings 2333 * as well as reducing the multiplies. (It actually doesn't 2334 * hurt in the case k = 1, either.) 2335 */ 2336 // Special case for exponent of one 2337 if (y.equals(ONE)) 2338 return this; 2339 2340 // Special case for base of zero 2341 if (signum==0) 2342 return ZERO; 2343 2344 int[] base = mag.clone(); 2345 int[] exp = y.mag; 2346 int[] mod = z.mag; 2347 int modLen = mod.length; 2348 2349 // Select an appropriate window size 2350 int wbits = 0; 2351 int ebits = bitLength(exp, exp.length); 2352 // if exponent is 65537 (0x10001), use minimum window size 2353 if ((ebits != 17) || (exp[0] != 65537)) { 2354 while (ebits > bnExpModThreshTable[wbits]) { 2355 wbits++; 2356 } 2357 } 2358 2359 // Calculate appropriate table size 2360 int tblmask = 1 << wbits; 2361 2362 // Allocate table for precomputed odd powers of base in Montgomery form 2363 int[][] table = new int[tblmask][]; 2364 for (int i=0; i<tblmask; i++) 2365 table[i] = new int[modLen]; 2366 2367 // Compute the modular inverse 2368 int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]); 2369 2370 // Convert base to Montgomery form 2371 int[] a = leftShift(base, base.length, modLen << 5); 2372 2373 MutableBigInteger q = new MutableBigInteger(), 2374 a2 = new MutableBigInteger(a), 2375 b2 = new MutableBigInteger(mod); 2376 2377 MutableBigInteger r= a2.divide(b2, q); 2378 table[0] = r.toIntArray(); 2379 2380 // Pad table[0] with leading zeros so its length is at least modLen 2381 if (table[0].length < modLen) { 2382 int offset = modLen - table[0].length; 2383 int[] t2 = new int[modLen]; 2384 for (int i=0; i<table[0].length; i++) 2385 t2[i+offset] = table[0][i]; 2386 table[0] = t2; 2387 } 2388 2389 // Set b to the square of the base 2390 int[] b = squareToLen(table[0], modLen, null); 2391 b = montReduce(b, mod, modLen, inv); 2392 2393 // Set t to high half of b 2394 int[] t = Arrays.copyOf(b, modLen); 2395 2396 // Fill in the table with odd powers of the base 2397 for (int i=1; i<tblmask; i++) { 2398 int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null); 2399 table[i] = montReduce(prod, mod, modLen, inv); 2400 } 2401 2402 // Pre load the window that slides over the exponent 2403 int bitpos = 1 << ((ebits-1) & (32-1)); 2404 2405 int buf = 0; 2406 int elen = exp.length; 2407 int eIndex = 0; 2408 for (int i = 0; i <= wbits; i++) { 2409 buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0); 2410 bitpos >>>= 1; 2411 if (bitpos == 0) { 2412 eIndex++; 2413 bitpos = 1 << (32-1); 2414 elen--; 2415 } 2416 } 2417 2418 int multpos = ebits; 2419 2420 // The first iteration, which is hoisted out of the main loop 2421 ebits--; 2422 boolean isone = true; 2423 2424 multpos = ebits - wbits; 2425 while ((buf & 1) == 0) { 2426 buf >>>= 1; 2427 multpos++; 2428 } 2429 2430 int[] mult = table[buf >>> 1]; 2431 2432 buf = 0; 2433 if (multpos == ebits) 2434 isone = false; 2435 2436 // The main loop 2437 while(true) { 2438 ebits--; 2439 // Advance the window 2440 buf <<= 1; 2441 2442 if (elen != 0) { 2443 buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0; 2444 bitpos >>>= 1; 2445 if (bitpos == 0) { 2446 eIndex++; 2447 bitpos = 1 << (32-1); 2448 elen--; 2449 } 2450 } 2451 2452 // Examine the window for pending multiplies 2453 if ((buf & tblmask) != 0) { 2454 multpos = ebits - wbits; 2455 while ((buf & 1) == 0) { 2456 buf >>>= 1; 2457 multpos++; 2458 } 2459 mult = table[buf >>> 1]; 2460 buf = 0; 2461 } 2462 2463 // Perform multiply 2464 if (ebits == multpos) { 2465 if (isone) { 2466 b = mult.clone(); 2467 isone = false; 2468 } else { 2469 t = b; 2470 a = multiplyToLen(t, modLen, mult, modLen, a); 2471 a = montReduce(a, mod, modLen, inv); 2472 t = a; a = b; b = t; 2473 } 2474 } 2475 2476 // Check if done 2477 if (ebits == 0) 2478 break; 2479 2480 // Square the input 2481 if (!isone) { 2482 t = b; 2483 a = squareToLen(t, modLen, a); 2484 a = montReduce(a, mod, modLen, inv); 2485 t = a; a = b; b = t; 2486 } 2487 } 2488 2489 // Convert result out of Montgomery form and return 2490 int[] t2 = new int[2*modLen]; 2491 System.arraycopy(b, 0, t2, modLen, modLen); 2492 2493 b = montReduce(t2, mod, modLen, inv); 2494 2495 t2 = Arrays.copyOf(b, modLen); 2496 2497 return new BigInteger(1, t2); 2498 } 2499 2500 /** 2501 * Montgomery reduce n, modulo mod. This reduces modulo mod and divides 2502 * by 2^(32*mlen). Adapted from Colin Plumb's C library. 2503 */ 2504 private static int[] montReduce(int[] n, int[] mod, int mlen, int inv) { 2505 int c=0; 2506 int len = mlen; 2507 int offset=0; 2508 2509 do { 2510 int nEnd = n[n.length-1-offset]; 2511 int carry = mulAdd(n, mod, offset, mlen, inv * nEnd); 2512 c += addOne(n, offset, mlen, carry); 2513 offset++; 2514 } while(--len > 0); 2515 2516 while(c>0) 2517 c += subN(n, mod, mlen); 2518 2519 while (intArrayCmpToLen(n, mod, mlen) >= 0) 2520 subN(n, mod, mlen); 2521 2522 return n; 2523 } 2524 2525 2526 /* 2527 * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than, 2528 * equal to, or greater than arg2 up to length len. 2529 */ 2530 private static int intArrayCmpToLen(int[] arg1, int[] arg2, int len) { 2531 for (int i=0; i<len; i++) { 2532 long b1 = arg1[i] & LONG_MASK; 2533 long b2 = arg2[i] & LONG_MASK; 2534 if (b1 < b2) 2535 return -1; 2536 if (b1 > b2) 2537 return 1; 2538 } 2539 return 0; 2540 } 2541 2542 /** 2543 * Subtracts two numbers of same length, returning borrow. 2544 */ 2545 private static int subN(int[] a, int[] b, int len) { 2546 long sum = 0; 2547 2548 while(--len >= 0) { 2549 sum = (a[len] & LONG_MASK) - 2550 (b[len] & LONG_MASK) + (sum >> 32); 2551 a[len] = (int)sum; 2552 } 2553 2554 return (int)(sum >> 32); 2555 } 2556 2557 /** 2558 * Multiply an array by one word k and add to result, return the carry 2559 */ 2560 static int mulAdd(int[] out, int[] in, int offset, int len, int k) { 2561 long kLong = k & LONG_MASK; 2562 long carry = 0; 2563 2564 offset = out.length-offset - 1; 2565 for (int j=len-1; j >= 0; j--) { 2566 long product = (in[j] & LONG_MASK) * kLong + 2567 (out[offset] & LONG_MASK) + carry; 2568 out[offset--] = (int)product; 2569 carry = product >>> 32; 2570 } 2571 return (int)carry; 2572 } 2573 2574 /** 2575 * Add one word to the number a mlen words into a. Return the resulting 2576 * carry. 2577 */ 2578 static int addOne(int[] a, int offset, int mlen, int carry) { 2579 offset = a.length-1-mlen-offset; 2580 long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK); 2581 2582 a[offset] = (int)t; 2583 if ((t >>> 32) == 0) 2584 return 0; 2585 while (--mlen >= 0) { 2586 if (--offset < 0) { // Carry out of number 2587 return 1; 2588 } else { 2589 a[offset]++; 2590 if (a[offset] != 0) 2591 return 0; 2592 } 2593 } 2594 return 1; 2595 } 2596 2597 /** 2598 * Returns a BigInteger whose value is (this ** exponent) mod (2**p) 2599 */ 2600 private BigInteger modPow2(BigInteger exponent, int p) { 2601 /* 2602 * Perform exponentiation using repeated squaring trick, chopping off 2603 * high order bits as indicated by modulus. 2604 */ 2605 BigInteger result = ONE; 2606 BigInteger baseToPow2 = this.mod2(p); 2607 int expOffset = 0; 2608 2609 int limit = exponent.bitLength(); 2610 2611 if (this.testBit(0)) 2612 limit = (p-1) < limit ? (p-1) : limit; 2613 2614 while (expOffset < limit) { 2615 if (exponent.testBit(expOffset)) 2616 result = result.multiply(baseToPow2).mod2(p); 2617 expOffset++; 2618 if (expOffset < limit) 2619 baseToPow2 = baseToPow2.square().mod2(p); 2620 } 2621 2622 return result; 2623 } 2624 2625 /** 2626 * Returns a BigInteger whose value is this mod(2**p). 2627 * Assumes that this {@code BigInteger >= 0} and {@code p > 0}. 2628 */ 2629 private BigInteger mod2(int p) { 2630 if (bitLength() <= p) 2631 return this; 2632 2633 // Copy remaining ints of mag 2634 int numInts = (p + 31) >>> 5; 2635 int[] mag = new int[numInts]; 2636 System.arraycopy(this.mag, (this.mag.length - numInts), mag, 0, numInts); 2637 2638 // Mask out any excess bits 2639 int excessBits = (numInts << 5) - p; 2640 mag[0] &= (1L << (32-excessBits)) - 1; 2641 2642 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1)); 2643 } 2644 2645 /** 2646 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}. 2647 * 2648 * @param m the modulus. 2649 * @return {@code this}<sup>-1</sup> {@code mod m}. 2650 * @throws ArithmeticException {@code m} ≤ 0, or this BigInteger 2651 * has no multiplicative inverse mod m (that is, this BigInteger 2652 * is not <i>relatively prime</i> to m). 2653 */ 2654 public BigInteger modInverse(BigInteger m) { 2655 if (m.signum != 1) 2656 throw new ArithmeticException("BigInteger: modulus not positive"); 2657 2658 if (m.equals(ONE)) 2659 return ZERO; 2660 2661 // Calculate (this mod m) 2662 BigInteger modVal = this; 2663 if (signum < 0 || (this.compareMagnitude(m) >= 0)) 2664 modVal = this.mod(m); 2665 2666 if (modVal.equals(ONE)) 2667 return ONE; 2668 2669 MutableBigInteger a = new MutableBigInteger(modVal); 2670 MutableBigInteger b = new MutableBigInteger(m); 2671 2672 MutableBigInteger result = a.mutableModInverse(b); 2673 return result.toBigInteger(1); 2674 } 2675 2676 // Shift Operations 2677 2678 /** 2679 * Returns a BigInteger whose value is {@code (this << n)}. 2680 * The shift distance, {@code n}, may be negative, in which case 2681 * this method performs a right shift. 2682 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.) 2683 * 2684 * @param n shift distance, in bits. 2685 * @return {@code this << n} 2686 * @throws ArithmeticException if the shift distance is {@code 2687 * Integer.MIN_VALUE}. 2688 * @see #shiftRight 2689 */ 2690 public BigInteger shiftLeft(int n) { 2691 if (signum == 0) 2692 return ZERO; 2693 if (n==0) 2694 return this; 2695 if (n<0) { 2696 if (n == Integer.MIN_VALUE) { 2697 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); 2698 } else { 2699 return shiftRight(-n); 2700 } 2701 } 2702 int[] newMag = shiftLeft(mag, n); 2703 2704 return new BigInteger(newMag, signum); 2705 } 2706 2707 private static int[] shiftLeft(int[] mag, int n) { 2708 int nInts = n >>> 5; 2709 int nBits = n & 0x1f; 2710 int magLen = mag.length; 2711 int newMag[] = null; 2712 2713 if (nBits == 0) { 2714 newMag = new int[magLen + nInts]; 2715 System.arraycopy(mag, 0, newMag, 0, magLen); 2716 } else { 2717 int i = 0; 2718 int nBits2 = 32 - nBits; 2719 int highBits = mag[0] >>> nBits2; 2720 if (highBits != 0) { 2721 newMag = new int[magLen + nInts + 1]; 2722 newMag[i++] = highBits; 2723 } else { 2724 newMag = new int[magLen + nInts]; 2725 } 2726 int j=0; 2727 while (j < magLen-1) 2728 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2; 2729 newMag[i] = mag[j] << nBits; 2730 } 2731 return newMag; 2732 } 2733 2734 /** 2735 * Returns a BigInteger whose value is {@code (this >> n)}. Sign 2736 * extension is performed. The shift distance, {@code n}, may be 2737 * negative, in which case this method performs a left shift. 2738 * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.) 2739 * 2740 * @param n shift distance, in bits. 2741 * @return {@code this >> n} 2742 * @throws ArithmeticException if the shift distance is {@code 2743 * Integer.MIN_VALUE}. 2744 * @see #shiftLeft 2745 */ 2746 public BigInteger shiftRight(int n) { 2747 if (n==0) 2748 return this; 2749 if (n<0) { 2750 if (n == Integer.MIN_VALUE) { 2751 throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported."); 2752 } else { 2753 return shiftLeft(-n); 2754 } 2755 } 2756 2757 int nInts = n >>> 5; 2758 int nBits = n & 0x1f; 2759 int magLen = mag.length; 2760 int newMag[] = null; 2761 2762 // Special case: entire contents shifted off the end 2763 if (nInts >= magLen) 2764 return (signum >= 0 ? ZERO : negConst[1]); 2765 2766 if (nBits == 0) { 2767 int newMagLen = magLen - nInts; 2768 newMag = Arrays.copyOf(mag, newMagLen); 2769 } else { 2770 int i = 0; 2771 int highBits = mag[0] >>> nBits; 2772 if (highBits != 0) { 2773 newMag = new int[magLen - nInts]; 2774 newMag[i++] = highBits; 2775 } else { 2776 newMag = new int[magLen - nInts -1]; 2777 } 2778 2779 int nBits2 = 32 - nBits; 2780 int j=0; 2781 while (j < magLen - nInts - 1) 2782 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits); 2783 } 2784 2785 if (signum < 0) { 2786 // Find out whether any one-bits were shifted off the end. 2787 boolean onesLost = false; 2788 for (int i=magLen-1, j=magLen-nInts; i>=j && !onesLost; i--) 2789 onesLost = (mag[i] != 0); 2790 if (!onesLost && nBits != 0) 2791 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0); 2792 2793 if (onesLost) 2794 newMag = javaIncrement(newMag); 2795 } 2796 2797 return new BigInteger(newMag, signum); 2798 } 2799 2800 int[] javaIncrement(int[] val) { 2801 int lastSum = 0; 2802 for (int i=val.length-1; i >= 0 && lastSum == 0; i--) 2803 lastSum = (val[i] += 1); 2804 if (lastSum == 0) { 2805 val = new int[val.length+1]; 2806 val[0] = 1; 2807 } 2808 return val; 2809 } 2810 2811 // Bitwise Operations 2812 2813 /** 2814 * Returns a BigInteger whose value is {@code (this & val)}. (This 2815 * method returns a negative BigInteger if and only if this and val are 2816 * both negative.) 2817 * 2818 * @param val value to be AND'ed with this BigInteger. 2819 * @return {@code this & val} 2820 */ 2821 public BigInteger and(BigInteger val) { 2822 int[] result = new int[Math.max(intLength(), val.intLength())]; 2823 for (int i=0; i<result.length; i++) 2824 result[i] = (getInt(result.length-i-1) 2825 & val.getInt(result.length-i-1)); 2826 2827 return valueOf(result); 2828 } 2829 2830 /** 2831 * Returns a BigInteger whose value is {@code (this | val)}. (This method 2832 * returns a negative BigInteger if and only if either this or val is 2833 * negative.) 2834 * 2835 * @param val value to be OR'ed with this BigInteger. 2836 * @return {@code this | val} 2837 */ 2838 public BigInteger or(BigInteger val) { 2839 int[] result = new int[Math.max(intLength(), val.intLength())]; 2840 for (int i=0; i<result.length; i++) 2841 result[i] = (getInt(result.length-i-1) 2842 | val.getInt(result.length-i-1)); 2843 2844 return valueOf(result); 2845 } 2846 2847 /** 2848 * Returns a BigInteger whose value is {@code (this ^ val)}. (This method 2849 * returns a negative BigInteger if and only if exactly one of this and 2850 * val are negative.) 2851 * 2852 * @param val value to be XOR'ed with this BigInteger. 2853 * @return {@code this ^ val} 2854 */ 2855 public BigInteger xor(BigInteger val) { 2856 int[] result = new int[Math.max(intLength(), val.intLength())]; 2857 for (int i=0; i<result.length; i++) 2858 result[i] = (getInt(result.length-i-1) 2859 ^ val.getInt(result.length-i-1)); 2860 2861 return valueOf(result); 2862 } 2863 2864 /** 2865 * Returns a BigInteger whose value is {@code (~this)}. (This method 2866 * returns a negative value if and only if this BigInteger is 2867 * non-negative.) 2868 * 2869 * @return {@code ~this} 2870 */ 2871 public BigInteger not() { 2872 int[] result = new int[intLength()]; 2873 for (int i=0; i<result.length; i++) 2874 result[i] = ~getInt(result.length-i-1); 2875 2876 return valueOf(result); 2877 } 2878 2879 /** 2880 * Returns a BigInteger whose value is {@code (this & ~val)}. This 2881 * method, which is equivalent to {@code and(val.not())}, is provided as 2882 * a convenience for masking operations. (This method returns a negative 2883 * BigInteger if and only if {@code this} is negative and {@code val} is 2884 * positive.) 2885 * 2886 * @param val value to be complemented and AND'ed with this BigInteger. 2887 * @return {@code this & ~val} 2888 */ 2889 public BigInteger andNot(BigInteger val) { 2890 int[] result = new int[Math.max(intLength(), val.intLength())]; 2891 for (int i=0; i<result.length; i++) 2892 result[i] = (getInt(result.length-i-1) 2893 & ~val.getInt(result.length-i-1)); 2894 2895 return valueOf(result); 2896 } 2897 2898 2899 // Single Bit Operations 2900 2901 /** 2902 * Returns {@code true} if and only if the designated bit is set. 2903 * (Computes {@code ((this & (1<<n)) != 0)}.) 2904 * 2905 * @param n index of bit to test. 2906 * @return {@code true} if and only if the designated bit is set. 2907 * @throws ArithmeticException {@code n} is negative. 2908 */ 2909 public boolean testBit(int n) { 2910 if (n<0) 2911 throw new ArithmeticException("Negative bit address"); 2912 2913 return (getInt(n >>> 5) & (1 << (n & 31))) != 0; 2914 } 2915 2916 /** 2917 * Returns a BigInteger whose value is equivalent to this BigInteger 2918 * with the designated bit set. (Computes {@code (this | (1<<n))}.) 2919 * 2920 * @param n index of bit to set. 2921 * @return {@code this | (1<<n)} 2922 * @throws ArithmeticException {@code n} is negative. 2923 */ 2924 public BigInteger setBit(int n) { 2925 if (n<0) 2926 throw new ArithmeticException("Negative bit address"); 2927 2928 int intNum = n >>> 5; 2929 int[] result = new int[Math.max(intLength(), intNum+2)]; 2930 2931 for (int i=0; i<result.length; i++) 2932 result[result.length-i-1] = getInt(i); 2933 2934 result[result.length-intNum-1] |= (1 << (n & 31)); 2935 2936 return valueOf(result); 2937 } 2938 2939 /** 2940 * Returns a BigInteger whose value is equivalent to this BigInteger 2941 * with the designated bit cleared. 2942 * (Computes {@code (this & ~(1<<n))}.) 2943 * 2944 * @param n index of bit to clear. 2945 * @return {@code this & ~(1<<n)} 2946 * @throws ArithmeticException {@code n} is negative. 2947 */ 2948 public BigInteger clearBit(int n) { 2949 if (n<0) 2950 throw new ArithmeticException("Negative bit address"); 2951 2952 int intNum = n >>> 5; 2953 int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)]; 2954 2955 for (int i=0; i<result.length; i++) 2956 result[result.length-i-1] = getInt(i); 2957 2958 result[result.length-intNum-1] &= ~(1 << (n & 31)); 2959 2960 return valueOf(result); 2961 } 2962 2963 /** 2964 * Returns a BigInteger whose value is equivalent to this BigInteger 2965 * with the designated bit flipped. 2966 * (Computes {@code (this ^ (1<<n))}.) 2967 * 2968 * @param n index of bit to flip. 2969 * @return {@code this ^ (1<<n)} 2970 * @throws ArithmeticException {@code n} is negative. 2971 */ 2972 public BigInteger flipBit(int n) { 2973 if (n<0) 2974 throw new ArithmeticException("Negative bit address"); 2975 2976 int intNum = n >>> 5; 2977 int[] result = new int[Math.max(intLength(), intNum+2)]; 2978 2979 for (int i=0; i<result.length; i++) 2980 result[result.length-i-1] = getInt(i); 2981 2982 result[result.length-intNum-1] ^= (1 << (n & 31)); 2983 2984 return valueOf(result); 2985 } 2986 2987 /** 2988 * Returns the index of the rightmost (lowest-order) one bit in this 2989 * BigInteger (the number of zero bits to the right of the rightmost 2990 * one bit). Returns -1 if this BigInteger contains no one bits. 2991 * (Computes {@code (this==0? -1 : log2(this & -this))}.) 2992 * 2993 * @return index of the rightmost one bit in this BigInteger. 2994 */ 2995 public int getLowestSetBit() { 2996 @SuppressWarnings("deprecation") int lsb = lowestSetBit - 2; 2997 if (lsb == -2) { // lowestSetBit not initialized yet 2998 lsb = 0; 2999 if (signum == 0) { 3000 lsb -= 1; 3001 } else { 3002 // Search for lowest order nonzero int 3003 int i,b; 3004 for (i=0; (b = getInt(i))==0; i++) 3005 ; 3006 lsb += (i << 5) + Integer.numberOfTrailingZeros(b); 3007 } 3008 lowestSetBit = lsb + 2; 3009 } 3010 return lsb; 3011 } 3012 3013 3014 // Miscellaneous Bit Operations 3015 3016 /** 3017 * Returns the number of bits in the minimal two's-complement 3018 * representation of this BigInteger, <i>excluding</i> a sign bit. 3019 * For positive BigIntegers, this is equivalent to the number of bits in 3020 * the ordinary binary representation. (Computes 3021 * {@code (ceil(log2(this < 0 ? -this : this+1)))}.) 3022 * 3023 * @return number of bits in the minimal two's-complement 3024 * representation of this BigInteger, <i>excluding</i> a sign bit. 3025 */ 3026 public int bitLength() { 3027 @SuppressWarnings("deprecation") int n = bitLength - 1; 3028 if (n == -1) { // bitLength not initialized yet 3029 int[] m = mag; 3030 int len = m.length; 3031 if (len == 0) { 3032 n = 0; // offset by one to initialize 3033 } else { 3034 // Calculate the bit length of the magnitude 3035 int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]); 3036 if (signum < 0) { 3037 // Check if magnitude is a power of two 3038 boolean pow2 = (Integer.bitCount(mag[0]) == 1); 3039 for (int i=1; i< len && pow2; i++) 3040 pow2 = (mag[i] == 0); 3041 3042 n = (pow2 ? magBitLength -1 : magBitLength); 3043 } else { 3044 n = magBitLength; 3045 } 3046 } 3047 bitLength = n + 1; 3048 } 3049 return n; 3050 } 3051 3052 /** 3053 * Returns the number of bits in the two's complement representation 3054 * of this BigInteger that differ from its sign bit. This method is 3055 * useful when implementing bit-vector style sets atop BigIntegers. 3056 * 3057 * @return number of bits in the two's complement representation 3058 * of this BigInteger that differ from its sign bit. 3059 */ 3060 public int bitCount() { 3061 @SuppressWarnings("deprecation") int bc = bitCount - 1; 3062 if (bc == -1) { // bitCount not initialized yet 3063 bc = 0; // offset by one to initialize 3064 // Count the bits in the magnitude 3065 for (int i=0; i<mag.length; i++) 3066 bc += Integer.bitCount(mag[i]); 3067 if (signum < 0) { 3068 // Count the trailing zeros in the magnitude 3069 int magTrailingZeroCount = 0, j; 3070 for (j=mag.length-1; mag[j]==0; j--) 3071 magTrailingZeroCount += 32; 3072 magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]); 3073 bc += magTrailingZeroCount - 1; 3074 } 3075 bitCount = bc + 1; 3076 } 3077 return bc; 3078 } 3079 3080 // Primality Testing 3081 3082 /** 3083 * Returns {@code true} if this BigInteger is probably prime, 3084 * {@code false} if it's definitely composite. If 3085 * {@code certainty} is ≤ 0, {@code true} is 3086 * returned. 3087 * 3088 * @param certainty a measure of the uncertainty that the caller is 3089 * willing to tolerate: if the call returns {@code true} 3090 * the probability that this BigInteger is prime exceeds 3091 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of 3092 * this method is proportional to the value of this parameter. 3093 * @return {@code true} if this BigInteger is probably prime, 3094 * {@code false} if it's definitely composite. 3095 */ 3096 public boolean isProbablePrime(int certainty) { 3097 if (certainty <= 0) 3098 return true; 3099 BigInteger w = this.abs(); 3100 if (w.equals(TWO)) 3101 return true; 3102 if (!w.testBit(0) || w.equals(ONE)) 3103 return false; 3104 3105 return w.primeToCertainty(certainty, null); 3106 } 3107 3108 // Comparison Operations 3109 3110 /** 3111 * Compares this BigInteger with the specified BigInteger. This 3112 * method is provided in preference to individual methods for each 3113 * of the six boolean comparison operators ({@literal <}, ==, 3114 * {@literal >}, {@literal >=}, !=, {@literal <=}). The suggested 3115 * idiom for performing these comparisons is: {@code 3116 * (x.compareTo(y)} <<i>op</i>> {@code 0)}, where 3117 * <<i>op</i>> is one of the six comparison operators. 3118 * 3119 * @param val BigInteger to which this BigInteger is to be compared. 3120 * @return -1, 0 or 1 as this BigInteger is numerically less than, equal 3121 * to, or greater than {@code val}. 3122 */ 3123 public int compareTo(BigInteger val) { 3124 if (signum == val.signum) { 3125 switch (signum) { 3126 case 1: 3127 return compareMagnitude(val); 3128 case -1: 3129 return val.compareMagnitude(this); 3130 default: 3131 return 0; 3132 } 3133 } 3134 return signum > val.signum ? 1 : -1; 3135 } 3136 3137 /** 3138 * Compares the magnitude array of this BigInteger with the specified 3139 * BigInteger's. This is the version of compareTo ignoring sign. 3140 * 3141 * @param val BigInteger whose magnitude array to be compared. 3142 * @return -1, 0 or 1 as this magnitude array is less than, equal to or 3143 * greater than the magnitude aray for the specified BigInteger's. 3144 */ 3145 final int compareMagnitude(BigInteger val) { 3146 int[] m1 = mag; 3147 int len1 = m1.length; 3148 int[] m2 = val.mag; 3149 int len2 = m2.length; 3150 if (len1 < len2) 3151 return -1; 3152 if (len1 > len2) 3153 return 1; 3154 for (int i = 0; i < len1; i++) { 3155 int a = m1[i]; 3156 int b = m2[i]; 3157 if (a != b) 3158 return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1; 3159 } 3160 return 0; 3161 } 3162 3163 /** 3164 * Version of compareMagnitude that compares magnitude with long value. 3165 * val can't be Long.MIN_VALUE. 3166 */ 3167 final int compareMagnitude(long val) { 3168 assert val != Long.MIN_VALUE; 3169 int[] m1 = mag; 3170 int len = m1.length; 3171 if(len > 2) { 3172 return 1; 3173 } 3174 if (val < 0) { 3175 val = -val; 3176 } 3177 int highWord = (int)(val >>> 32); 3178 if (highWord==0) { 3179 if (len < 1) 3180 return -1; 3181 if (len > 1) 3182 return 1; 3183 int a = m1[0]; 3184 int b = (int)val; 3185 if (a != b) { 3186 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 3187 } 3188 return 0; 3189 } else { 3190 if (len < 2) 3191 return -1; 3192 int a = m1[0]; 3193 int b = highWord; 3194 if (a != b) { 3195 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 3196 } 3197 a = m1[1]; 3198 b = (int)val; 3199 if (a != b) { 3200 return ((a & LONG_MASK) < (b & LONG_MASK))? -1 : 1; 3201 } 3202 return 0; 3203 } 3204 } 3205 3206 /** 3207 * Compares this BigInteger with the specified Object for equality. 3208 * 3209 * @param x Object to which this BigInteger is to be compared. 3210 * @return {@code true} if and only if the specified Object is a 3211 * BigInteger whose value is numerically equal to this BigInteger. 3212 */ 3213 public boolean equals(Object x) { 3214 // This test is just an optimization, which may or may not help 3215 if (x == this) 3216 return true; 3217 3218 if (!(x instanceof BigInteger)) 3219 return false; 3220 3221 BigInteger xInt = (BigInteger) x; 3222 if (xInt.signum != signum) 3223 return false; 3224 3225 int[] m = mag; 3226 int len = m.length; 3227 int[] xm = xInt.mag; 3228 if (len != xm.length) 3229 return false; 3230 3231 for (int i = 0; i < len; i++) 3232 if (xm[i] != m[i]) 3233 return false; 3234 3235 return true; 3236 } 3237 3238 /** 3239 * Returns the minimum of this BigInteger and {@code val}. 3240 * 3241 * @param val value with which the minimum is to be computed. 3242 * @return the BigInteger whose value is the lesser of this BigInteger and 3243 * {@code val}. If they are equal, either may be returned. 3244 */ 3245 public BigInteger min(BigInteger val) { 3246 return (compareTo(val)<0 ? this : val); 3247 } 3248 3249 /** 3250 * Returns the maximum of this BigInteger and {@code val}. 3251 * 3252 * @param val value with which the maximum is to be computed. 3253 * @return the BigInteger whose value is the greater of this and 3254 * {@code val}. If they are equal, either may be returned. 3255 */ 3256 public BigInteger max(BigInteger val) { 3257 return (compareTo(val)>0 ? this : val); 3258 } 3259 3260 3261 // Hash Function 3262 3263 /** 3264 * Returns the hash code for this BigInteger. 3265 * 3266 * @return hash code for this BigInteger. 3267 */ 3268 public int hashCode() { 3269 int hashCode = 0; 3270 3271 for (int i=0; i<mag.length; i++) 3272 hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK)); 3273 3274 return hashCode * signum; 3275 } 3276 3277 /** 3278 * Returns the String representation of this BigInteger in the 3279 * given radix. If the radix is outside the range from {@link 3280 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive, 3281 * it will default to 10 (as is the case for 3282 * {@code Integer.toString}). The digit-to-character mapping 3283 * provided by {@code Character.forDigit} is used, and a minus 3284 * sign is prepended if appropriate. (This representation is 3285 * compatible with the {@link #BigInteger(String, int) (String, 3286 * int)} constructor.) 3287 * 3288 * @param radix radix of the String representation. 3289 * @return String representation of this BigInteger in the given radix. 3290 * @see Integer#toString 3291 * @see Character#forDigit 3292 * @see #BigInteger(java.lang.String, int) 3293 */ 3294 public String toString(int radix) { 3295 if (signum == 0) 3296 return "0"; 3297 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) 3298 radix = 10; 3299 3300 // Compute upper bound on number of digit groups and allocate space 3301 int maxNumDigitGroups = (4*mag.length + 6)/7; 3302 String digitGroup[] = new String[maxNumDigitGroups]; 3303 3304 // Translate number to string, a digit group at a time 3305 BigInteger tmp = this.abs(); 3306 int numGroups = 0; 3307 while (tmp.signum != 0) { 3308 BigInteger d = longRadix[radix]; 3309 3310 MutableBigInteger q = new MutableBigInteger(), 3311 a = new MutableBigInteger(tmp.mag), 3312 b = new MutableBigInteger(d.mag); 3313 MutableBigInteger r = a.divide(b, q); 3314 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum); 3315 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum); 3316 3317 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix); 3318 tmp = q2; 3319 } 3320 3321 // Put sign (if any) and first digit group into result buffer 3322 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1); 3323 if (signum<0) 3324 buf.append('-'); 3325 buf.append(digitGroup[numGroups-1]); 3326 3327 // Append remaining digit groups padded with leading zeros 3328 for (int i=numGroups-2; i>=0; i--) { 3329 // Prepend (any) leading zeros for this digit group 3330 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length(); 3331 if (numLeadingZeros != 0) 3332 buf.append(zeros[numLeadingZeros]); 3333 buf.append(digitGroup[i]); 3334 } 3335 return buf.toString(); 3336 } 3337 3338 3339 /* zero[i] is a string of i consecutive zeros. */ 3340 private static String zeros[] = new String[64]; 3341 static { 3342 zeros[63] = 3343 "000000000000000000000000000000000000000000000000000000000000000"; 3344 for (int i=0; i<63; i++) 3345 zeros[i] = zeros[63].substring(0, i); 3346 } 3347 3348 /** 3349 * Returns the decimal String representation of this BigInteger. 3350 * The digit-to-character mapping provided by 3351 * {@code Character.forDigit} is used, and a minus sign is 3352 * prepended if appropriate. (This representation is compatible 3353 * with the {@link #BigInteger(String) (String)} constructor, and 3354 * allows for String concatenation with Java's + operator.) 3355 * 3356 * @return decimal String representation of this BigInteger. 3357 * @see Character#forDigit 3358 * @see #BigInteger(java.lang.String) 3359 */ 3360 public String toString() { 3361 return toString(10); 3362 } 3363 3364 /** 3365 * Returns a byte array containing the two's-complement 3366 * representation of this BigInteger. The byte array will be in 3367 * <i>big-endian</i> byte-order: the most significant byte is in 3368 * the zeroth element. The array will contain the minimum number 3369 * of bytes required to represent this BigInteger, including at 3370 * least one sign bit, which is {@code (ceil((this.bitLength() + 3371 * 1)/8))}. (This representation is compatible with the 3372 * {@link #BigInteger(byte[]) (byte[])} constructor.) 3373 * 3374 * @return a byte array containing the two's-complement representation of 3375 * this BigInteger. 3376 * @see #BigInteger(byte[]) 3377 */ 3378 public byte[] toByteArray() { 3379 int byteLen = bitLength()/8 + 1; 3380 byte[] byteArray = new byte[byteLen]; 3381 3382 for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i>=0; i--) { 3383 if (bytesCopied == 4) { 3384 nextInt = getInt(intIndex++); 3385 bytesCopied = 1; 3386 } else { 3387 nextInt >>>= 8; 3388 bytesCopied++; 3389 } 3390 byteArray[i] = (byte)nextInt; 3391 } 3392 return byteArray; 3393 } 3394 3395 /** 3396 * Converts this BigInteger to an {@code int}. This 3397 * conversion is analogous to a 3398 * <i>narrowing primitive conversion</i> from {@code long} to 3399 * {@code int} as defined in section 5.1.3 of 3400 * <cite>The Java™ Language Specification</cite>: 3401 * if this BigInteger is too big to fit in an 3402 * {@code int}, only the low-order 32 bits are returned. 3403 * Note that this conversion can lose information about the 3404 * overall magnitude of the BigInteger value as well as return a 3405 * result with the opposite sign. 3406 * 3407 * @return this BigInteger converted to an {@code int}. 3408 * @see #intValueExact() 3409 */ 3410 public int intValue() { 3411 int result = 0; 3412 result = getInt(0); 3413 return result; 3414 } 3415 3416 /** 3417 * Converts this BigInteger to a {@code long}. This 3418 * conversion is analogous to a 3419 * <i>narrowing primitive conversion</i> from {@code long} to 3420 * {@code int} as defined in section 5.1.3 of 3421 * <cite>The Java™ Language Specification</cite>: 3422 * if this BigInteger is too big to fit in a 3423 * {@code long}, only the low-order 64 bits are returned. 3424 * Note that this conversion can lose information about the 3425 * overall magnitude of the BigInteger value as well as return a 3426 * result with the opposite sign. 3427 * 3428 * @return this BigInteger converted to a {@code long}. 3429 * @see #longValueExact() 3430 */ 3431 public long longValue() { 3432 long result = 0; 3433 3434 for (int i=1; i>=0; i--) 3435 result = (result << 32) + (getInt(i) & LONG_MASK); 3436 return result; 3437 } 3438 3439 /** 3440 * Converts this BigInteger to a {@code float}. This 3441 * conversion is similar to the 3442 * <i>narrowing primitive conversion</i> from {@code double} to 3443 * {@code float} as defined in section 5.1.3 of 3444 * <cite>The Java™ Language Specification</cite>: 3445 * if this BigInteger has too great a magnitude 3446 * to represent as a {@code float}, it will be converted to 3447 * {@link Float#NEGATIVE_INFINITY} or {@link 3448 * Float#POSITIVE_INFINITY} as appropriate. Note that even when 3449 * the return value is finite, this conversion can lose 3450 * information about the precision of the BigInteger value. 3451 * 3452 * @return this BigInteger converted to a {@code float}. 3453 */ 3454 public float floatValue() { 3455 // Somewhat inefficient, but guaranteed to work. 3456 return Float.parseFloat(this.toString()); 3457 } 3458 3459 /** 3460 * Converts this BigInteger to a {@code double}. This 3461 * conversion is similar to the 3462 * <i>narrowing primitive conversion</i> from {@code double} to 3463 * {@code float} as defined in section 5.1.3 of 3464 * <cite>The Java™ Language Specification</cite>: 3465 * if this BigInteger has too great a magnitude 3466 * to represent as a {@code double}, it will be converted to 3467 * {@link Double#NEGATIVE_INFINITY} or {@link 3468 * Double#POSITIVE_INFINITY} as appropriate. Note that even when 3469 * the return value is finite, this conversion can lose 3470 * information about the precision of the BigInteger value. 3471 * 3472 * @return this BigInteger converted to a {@code double}. 3473 */ 3474 public double doubleValue() { 3475 // Somewhat inefficient, but guaranteed to work. 3476 return Double.parseDouble(this.toString()); 3477 } 3478 3479 /** 3480 * Returns a copy of the input array stripped of any leading zero bytes. 3481 */ 3482 private static int[] stripLeadingZeroInts(int val[]) { 3483 int vlen = val.length; 3484 int keep; 3485 3486 // Find first nonzero byte 3487 for (keep = 0; keep < vlen && val[keep] == 0; keep++) 3488 ; 3489 return java.util.Arrays.copyOfRange(val, keep, vlen); 3490 } 3491 3492 /** 3493 * Returns the input array stripped of any leading zero bytes. 3494 * Since the source is trusted the copying may be skipped. 3495 */ 3496 private static int[] trustedStripLeadingZeroInts(int val[]) { 3497 int vlen = val.length; 3498 int keep; 3499 3500 // Find first nonzero byte 3501 for (keep = 0; keep < vlen && val[keep] == 0; keep++) 3502 ; 3503 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen); 3504 } 3505 3506 /** 3507 * Returns a copy of the input array stripped of any leading zero bytes. 3508 */ 3509 private static int[] stripLeadingZeroBytes(byte a[]) { 3510 int byteLength = a.length; 3511 int keep; 3512 3513 // Find first nonzero byte 3514 for (keep = 0; keep < byteLength && a[keep]==0; keep++) 3515 ; 3516 3517 // Allocate new array and copy relevant part of input array 3518 int intLength = ((byteLength - keep) + 3) >>> 2; 3519 int[] result = new int[intLength]; 3520 int b = byteLength - 1; 3521 for (int i = intLength-1; i >= 0; i--) { 3522 result[i] = a[b--] & 0xff; 3523 int bytesRemaining = b - keep + 1; 3524 int bytesToTransfer = Math.min(3, bytesRemaining); 3525 for (int j=8; j <= (bytesToTransfer << 3); j += 8) 3526 result[i] |= ((a[b--] & 0xff) << j); 3527 } 3528 return result; 3529 } 3530 3531 /** 3532 * Takes an array a representing a negative 2's-complement number and 3533 * returns the minimal (no leading zero bytes) unsigned whose value is -a. 3534 */ 3535 private static int[] makePositive(byte a[]) { 3536 int keep, k; 3537 int byteLength = a.length; 3538 3539 // Find first non-sign (0xff) byte of input 3540 for (keep=0; keep<byteLength && a[keep]==-1; keep++) 3541 ; 3542 3543 3544 /* Allocate output array. If all non-sign bytes are 0x00, we must 3545 * allocate space for one extra output byte. */ 3546 for (k=keep; k<byteLength && a[k]==0; k++) 3547 ; 3548 3549 int extraByte = (k==byteLength) ? 1 : 0; 3550 int intLength = ((byteLength - keep + extraByte) + 3)/4; 3551 int result[] = new int[intLength]; 3552 3553 /* Copy one's complement of input into output, leaving extra 3554 * byte (if it exists) == 0x00 */ 3555 int b = byteLength - 1; 3556 for (int i = intLength-1; i >= 0; i--) { 3557 result[i] = a[b--] & 0xff; 3558 int numBytesToTransfer = Math.min(3, b-keep+1); 3559 if (numBytesToTransfer < 0) 3560 numBytesToTransfer = 0; 3561 for (int j=8; j <= 8*numBytesToTransfer; j += 8) 3562 result[i] |= ((a[b--] & 0xff) << j); 3563 3564 // Mask indicates which bits must be complemented 3565 int mask = -1 >>> (8*(3-numBytesToTransfer)); 3566 result[i] = ~result[i] & mask; 3567 } 3568 3569 // Add one to one's complement to generate two's complement 3570 for (int i=result.length-1; i>=0; i--) { 3571 result[i] = (int)((result[i] & LONG_MASK) + 1); 3572 if (result[i] != 0) 3573 break; 3574 } 3575 3576 return result; 3577 } 3578 3579 /** 3580 * Takes an array a representing a negative 2's-complement number and 3581 * returns the minimal (no leading zero ints) unsigned whose value is -a. 3582 */ 3583 private static int[] makePositive(int a[]) { 3584 int keep, j; 3585 3586 // Find first non-sign (0xffffffff) int of input 3587 for (keep=0; keep<a.length && a[keep]==-1; keep++) 3588 ; 3589 3590 /* Allocate output array. If all non-sign ints are 0x00, we must 3591 * allocate space for one extra output int. */ 3592 for (j=keep; j<a.length && a[j]==0; j++) 3593 ; 3594 int extraInt = (j==a.length ? 1 : 0); 3595 int result[] = new int[a.length - keep + extraInt]; 3596 3597 /* Copy one's complement of input into output, leaving extra 3598 * int (if it exists) == 0x00 */ 3599 for (int i = keep; i<a.length; i++) 3600 result[i - keep + extraInt] = ~a[i]; 3601 3602 // Add one to one's complement to generate two's complement 3603 for (int i=result.length-1; ++result[i]==0; i--) 3604 ; 3605 3606 return result; 3607 } 3608 3609 /* 3610 * The following two arrays are used for fast String conversions. Both 3611 * are indexed by radix. The first is the number of digits of the given 3612 * radix that can fit in a Java long without "going negative", i.e., the 3613 * highest integer n such that radix**n < 2**63. The second is the 3614 * "long radix" that tears each number into "long digits", each of which 3615 * consists of the number of digits in the corresponding element in 3616 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have 3617 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not 3618 * used. 3619 */ 3620 private static int digitsPerLong[] = {0, 0, 3621 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14, 3622 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12}; 3623 3624 private static BigInteger longRadix[] = {null, null, 3625 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL), 3626 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL), 3627 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L), 3628 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L), 3629 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L), 3630 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL), 3631 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L), 3632 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L), 3633 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L), 3634 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L), 3635 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L), 3636 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L), 3637 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL), 3638 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L), 3639 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L), 3640 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L), 3641 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L), 3642 valueOf(0x41c21cb8e1000000L)}; 3643 3644 /* 3645 * These two arrays are the integer analogue of above. 3646 */ 3647 private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11, 3648 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 3649 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5}; 3650 3651 private static int intRadix[] = {0, 0, 3652 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800, 3653 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61, 3654 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000, 3655 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d, 3656 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40, 3657 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41, 3658 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400 3659 }; 3660 3661 /** 3662 * These routines provide access to the two's complement representation 3663 * of BigIntegers. 3664 */ 3665 3666 /** 3667 * Returns the length of the two's complement representation in ints, 3668 * including space for at least one sign bit. 3669 */ 3670 private int intLength() { 3671 return (bitLength() >>> 5) + 1; 3672 } 3673 3674 /* Returns sign bit */ 3675 private int signBit() { 3676 return signum < 0 ? 1 : 0; 3677 } 3678 3679 /* Returns an int of sign bits */ 3680 private int signInt() { 3681 return signum < 0 ? -1 : 0; 3682 } 3683 3684 /** 3685 * Returns the specified int of the little-endian two's complement 3686 * representation (int 0 is the least significant). The int number can 3687 * be arbitrarily high (values are logically preceded by infinitely many 3688 * sign ints). 3689 */ 3690 private int getInt(int n) { 3691 if (n < 0) 3692 return 0; 3693 if (n >= mag.length) 3694 return signInt(); 3695 3696 int magInt = mag[mag.length-n-1]; 3697 3698 return (signum >= 0 ? magInt : 3699 (n <= firstNonzeroIntNum() ? -magInt : ~magInt)); 3700 } 3701 3702 /** 3703 * Returns the index of the int that contains the first nonzero int in the 3704 * little-endian binary representation of the magnitude (int 0 is the 3705 * least significant). If the magnitude is zero, return value is undefined. 3706 */ 3707 private int firstNonzeroIntNum() { 3708 int fn = firstNonzeroIntNum - 2; 3709 if (fn == -2) { // firstNonzeroIntNum not initialized yet 3710 fn = 0; 3711 3712 // Search for the first nonzero int 3713 int i; 3714 int mlen = mag.length; 3715 for (i = mlen - 1; i >= 0 && mag[i] == 0; i--) 3716 ; 3717 fn = mlen - i - 1; 3718 firstNonzeroIntNum = fn + 2; // offset by two to initialize 3719 } 3720 return fn; 3721 } 3722 3723 /** use serialVersionUID from JDK 1.1. for interoperability */ 3724 private static final long serialVersionUID = -8287574255936472291L; 3725 3726 /** 3727 * Serializable fields for BigInteger. 3728 * 3729 * @serialField signum int 3730 * signum of this BigInteger. 3731 * @serialField magnitude int[] 3732 * magnitude array of this BigInteger. 3733 * @serialField bitCount int 3734 * number of bits in this BigInteger 3735 * @serialField bitLength int 3736 * the number of bits in the minimal two's-complement 3737 * representation of this BigInteger 3738 * @serialField lowestSetBit int 3739 * lowest set bit in the twos complement representation 3740 */ 3741 private static final ObjectStreamField[] serialPersistentFields = { 3742 new ObjectStreamField("signum", Integer.TYPE), 3743 new ObjectStreamField("magnitude", byte[].class), 3744 new ObjectStreamField("bitCount", Integer.TYPE), 3745 new ObjectStreamField("bitLength", Integer.TYPE), 3746 new ObjectStreamField("firstNonzeroByteNum", Integer.TYPE), 3747 new ObjectStreamField("lowestSetBit", Integer.TYPE) 3748 }; 3749 3750 /** 3751 * Reconstitute the {@code BigInteger} instance from a stream (that is, 3752 * deserialize it). The magnitude is read in as an array of bytes 3753 * for historical reasons, but it is converted to an array of ints 3754 * and the byte array is discarded. 3755 * Note: 3756 * The current convention is to initialize the cache fields, bitCount, 3757 * bitLength and lowestSetBit, to 0 rather than some other marker value. 3758 * Therefore, no explicit action to set these fields needs to be taken in 3759 * readObject because those fields already have a 0 value be default since 3760 * defaultReadObject is not being used. 3761 */ 3762 private void readObject(java.io.ObjectInputStream s) 3763 throws java.io.IOException, ClassNotFoundException { 3764 /* 3765 * In order to maintain compatibility with previous serialized forms, 3766 * the magnitude of a BigInteger is serialized as an array of bytes. 3767 * The magnitude field is used as a temporary store for the byte array 3768 * that is deserialized. The cached computation fields should be 3769 * transient but are serialized for compatibility reasons. 3770 */ 3771 3772 // prepare to read the alternate persistent fields 3773 ObjectInputStream.GetField fields = s.readFields(); 3774 3775 // Read the alternate persistent fields that we care about 3776 int sign = fields.get("signum", -2); 3777 byte[] magnitude = (byte[])fields.get("magnitude", null); 3778 3779 // Validate signum 3780 if (sign < -1 || sign > 1) { 3781 String message = "BigInteger: Invalid signum value"; 3782 if (fields.defaulted("signum")) 3783 message = "BigInteger: Signum not present in stream"; 3784 throw new java.io.StreamCorruptedException(message); 3785 } 3786 if ((magnitude.length == 0) != (sign == 0)) { 3787 String message = "BigInteger: signum-magnitude mismatch"; 3788 if (fields.defaulted("magnitude")) 3789 message = "BigInteger: Magnitude not present in stream"; 3790 throw new java.io.StreamCorruptedException(message); 3791 } 3792 3793 // Commit final fields via Unsafe 3794 UnsafeHolder.putSign(this, sign); 3795 3796 // Calculate mag field from magnitude and discard magnitude 3797 UnsafeHolder.putMag(this, stripLeadingZeroBytes(magnitude)); 3798 } 3799 3800 // Support for resetting final fields while deserializing 3801 private static class UnsafeHolder { 3802 private static final sun.misc.Unsafe unsafe; 3803 private static final long signumOffset; 3804 private static final long magOffset; 3805 static { 3806 try { 3807 unsafe = sun.misc.Unsafe.getUnsafe(); 3808 signumOffset = unsafe.objectFieldOffset 3809 (BigInteger.class.getDeclaredField("signum")); 3810 magOffset = unsafe.objectFieldOffset 3811 (BigInteger.class.getDeclaredField("mag")); 3812 } catch (Exception ex) { 3813 throw new ExceptionInInitializerError(ex); 3814 } 3815 } 3816 3817 static void putSign(BigInteger bi, int sign) { 3818 unsafe.putIntVolatile(bi, signumOffset, sign); 3819 } 3820 3821 static void putMag(BigInteger bi, int[] magnitude) { 3822 unsafe.putObjectVolatile(bi, magOffset, magnitude); 3823 } 3824 } 3825 3826 /** 3827 * Save the {@code BigInteger} instance to a stream. 3828 * The magnitude of a BigInteger is serialized as a byte array for 3829 * historical reasons. 3830 * 3831 * @serialData two necessary fields are written as well as obsolete 3832 * fields for compatibility with older versions. 3833 */ 3834 private void writeObject(ObjectOutputStream s) throws IOException { 3835 // set the values of the Serializable fields 3836 ObjectOutputStream.PutField fields = s.putFields(); 3837 fields.put("signum", signum); 3838 fields.put("magnitude", magSerializedForm()); 3839 // The values written for cached fields are compatible with older 3840 // versions, but are ignored in readObject so don't otherwise matter. 3841 fields.put("bitCount", -1); 3842 fields.put("bitLength", -1); 3843 fields.put("lowestSetBit", -2); 3844 fields.put("firstNonzeroByteNum", -2); 3845 3846 // save them 3847 s.writeFields(); 3848 } 3849 3850 /** 3851 * Returns the mag array as an array of bytes. 3852 */ 3853 private byte[] magSerializedForm() { 3854 int len = mag.length; 3855 3856 int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0])); 3857 int byteLen = (bitLen + 7) >>> 3; 3858 byte[] result = new byte[byteLen]; 3859 3860 for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0; 3861 i>=0; i--) { 3862 if (bytesCopied == 4) { 3863 nextInt = mag[intIndex--]; 3864 bytesCopied = 1; 3865 } else { 3866 nextInt >>>= 8; 3867 bytesCopied++; 3868 } 3869 result[i] = (byte)nextInt; 3870 } 3871 return result; 3872 } 3873 3874 /** 3875 * Converts this {@code BigInteger} to a {@code long}, checking 3876 * for lost information. If the value of this {@code BigInteger} 3877 * is out of the range of the {@code long} type, then an 3878 * {@code ArithmeticException} is thrown. 3879 * 3880 * @return this {@code BigInteger} converted to a {@code long}. 3881 * @throws ArithmeticException if the value of {@code this} will 3882 * not exactly fit in a {@code long}. 3883 * @see BigInteger#longValue 3884 * @since 1.8 3885 */ 3886 public long longValueExact() { 3887 if (mag.length <= 2 && bitLength() <= 63) 3888 return longValue(); 3889 else 3890 throw new ArithmeticException("BigInteger out of long range"); 3891 } 3892 3893 /** 3894 * Converts this {@code BigInteger} to an {@code int}, checking 3895 * for lost information. If the value of this {@code BigInteger} 3896 * is out of the range of the {@code int} type, then an 3897 * {@code ArithmeticException} is thrown. 3898 * 3899 * @return this {@code BigInteger} converted to an {@code int}. 3900 * @throws ArithmeticException if the value of {@code this} will 3901 * not exactly fit in a {@code int}. 3902 * @see BigInteger#intValue 3903 * @since 1.8 3904 */ 3905 public int intValueExact() { 3906 if (mag.length <= 1 && bitLength() <= 31) 3907 return intValue(); 3908 else 3909 throw new ArithmeticException("BigInteger out of int range"); 3910 } 3911 3912 /** 3913 * Converts this {@code BigInteger} to a {@code short}, checking 3914 * for lost information. If the value of this {@code BigInteger} 3915 * is out of the range of the {@code short} type, then an 3916 * {@code ArithmeticException} is thrown. 3917 * 3918 * @return this {@code BigInteger} converted to a {@code short}. 3919 * @throws ArithmeticException if the value of {@code this} will 3920 * not exactly fit in a {@code short}. 3921 * @see BigInteger#shortValue 3922 * @since 1.8 3923 */ 3924 public short shortValueExact() { 3925 if (mag.length <= 1 && bitLength() <= 31) { 3926 int value = intValue(); 3927 if (value >= Short.MIN_VALUE && value <= Short.MAX_VALUE) 3928 return shortValue(); 3929 } 3930 throw new ArithmeticException("BigInteger out of short range"); 3931 } 3932 3933 /** 3934 * Converts this {@code BigInteger} to a {@code byte}, checking 3935 * for lost information. If the value of this {@code BigInteger} 3936 * is out of the range of the {@code byte} type, then an 3937 * {@code ArithmeticException} is thrown. 3938 * 3939 * @return this {@code BigInteger} converted to a {@code byte}. 3940 * @throws ArithmeticException if the value of {@code this} will 3941 * not exactly fit in a {@code byte}. 3942 * @see BigInteger#byteValue 3943 * @since 1.8 3944 */ 3945 public byte byteValueExact() { 3946 if (mag.length <= 1 && bitLength() <= 31) { 3947 int value = intValue(); 3948 if (value >= Byte.MIN_VALUE && value <= Byte.MAX_VALUE) 3949 return byteValue(); 3950 } 3951 throw new ArithmeticException("BigInteger out of byte range"); 3952 } 3953 }