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