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