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