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