1 /*
2 * Copyright (c) 1996, 2011, 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.util.Random;
33 import java.io.*;
34 import java.util.Arrays;
35
36 /**
37 * Immutable arbitrary-precision integers. All operations behave as if
38 * BigIntegers were represented in two's-complement notation (like Java's
39 * primitive integer types). BigInteger provides analogues to all of Java's
40 * primitive integer operators, and all relevant methods from java.lang.Math.
41 * Additionally, BigInteger provides operations for modular arithmetic, GCD
42 * calculation, primality testing, prime generation, bit manipulation,
43 * and a few other miscellaneous operations.
44 *
45 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
46 * arithmetic operators, as defined in <i>The Java Language Specification</i>.
47 * For example, division by zero throws an {@code ArithmeticException}, and
48 * division of a negative by a positive yields a negative (or zero) remainder.
49 * All of the details in the Spec concerning overflow are ignored, as
50 * BigIntegers are made as large as necessary to accommodate the results of an
51 * operation.
52 *
53 * <p>Semantics of shift operations extend those of Java's shift operators
54 * to allow for negative shift distances. A right-shift with a negative
77 * BigInteger being operated on, as they affect only a single bit, and the
78 * "infinite word size" abstraction provided by this class ensures that there
79 * are infinitely many "virtual sign bits" preceding each BigInteger.
80 *
81 * <p>For the sake of brevity and clarity, pseudo-code is used throughout the
82 * descriptions of BigInteger methods. The pseudo-code expression
83 * {@code (i + j)} is shorthand for "a BigInteger whose value is
84 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}."
85 * The pseudo-code expression {@code (i == j)} is shorthand for
86 * "{@code true} if and only if the BigInteger {@code i} represents the same
87 * value as the BigInteger {@code j}." Other pseudo-code expressions are
88 * interpreted similarly.
89 *
90 * <p>All methods and constructors in this class throw
91 * {@code NullPointerException} when passed
92 * a null object reference for any input parameter.
93 *
94 * @see BigDecimal
95 * @author Josh Bloch
96 * @author Michael McCloskey
97 * @since JDK1.1
98 */
99
100 public class BigInteger extends Number implements Comparable<BigInteger> {
101 /**
102 * The signum of this BigInteger: -1 for negative, 0 for zero, or
103 * 1 for positive. Note that the BigInteger zero <i>must</i> have
104 * a signum of 0. This is necessary to ensures that there is exactly one
105 * representation for each BigInteger value.
106 *
107 * @serial
108 */
109 final int signum;
110
111 /**
112 * The magnitude of this BigInteger, in <i>big-endian</i> order: the
113 * zeroth element of this array is the most-significant int of the
114 * magnitude. The magnitude must be "minimal" in that the most-significant
115 * int ({@code mag[0]}) must be non-zero. This is necessary to
116 * ensure that there is exactly one representation for each BigInteger
157 */
158 @Deprecated
159 private int lowestSetBit;
160
161 /**
162 * Two plus the index of the lowest-order int in the magnitude of this
163 * BigInteger that contains a nonzero int, or -2 (either value is acceptable).
164 * The least significant int has int-number 0, the next int in order of
165 * increasing significance has int-number 1, and so forth.
166 * @deprecated Deprecated since logical value is offset from stored
167 * value and correction factor is applied in accessor method.
168 */
169 @Deprecated
170 private int firstNonzeroIntNum;
171
172 /**
173 * This mask is used to obtain the value of an int as if it were unsigned.
174 */
175 final static long LONG_MASK = 0xffffffffL;
176
177 //Constructors
178
179 /**
180 * Translates a byte array containing the two's-complement binary
181 * representation of a BigInteger into a BigInteger. The input array is
182 * assumed to be in <i>big-endian</i> byte-order: the most significant
183 * byte is in the zeroth element.
184 *
185 * @param val big-endian two's-complement binary representation of
186 * BigInteger.
187 * @throws NumberFormatException {@code val} is zero bytes long.
188 */
189 public BigInteger(byte[] val) {
190 if (val.length == 0)
191 throw new NumberFormatException("Zero length BigInteger");
192
193 if (val[0] < 0) {
194 mag = makePositive(val);
195 signum = -1;
196 } else {
505 * <p>It is recommended that the {@link #probablePrime probablePrime}
506 * method be used in preference to this constructor unless there
507 * is a compelling need to specify a certainty.
508 *
509 * @param bitLength bitLength of the returned BigInteger.
510 * @param certainty a measure of the uncertainty that the caller is
511 * willing to tolerate. The probability that the new BigInteger
512 * represents a prime number will exceed
513 * (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
514 * this constructor is proportional to the value of this parameter.
515 * @param rnd source of random bits used to select candidates to be
516 * tested for primality.
517 * @throws ArithmeticException {@code bitLength < 2}.
518 * @see #bitLength()
519 */
520 public BigInteger(int bitLength, int certainty, Random rnd) {
521 BigInteger prime;
522
523 if (bitLength < 2)
524 throw new ArithmeticException("bitLength < 2");
525 // The cutoff of 95 was chosen empirically for best performance
526 prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
527 : largePrime(bitLength, certainty, rnd));
528 signum = 1;
529 mag = prime.mag;
530 }
531
532 // Minimum size in bits that the requested prime number has
533 // before we use the large prime number generating algorithms
534 private static final int SMALL_PRIME_THRESHOLD = 95;
535
536 // Certainty required to meet the spec of probablePrime
537 private static final int DEFAULT_PRIME_CERTAINTY = 100;
538
539 /**
540 * Returns a positive BigInteger that is probably prime, with the
541 * specified bitLength. The probability that a BigInteger returned
542 * by this method is composite does not exceed 2<sup>-100</sup>.
543 *
544 * @param bitLength bitLength of the returned BigInteger.
545 * @param rnd source of random bits used to select candidates to be
546 * tested for primality.
547 * @return a BigInteger of {@code bitLength} bits that is probably prime
548 * @throws ArithmeticException {@code bitLength < 2}.
549 * @see #bitLength()
550 * @since 1.4
551 */
552 public static BigInteger probablePrime(int bitLength, Random rnd) {
553 if (bitLength < 2)
554 throw new ArithmeticException("bitLength < 2");
555
556 // The cutoff of 95 was chosen empirically for best performance
557 return (bitLength < SMALL_PRIME_THRESHOLD ?
558 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
559 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
560 }
561
562 /**
563 * Find a random number of the specified bitLength that is probably prime.
564 * This method is used for smaller primes, its performance degrades on
565 * larger bitlengths.
566 *
567 * This method assumes bitLength > 1.
568 */
569 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
570 int magLen = (bitLength + 31) >>> 5;
571 int temp[] = new int[magLen];
572 int highBit = 1 << ((bitLength+31) & 0x1f); // High bit of high int
573 int highMask = (highBit << 1) - 1; // Bits to keep in high int
574
575 while(true) {
576 // Construct a candidate
969 }
970 }
971
972 /**
973 * Returns a BigInteger with the given two's complement representation.
974 * Assumes that the input array will not be modified (the returned
975 * BigInteger will reference the input array if feasible).
976 */
977 private static BigInteger valueOf(int val[]) {
978 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
979 }
980
981 // Constants
982
983 /**
984 * Initialize static constant array when class is loaded.
985 */
986 private final static int MAX_CONSTANT = 16;
987 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
988 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
989 static {
990 for (int i = 1; i <= MAX_CONSTANT; i++) {
991 int[] magnitude = new int[1];
992 magnitude[0] = i;
993 posConst[i] = new BigInteger(magnitude, 1);
994 negConst[i] = new BigInteger(magnitude, -1);
995 }
996 }
997
998 /**
999 * The BigInteger constant zero.
1000 *
1001 * @since 1.2
1002 */
1003 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1004
1005 /**
1006 * The BigInteger constant one.
1007 *
1008 * @since 1.2
1009 */
1010 public static final BigInteger ONE = valueOf(1);
1011
1012 /**
1013 * The BigInteger constant two. (Not exported.)
1014 */
1015 private static final BigInteger TWO = valueOf(2);
1016
1017 /**
1018 * The BigInteger constant ten.
1019 *
1020 * @since 1.5
1021 */
1022 public static final BigInteger TEN = valueOf(10);
1023
1024 // Arithmetic Operations
1025
1026 /**
1027 * Returns a BigInteger whose value is {@code (this + val)}.
1028 *
1029 * @param val value to be added to this BigInteger.
1030 * @return {@code this + val}
1031 */
1032 public BigInteger add(BigInteger val) {
1033 if (val.signum == 0)
1034 return this;
1035 if (signum == 0)
1036 return val;
1037 if (val.signum == signum)
1273 boolean borrow = (difference >> 32 != 0);
1274 while (bigIndex > 0 && borrow)
1275 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1276
1277 // Copy remainder of longer number
1278 while (bigIndex > 0)
1279 result[--bigIndex] = big[bigIndex];
1280
1281 return result;
1282 }
1283
1284 /**
1285 * Returns a BigInteger whose value is {@code (this * val)}.
1286 *
1287 * @param val value to be multiplied by this BigInteger.
1288 * @return {@code this * val}
1289 */
1290 public BigInteger multiply(BigInteger val) {
1291 if (val.signum == 0 || signum == 0)
1292 return ZERO;
1293 int resultSign = signum == val.signum ? 1 : -1;
1294 if (val.mag.length == 1) {
1295 return multiplyByInt(mag,val.mag[0], resultSign);
1296 }
1297 if(mag.length == 1) {
1298 return multiplyByInt(val.mag,mag[0], resultSign);
1299 }
1300 int[] result = multiplyToLen(mag, mag.length,
1301 val.mag, val.mag.length, null);
1302 result = trustedStripLeadingZeroInts(result);
1303 return new BigInteger(result, resultSign);
1304 }
1305
1306 private static BigInteger multiplyByInt(int[] x, int y, int sign) {
1307 if(Integer.bitCount(y)==1) {
1308 return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
1309 }
1310 int xlen = x.length;
1311 int[] rmag = new int[xlen + 1];
1312 long carry = 0;
1313 long yl = y & LONG_MASK;
1314 int rstart = rmag.length - 1;
1315 for (int i = xlen - 1; i >= 0; i--) {
1316 long product = (x[i] & LONG_MASK) * yl + carry;
1317 rmag[rstart--] = (int)product;
1318 carry = product >>> 32;
1319 }
1320 if (carry == 0L) {
1321 rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
1322 } else {
1323 rmag[rstart] = (int)carry;
1324 }
1385 z[k] = (int)product;
1386 carry = product >>> 32;
1387 }
1388 z[xstart] = (int)carry;
1389
1390 for (int i = xstart-1; i >= 0; i--) {
1391 carry = 0;
1392 for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
1393 long product = (y[j] & LONG_MASK) *
1394 (x[i] & LONG_MASK) +
1395 (z[k] & LONG_MASK) + carry;
1396 z[k] = (int)product;
1397 carry = product >>> 32;
1398 }
1399 z[i] = (int)carry;
1400 }
1401 return z;
1402 }
1403
1404 /**
1405 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1406 *
1407 * @return {@code this<sup>2</sup>}
1408 */
1409 private BigInteger square() {
1410 if (signum == 0)
1411 return ZERO;
1412 int[] z = squareToLen(mag, mag.length, null);
1413 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1414 }
1415
1416 /**
1417 * Squares the contents of the int array x. The result is placed into the
1418 * int array z. The contents of x are not changed.
1419 */
1420 private static final int[] squareToLen(int[] x, int len, int[] z) {
1421 /*
1422 * The algorithm used here is adapted from Colin Plumb's C library.
1423 * Technique: Consider the partial products in the multiplication
1424 * of "abcde" by itself:
1425 *
1426 * a b c d e
1427 * * a b c d e
1428 * ==================
1429 * ae be ce de ee
1430 * ad bd cd dd de
1431 * ac bc cc cd ce
1432 * ab bb bc bd be
1433 * aa ab ac ad ae
1434 *
1464 z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
1465 z[i++] = (int)(product >>> 1);
1466 lastProductLowWord = (int)product;
1467 }
1468
1469 // Add in off-diagonal sums
1470 for (int i=len, offset=1; i>0; i--, offset+=2) {
1471 int t = x[i-1];
1472 t = mulAdd(z, x, offset, i-1, t);
1473 addOne(z, offset-1, i, t);
1474 }
1475
1476 // Shift back up and set low bit
1477 primitiveLeftShift(z, zlen, 1);
1478 z[zlen-1] |= x[len-1] & 1;
1479
1480 return z;
1481 }
1482
1483 /**
1484 * Returns a BigInteger whose value is {@code (this / val)}.
1485 *
1486 * @param val value by which this BigInteger is to be divided.
1487 * @return {@code this / val}
1488 * @throws ArithmeticException if {@code val} is zero.
1489 */
1490 public BigInteger divide(BigInteger val) {
1491 MutableBigInteger q = new MutableBigInteger(),
1492 a = new MutableBigInteger(this.mag),
1493 b = new MutableBigInteger(val.mag);
1494
1495 a.divide(b, q, false);
1496 return q.toBigInteger(this.signum * val.signum);
1497 }
1498
1499 /**
1500 * Returns an array of two BigIntegers containing {@code (this / val)}
1501 * followed by {@code (this % val)}.
1502 *
1503 * @param val value by which this BigInteger is to be divided, and the
1532 b = new MutableBigInteger(val.mag);
1533
1534 return a.divide(b, q).toBigInteger(this.signum);
1535 }
1536
1537 /**
1538 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1539 * Note that {@code exponent} is an integer rather than a BigInteger.
1540 *
1541 * @param exponent exponent to which this BigInteger is to be raised.
1542 * @return <tt>this<sup>exponent</sup></tt>
1543 * @throws ArithmeticException {@code exponent} is negative. (This would
1544 * cause the operation to yield a non-integer value.)
1545 */
1546 public BigInteger pow(int exponent) {
1547 if (exponent < 0)
1548 throw new ArithmeticException("Negative exponent");
1549 if (signum==0)
1550 return (exponent==0 ? ONE : this);
1551
1552 // Perform exponentiation using repeated squaring trick
1553 int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
1554 int[] baseToPow2 = this.mag;
1555 int[] result = {1};
1556
1557 while (exponent != 0) {
1558 if ((exponent & 1)==1) {
1559 result = multiplyToLen(result, result.length,
1560 baseToPow2, baseToPow2.length, null);
1561 result = trustedStripLeadingZeroInts(result);
1562 }
1563 if ((exponent >>>= 1) != 0) {
1564 baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
1565 baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
1566 }
1567 }
1568 return new BigInteger(result, newSign);
1569 }
1570
1571 /**
1572 * Returns a BigInteger whose value is the greatest common divisor of
1573 * {@code abs(this)} and {@code abs(val)}. Returns 0 if
1574 * {@code this==0 && val==0}.
1575 *
1576 * @param val value with which the GCD is to be computed.
1577 * @return {@code GCD(abs(this), abs(val))}
1578 */
1579 public BigInteger gcd(BigInteger val) {
1580 if (val.signum == 0)
1581 return this.abs();
1582 else if (this.signum == 0)
1583 return val.abs();
1584
1585 MutableBigInteger a = new MutableBigInteger(this);
1586 MutableBigInteger b = new MutableBigInteger(val);
1587
1588 MutableBigInteger result = a.hybridGCD(b);
2100 while (--mlen >= 0) {
2101 if (--offset < 0) { // Carry out of number
2102 return 1;
2103 } else {
2104 a[offset]++;
2105 if (a[offset] != 0)
2106 return 0;
2107 }
2108 }
2109 return 1;
2110 }
2111
2112 /**
2113 * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
2114 */
2115 private BigInteger modPow2(BigInteger exponent, int p) {
2116 /*
2117 * Perform exponentiation using repeated squaring trick, chopping off
2118 * high order bits as indicated by modulus.
2119 */
2120 BigInteger result = valueOf(1);
2121 BigInteger baseToPow2 = this.mod2(p);
2122 int expOffset = 0;
2123
2124 int limit = exponent.bitLength();
2125
2126 if (this.testBit(0))
2127 limit = (p-1) < limit ? (p-1) : limit;
2128
2129 while (expOffset < limit) {
2130 if (exponent.testBit(expOffset))
2131 result = result.multiply(baseToPow2).mod2(p);
2132 expOffset++;
2133 if (expOffset < limit)
2134 baseToPow2 = baseToPow2.square().mod2(p);
2135 }
2136
2137 return result;
2138 }
2139
2140 /**
2833 tmp = q2;
2834 }
2835
2836 // Put sign (if any) and first digit group into result buffer
2837 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
2838 if (signum<0)
2839 buf.append('-');
2840 buf.append(digitGroup[numGroups-1]);
2841
2842 // Append remaining digit groups padded with leading zeros
2843 for (int i=numGroups-2; i>=0; i--) {
2844 // Prepend (any) leading zeros for this digit group
2845 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
2846 if (numLeadingZeros != 0)
2847 buf.append(zeros[numLeadingZeros]);
2848 buf.append(digitGroup[i]);
2849 }
2850 return buf.toString();
2851 }
2852
2853 /* zero[i] is a string of i consecutive zeros. */
2854 private static String zeros[] = new String[64];
2855 static {
2856 zeros[63] =
2857 "000000000000000000000000000000000000000000000000000000000000000";
2858 for (int i=0; i<63; i++)
2859 zeros[i] = zeros[63].substring(0, i);
2860 }
2861
2862 /**
2863 * Returns the decimal String representation of this BigInteger.
2864 * The digit-to-character mapping provided by
2865 * {@code Character.forDigit} is used, and a minus sign is
2866 * prepended if appropriate. (This representation is compatible
2867 * with the {@link #BigInteger(String) (String)} constructor, and
2868 * allows for String concatenation with Java's + operator.)
2869 *
2870 * @return decimal String representation of this BigInteger.
2871 * @see Character#forDigit
2872 * @see #BigInteger(java.lang.String)
|
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
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
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 {
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
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)
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 }
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 *
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
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);
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 /**
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)
|