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