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