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