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