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