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