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