rev 12826 : 8032027: Add BigInteger square root methods
Summary: Add sqrt() and sqrtAndReminder() using Newton iteration
Reviewed-by: XXX

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