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