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