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