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