BigInteger.java revision 1246
/*
* Portions Copyright 1996-2007 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Sun designates this
* particular file as subject to the "Classpath" exception as provided
* by Sun in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
* CA 95054 USA or visit www.sun.com if you need additional information or
* have any questions.
*/
/*
* Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
*/
/**
* Immutable arbitrary-precision integers. All operations behave as if
* BigIntegers were represented in two's-complement notation (like Java's
* primitive integer types). BigInteger provides analogues to all of Java's
* primitive integer operators, and all relevant methods from java.lang.Math.
* Additionally, BigInteger provides operations for modular arithmetic, GCD
* calculation, primality testing, prime generation, bit manipulation,
* and a few other miscellaneous operations.
*
* <p>Semantics of arithmetic operations exactly mimic those of Java's integer
* arithmetic operators, as defined in <i>The Java Language Specification</i>.
* For example, division by zero throws an {@code ArithmeticException}, and
* division of a negative by a positive yields a negative (or zero) remainder.
* All of the details in the Spec concerning overflow are ignored, as
* BigIntegers are made as large as necessary to accommodate the results of an
* operation.
*
* <p>Semantics of shift operations extend those of Java's shift operators
* to allow for negative shift distances. A right-shift with a negative
* shift distance results in a left shift, and vice-versa. The unsigned
* right shift operator ({@code >>>}) is omitted, as this operation makes
* little sense in combination with the "infinite word size" abstraction
* provided by this class.
*
* <p>Semantics of bitwise logical operations exactly mimic those of Java's
* bitwise integer operators. The binary operators ({@code and},
* {@code or}, {@code xor}) implicitly perform sign extension on the shorter
* of the two operands prior to performing the operation.
*
* <p>Comparison operations perform signed integer comparisons, analogous to
* those performed by Java's relational and equality operators.
*
* <p>Modular arithmetic operations are provided to compute residues, perform
* exponentiation, and compute multiplicative inverses. These methods always
* return a non-negative result, between {@code 0} and {@code (modulus - 1)},
* inclusive.
*
* <p>Bit operations operate on a single bit of the two's-complement
* representation of their operand. If necessary, the operand is sign-
* extended so that it contains the designated bit. None of the single-bit
* operations can produce a BigInteger with a different sign from the
* BigInteger being operated on, as they affect only a single bit, and the
* "infinite word size" abstraction provided by this class ensures that there
* are infinitely many "virtual sign bits" preceding each BigInteger.
*
* <p>For the sake of brevity and clarity, pseudo-code is used throughout the
* descriptions of BigInteger methods. The pseudo-code expression
* {@code (i + j)} is shorthand for "a BigInteger whose value is
* that of the BigInteger {@code i} plus that of the BigInteger {@code j}."
* The pseudo-code expression {@code (i == j)} is shorthand for
* "{@code true} if and only if the BigInteger {@code i} represents the same
* value as the BigInteger {@code j}." Other pseudo-code expressions are
* interpreted similarly.
*
* <p>All methods and constructors in this class throw
* {@code NullPointerException} when passed
* a null object reference for any input parameter.
*
* @see BigDecimal
* @author Josh Bloch
* @author Michael McCloskey
* @since JDK1.1
*/
/**
* The signum of this BigInteger: -1 for negative, 0 for zero, or
* 1 for positive. Note that the BigInteger zero <i>must</i> have
* a signum of 0. This is necessary to ensures that there is exactly one
* representation for each BigInteger value.
*
* @serial
*/
final int signum;
/**
* The magnitude of this BigInteger, in <i>big-endian</i> order: the
* zeroth element of this array is the most-significant int of the
* magnitude. The magnitude must be "minimal" in that the most-significant
* int ({@code mag[0]}) must be non-zero. This is necessary to
* ensure that there is exactly one representation for each BigInteger
* value. Note that this implies that the BigInteger zero has a
* zero-length mag array.
*/
final int[] mag;
// These "redundant fields" are initialized with recognizable nonsense
// values, and cached the first time they are needed (or never, if they
// aren't needed).
/**
* One plus the bitCount of this BigInteger. Zeros means unitialized.
*
* @serial
* @see #bitCount
* @deprecated Deprecated since logical value is offset from stored
* value and correction factor is applied in accessor method.
*/
private int bitCount;
/**
* One plus the bitLength of this BigInteger. Zeros means unitialized.
* (either value is acceptable).
*
* @serial
* @see #bitLength()
* @deprecated Deprecated since logical value is offset from stored
* value and correction factor is applied in accessor method.
*/
private int bitLength;
/**
* Two plus the lowest set bit of this BigInteger, as returned by
* getLowestSetBit().
*
* @serial
* @see #getLowestSetBit
* @deprecated Deprecated since logical value is offset from stored
* value and correction factor is applied in accessor method.
*/
private int lowestSetBit;
/**
* Two plus the index of the lowest-order int in the magnitude of this
* BigInteger that contains a nonzero int, or -2 (either value is acceptable).
* The least significant int has int-number 0, the next int in order of
* increasing significance has int-number 1, and so forth.
* @deprecated Deprecated since logical value is offset from stored
* value and correction factor is applied in accessor method.
*/
private int firstNonzeroIntNum;
/**
* This mask is used to obtain the value of an int as if it were unsigned.
*/
final static long LONG_MASK = 0xffffffffL;
//Constructors
/**
* Translates a byte array containing the two's-complement binary
* representation of a BigInteger into a BigInteger. The input array is
* assumed to be in <i>big-endian</i> byte-order: the most significant
* byte is in the zeroth element.
*
* @param val big-endian two's-complement binary representation of
* BigInteger.
* @throws NumberFormatException {@code val} is zero bytes long.
*/
public BigInteger(byte[] val) {
throw new NumberFormatException("Zero length BigInteger");
signum = -1;
} else {
}
}
/**
* This private constructor translates an int array containing the
* two's-complement binary representation of a BigInteger into a
* BigInteger. The input array is assumed to be in <i>big-endian</i>
* int-order: the most significant int is in the zeroth element.
*/
private BigInteger(int[] val) {
throw new NumberFormatException("Zero length BigInteger");
signum = -1;
} else {
}
}
/**
* Translates the sign-magnitude representation of a BigInteger into a
* BigInteger. The sign is represented as an integer signum value: -1 for
* negative, 0 for zero, or 1 for positive. The magnitude is a byte array
* in <i>big-endian</i> byte-order: the most significant byte is in the
* zeroth element. A zero-length magnitude array is permissible, and will
* result in a BigInteger value of 0, whether signum is -1, 0 or 1.
*
* @param signum signum of the number (-1 for negative, 0 for zero, 1
* for positive).
* @param magnitude big-endian binary representation of the magnitude of
* the number.
* @throws NumberFormatException {@code signum} is not one of the three
* legal values (-1, 0, and 1), or {@code signum} is 0 and
* {@code magnitude} contains one or more non-zero bytes.
*/
throw(new NumberFormatException("Invalid signum value"));
this.signum = 0;
} else {
if (signum == 0)
throw(new NumberFormatException("signum-magnitude mismatch"));
}
}
/**
* A constructor for internal use that translates the sign-magnitude
* representation of a BigInteger into a BigInteger. It checks the
* arguments and copies the magnitude so this constructor would be
* safe for external use.
*/
throw(new NumberFormatException("Invalid signum value"));
this.signum = 0;
} else {
if (signum == 0)
throw(new NumberFormatException("signum-magnitude mismatch"));
}
}
/**
* Translates the String representation of a BigInteger in the
* specified radix into a BigInteger. The String representation
* consists of an optional minus or plus sign followed by a
* sequence of one or more digits in the specified radix. The
* character-to-digit mapping is provided by {@code
* Character.digit}. The String may not contain any extraneous
* characters (whitespace, for example).
*
* @param val String representation of BigInteger.
* @param radix radix to be used in interpreting {@code val}.
* @throws NumberFormatException {@code val} is not a valid representation
* of a BigInteger in the specified radix, or {@code radix} is
* outside the range from {@link Character#MIN_RADIX} to
* {@link Character#MAX_RADIX}, inclusive.
* @see Character#digit
*/
throw new NumberFormatException("Radix out of range");
throw new NumberFormatException("Zero length BigInteger");
// Check for at most one leading sign
int sign = 1;
// No leading sign character or at most one leading sign character
cursor = 1;
throw new NumberFormatException("Zero length BigInteger");
}
if (index1 == 0)
sign = -1;
} else
throw new NumberFormatException("Illegal embedded sign character");
// Skip leading zeros and compute number of digits in magnitude
cursor++;
signum = 0;
return;
}
// Pre-allocate array of expected size. May be too large but can
// never be too small. Typically exact.
// Process first (potentially short) digit group
if (firstGroupLen == 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
int groupVal = 0;
if (groupVal < 0)
throw new NumberFormatException("Illegal digit");
}
// Required for cases where the array was overallocated.
}
// Constructs a new BigInteger using a char array with radix=10
BigInteger(char[] val) {
// Check for leading minus sign
int sign = 1;
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
sign = -1;
cursor = 1;
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
cursor = 1;
}
// Skip leading zeros and compute number of digits in magnitude
cursor++;
signum = 0;
return;
}
// Pre-allocate array of expected size
int numWords;
if (len < 10) {
numWords = 1;
} else {
}
// Process first (potentially short) digit group
if (firstGroupLen == 0)
// Process remaining digit groups
}
}
// Create an integer with the digits between the two indexes
// Assumes start < end. The result may be negative, but it
// is to be treated as an unsigned value.
if (result == -1)
if (nextVal == -1)
}
return result;
}
// bitsPerDigit in the given radix times 1024
// Rounded up to avoid underallocation.
1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
5253, 5295};
// Multiply x array times word y in place, and add word z
private static void destructiveMulAdd(int[] x, int y, int z) {
// Perform the multiplication word by word
long product = 0;
long carry = 0;
x[i] = (int)product;
}
// Perform the addition
x[i] = (int)sum;
}
}
/**
* Translates the decimal String representation of a BigInteger into a
* BigInteger. The String representation consists of an optional minus
* sign followed by a sequence of one or more decimal digits. The
* character-to-digit mapping is provided by {@code Character.digit}.
* The String may not contain any extraneous characters (whitespace, for
* example).
*
* @param val decimal String representation of BigInteger.
* @throws NumberFormatException {@code val} is not a valid representation
* of a BigInteger.
* @see Character#digit
*/
this(val, 10);
}
/**
* Constructs a randomly generated BigInteger, uniformly distributed over
* the range {@code 0} to (2<sup>{@code numBits}</sup> - 1), inclusive.
* The uniformity of the distribution assumes that a fair source of random
* bits is provided in {@code rnd}. Note that this constructor always
* constructs a non-negative BigInteger.
*
* @param numBits maximum bitLength of the new BigInteger.
* @param rnd source of randomness to be used in computing the new
* BigInteger.
* @throws IllegalArgumentException {@code numBits} is negative.
* @see #bitLength()
*/
}
if (numBits < 0)
throw new IllegalArgumentException("numBits must be non-negative");
byte[] randomBits = new byte[numBytes];
// Generate random bytes and mask out any excess bits
if (numBytes > 0) {
}
return randomBits;
}
/**
* Constructs a randomly generated positive BigInteger that is probably
* prime, with the specified bitLength.
*
* <p>It is recommended that the {@link #probablePrime probablePrime}
* method be used in preference to this constructor unless there
* is a compelling need to specify a certainty.
*
* @param bitLength bitLength of the returned BigInteger.
* @param certainty a measure of the uncertainty that the caller is
* willing to tolerate. The probability that the new BigInteger
* represents a prime number will exceed
* (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
* this constructor is proportional to the value of this parameter.
* @param rnd source of random bits used to select candidates to be
* tested for primality.
* @throws ArithmeticException {@code bitLength < 2}.
* @see #bitLength()
*/
if (bitLength < 2)
throw new ArithmeticException("bitLength < 2");
// The cutoff of 95 was chosen empirically for best performance
signum = 1;
}
// Minimum size in bits that the requested prime number has
// before we use the large prime number generating algorithms
private static final int SMALL_PRIME_THRESHOLD = 95;
// Certainty required to meet the spec of probablePrime
private static final int DEFAULT_PRIME_CERTAINTY = 100;
/**
* Returns a positive BigInteger that is probably prime, with the
* specified bitLength. The probability that a BigInteger returned
* by this method is composite does not exceed 2<sup>-100</sup>.
*
* @param bitLength bitLength of the returned BigInteger.
* @param rnd source of random bits used to select candidates to be
* tested for primality.
* @return a BigInteger of {@code bitLength} bits that is probably prime
* @throws ArithmeticException {@code bitLength < 2}.
* @see #bitLength()
* @since 1.4
*/
if (bitLength < 2)
throw new ArithmeticException("bitLength < 2");
// The cutoff of 95 was chosen empirically for best performance
return (bitLength < SMALL_PRIME_THRESHOLD ?
}
/**
* Find a random number of the specified bitLength that is probably prime.
* This method is used for smaller primes, its performance degrades on
* larger bitlengths.
*
* This method assumes bitLength > 1.
*/
while(true) {
// Construct a candidate
for (int i=0; i<magLen; i++)
if (bitLength > 2)
// Do cheap "pre-test" if applicable
if (bitLength > 6) {
if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) ||
(r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
(r%29==0) || (r%31==0) || (r%37==0) || (r%41==0))
continue; // Candidate is composite; try another
}
// All candidates of bitLength 2 and 3 are prime by this point
if (bitLength < 4)
return p;
// Do expensive test if we survive pre-test (or it's inapplicable)
return p;
}
}
private static final BigInteger SMALL_PRIME_PRODUCT
/**
* Find a random number of the specified bitLength that is probably prime.
* This method is more appropriate for larger bitlengths since it uses
* a sieve to eliminate most composites before using a more expensive
* test.
*/
BigInteger p;
// Use a sieve length likely to contain the next prime number
}
return candidate;
}
/**
* Returns the first integer greater than this {@code BigInteger} that
* is probably prime. The probability that the number returned by this
* method is composite does not exceed 2<sup>-100</sup>. This method will
* never skip over a prime when searching: if it returns {@code p}, there
* is no prime {@code q} such that {@code this < q < p}.
*
* @return the first integer greater than this {@code BigInteger} that
* is probably prime.
* @throws ArithmeticException {@code this < 0}.
* @since 1.5
*/
public BigInteger nextProbablePrime() {
if (this.signum < 0)
throw new ArithmeticException("start < 0: " + this);
// Handle trivial cases
return TWO;
// Fastpath for small numbers
// Ensure an odd number
while(true) {
// Do cheap "pre-test" if applicable
if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) ||
(r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
(r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
continue; // Candidate is composite; try another
}
}
// All candidates of bitLength 2 and 3 are prime by this point
return result;
// The expensive test
return result;
}
}
// Start at previous even number
// Looking for the next large prime
while(true) {
return candidate;
}
}
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*
* This method assumes bitLength > 2.
*
* @param certainty a measure of the uncertainty that the caller is
* willing to tolerate: if the call returns {@code true}
* the probability that this BigInteger is prime exceeds
* {@code (1 - 1/2<sup>certainty</sup>)}. The execution time of
* this method is proportional to the value of this parameter.
* @return {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*/
int rounds = 0;
// The relationship between the certainty and the number of rounds
// we perform is given in the draft standard ANSI X9.80, "PRIME
// NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
int sizeInBits = this.bitLength();
if (sizeInBits < 100) {
rounds = 50;
}
if (sizeInBits < 256) {
rounds = 27;
} else if (sizeInBits < 512) {
rounds = 15;
} else if (sizeInBits < 768) {
rounds = 8;
} else if (sizeInBits < 1024) {
rounds = 4;
} else {
rounds = 2;
}
}
/**
* Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
*
* The following assumptions are made:
* This BigInteger is a positive, odd number.
*/
private boolean passesLucasLehmer() {
// Step 1
int d = 5;
while (jacobiSymbol(d, this) != -1) {
// 5, -7, 9, -11, ...
}
// Step 2
// Step 3
}
/**
* Computes Jacobi(p,n).
* Assumes n positive, odd, n>=3.
*/
private static int jacobiSymbol(int p, BigInteger n) {
if (p == 0)
return 0;
// Algorithm and comments adapted from Colin Plumb's C library.
int j = 1;
// Make p positive
if (p < 0) {
p = -p;
int n8 = u & 7;
j = -j; // 3 (011) or 7 (111) mod 8
}
// Get rid of factors of 2 in p
while ((p & 3) == 0)
p >>= 2;
if ((p & 1) == 0) {
p >>= 1;
if (((u ^ (u>>1)) & 2) != 0)
j = -j; // 3 (011) or 5 (101) mod 8
}
if (p == 1)
return j;
// Then, apply quadratic reciprocity
if ((p & u & 2) != 0) // p = u = 3 (mod 4)?
j = -j;
// And reduce u mod p
// Now compute Jacobi(u,p), u < p
while (u != 0) {
while ((u & 3) == 0)
u >>= 2;
if ((u & 1) == 0) {
u >>= 1;
if (((p ^ (p>>1)) & 2) != 0)
j = -j; // 3 (011) or 5 (101) mod 8
}
if (u == 1)
return j;
// Now both u and p are odd, so use quadratic reciprocity
assert (u < p);
int t = u; u = p; p = t;
if ((u & p & 2) != 0) // u = p = 3 (mod 4)?
j = -j;
// Now u >= p, so it can be reduced
u %= p;
}
return 0;
}
if (k.testBit(i)) {
}
}
return u;
}
private static volatile Random staticRandom;
private static Random getSecureRandom() {
if (staticRandom == null) {
}
return staticRandom;
}
/**
* Returns true iff this BigInteger passes the specified number of
* Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
* 186-2).
*
* The following assumptions are made:
* This BigInteger is a positive, odd number greater than 2.
* iterations<=50.
*/
// Find a and m such that m is odd and this == 1 + 2**a * m
BigInteger m = thisMinusOne;
int a = m.getLowestSetBit();
m = m.shiftRight(a);
// Do the tests
rnd = getSecureRandom();
}
for (int i=0; i<iterations; i++) {
// Generate a uniform random on (1, this)
BigInteger b;
do {
int j = 0;
BigInteger z = b.modPow(m, this);
return false;
}
}
return true;
}
/**
* This internal constructor differs from its public cousin
* with the arguments reversed in two ways: it assumes that its
* arguments are correct, and it doesn't copy the magnitude array.
*/
}
/**
* This private constructor is for internal use and assumes that its
* arguments are correct.
*/
}
//Static Factory Methods
/**
* Returns a BigInteger whose value is equal to that of the
* specified {@code long}. This "static factory method" is
* provided in preference to a ({@code long}) constructor
* because it allows for reuse of frequently used BigIntegers.
*
* @param val value of the BigInteger to return.
* @return a BigInteger with the specified value.
*/
// If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
if (val == 0)
return ZERO;
return new BigInteger(val);
}
/**
* Constructs a BigInteger with the specified value, which may not be zero.
*/
private BigInteger(long val) {
if (val < 0) {
signum = -1;
} else {
signum = 1;
}
if (highWord==0) {
mag = new int[1];
} else {
mag = new int[2];
}
}
/**
* Returns a BigInteger with the given two's complement representation.
* Assumes that the input array will not be modified (the returned
* BigInteger will reference the input array if feasible).
*/
}
// Constants
/**
* Initialize static constant array when class is loaded.
*/
private final static int MAX_CONSTANT = 16;
static {
for (int i = 1; i <= MAX_CONSTANT; i++) {
int[] magnitude = new int[1];
magnitude[0] = i;
}
}
/**
* The BigInteger constant zero.
*
* @since 1.2
*/
/**
* The BigInteger constant one.
*
* @since 1.2
*/
/**
* The BigInteger constant two. (Not exported.)
*/
/**
* The BigInteger constant ten.
*
* @since 1.5
*/
// Arithmetic Operations
/**
* Returns a BigInteger whose value is {@code (this + val)}.
*
* @param val value to be added to this BigInteger.
* @return {@code this + val}
*/
return this;
if (signum == 0)
return val;
if (cmp == 0)
return ZERO;
}
/**
* Adds the contents of the int arrays x and y. This method allocates
* a new int array to hold the answer and returns a reference to that
* array.
*/
private static int[] add(int[] x, int[] y) {
// If x is shorter, swap the two arrays
int[] tmp = x;
x = y;
y = tmp;
}
long sum = 0;
// Add common parts of both numbers
while(yIndex > 0) {
}
// Copy remainder of longer number while carry propagation is required
// Copy remainder of longer number
while (xIndex > 0)
// Grow result if necessary
if (carry) {
return bigger;
}
return result;
}
/**
* Returns a BigInteger whose value is {@code (this - val)}.
*
* @param val value to be subtracted from this BigInteger.
* @return {@code this - val}
*/
return this;
if (signum == 0)
if (cmp == 0)
return ZERO;
}
/**
* Subtracts the contents of the second int arrays (little) from the
* first (big). The first int array (big) must represent a larger number
* than the second. This method allocates the space necessary to hold the
* answer.
*/
long difference = 0;
// Subtract common parts of both numbers
while(littleIndex > 0) {
(difference >> 32);
}
// Subtract remainder of longer number while borrow propagates
// Copy remainder of longer number
while (bigIndex > 0)
return result;
}
/**
* Returns a BigInteger whose value is {@code (this * val)}.
*
* @param val value to be multiplied by this BigInteger.
* @return {@code this * val}
*/
return ZERO;
}
/**
* Package private methods used by BigDecimal code to multiply a BigInteger
* with a long. Assumes v is not equal to INFLATED.
*/
BigInteger multiply(long v) {
return ZERO;
if (v == BigDecimal.INFLATED)
if (v < 0)
v = -v;
long carry = 0;
}
if (dh != 0L) {
carry = 0;
}
}
if (carry == 0L)
}
/**
* Multiplies int arrays x and y to the specified lengths and places
* the result into z. There will be no leading zeros in the resultant array.
*/
long carry = 0;
z[k] = (int)product;
}
carry = 0;
(x[i] & LONG_MASK) +
z[k] = (int)product;
}
z[i] = (int)carry;
}
return z;
}
/**
* Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
*
* @return {@code this<sup>2</sup>}
*/
private BigInteger square() {
if (signum == 0)
return ZERO;
}
/**
* Squares the contents of the int array x. The result is placed into the
* int array z. The contents of x are not changed.
*/
private static final int[] squareToLen(int[] x, int len, int[] z) {
/*
* The algorithm used here is adapted from Colin Plumb's C library.
* Technique: Consider the partial products in the multiplication
* of "abcde" by itself:
*
* a b c d e
* * a b c d e
* ==================
* ae be ce de ee
* ad bd cd dd de
* ac bc cc cd ce
* ab bb bc bd be
* aa ab ac ad ae
*
* Note that everything above the main diagonal:
* ae be ce de = (abcd) * e
* ad bd cd = (abc) * d
* ac bc = (ab) * c
* ab = (a) * b
*
* is a copy of everything below the main diagonal:
* de
* cd ce
* bc bd be
* ab ac ad ae
*
* Thus, the sum is 2 * (off the diagonal) + diagonal.
*
* This is accumulated beginning with the diagonal (which
* consist of the squares of the digits of the input), which is then
* divided by two, the off-diagonal added, and multiplied by two
* again. The low bit is simply a copy of the low bit of the
* input, so it doesn't need special care.
*/
z = new int[zlen];
// Store the squares, right shifted one bit (i.e., divided by 2)
int lastProductLowWord = 0;
z[i++] = (int)(product >>> 1);
lastProductLowWord = (int)product;
}
// Add in off-diagonal sums
int t = x[i-1];
}
// Shift back up and set low bit
return z;
}
/**
* Returns a BigInteger whose value is {@code (this / val)}.
*
* @param val value by which this BigInteger is to be divided.
* @return {@code this / val}
* @throws ArithmeticException {@code val==0}
*/
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
a.divide(b, q);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
* followed by {@code (this % val)}.
*
* @param val value by which this BigInteger is to be divided, and the
* remainder computed.
* @return an array of two BigIntegers: the quotient {@code (this / val)}
* is the initial element, and the remainder {@code (this % val)}
* is the final element.
* @throws ArithmeticException {@code val==0}
*/
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
MutableBigInteger r = a.divide(b, q);
return result;
}
/**
* Returns a BigInteger whose value is {@code (this % val)}.
*
* @param val value by which this BigInteger is to be divided, and the
* remainder computed.
* @return {@code this % val}
* @throws ArithmeticException {@code val==0}
*/
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
}
/**
* Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
* Note that {@code exponent} is an integer rather than a BigInteger.
*
* @param exponent exponent to which this BigInteger is to be raised.
* @return <tt>this<sup>exponent</sup></tt>
* @throws ArithmeticException {@code exponent} is negative. (This would
* cause the operation to yield a non-integer value.)
*/
if (exponent < 0)
throw new ArithmeticException("Negative exponent");
if (signum==0)
// Perform exponentiation using repeated squaring trick
int[] baseToPow2 = this.mag;
int[] result = {1};
while (exponent != 0) {
}
}
}
}
/**
* Returns a BigInteger whose value is the greatest common divisor of
* {@code abs(this)} and {@code abs(val)}. Returns 0 if
* {@code this==0 && val==0}.
*
* @param val value with which the GCD is to be computed.
* @return {@code GCD(abs(this), abs(val))}
*/
return this.abs();
else if (this.signum == 0)
MutableBigInteger a = new MutableBigInteger(this);
}
/**
* Package private method to return bit length for an integer.
*/
static int bitLengthForInt(int n) {
}
/**
* Left shift int array a up to len by n bits. Returns the array that
* results from the shift since space may have to be reallocated.
*/
int nInts = n >>> 5;
int nBits = n&0x1F;
// If shift can be done without recopy, do so
if (n <= (32-bitsInHighWord)) {
return a;
} else { // Array must be resized
for (int i=0; i<len; i++)
result[i] = a[i];
return result;
} else {
for (int i=0; i<len; i++)
result[i] = a[i];
return result;
}
}
}
// shifts a up to len right n bits assumes no leading zeros, 0<n<32
static void primitiveRightShift(int[] a, int len, int n) {
int n2 = 32 - n;
int b = c;
c = a[i-1];
a[i] = (c << n2) | (b >>> n);
}
a[0] >>>= n;
}
// shifts a up to len left n bits assumes no leading zeros, 0<=n<32
static void primitiveLeftShift(int[] a, int len, int n) {
return;
int n2 = 32 - n;
int b = c;
c = a[i+1];
a[i] = (b << n) | (c >>> n2);
}
a[len-1] <<= n;
}
/**
* Calculate bitlength of contents of the first len elements an int array,
* assuming there are no leading zero ints.
*/
if (len == 0)
return 0;
}
/**
* Returns a BigInteger whose value is the absolute value of this
* BigInteger.
*
* @return {@code abs(this)}
*/
public BigInteger abs() {
}
/**
* Returns a BigInteger whose value is {@code (-this)}.
*
* @return {@code -this}
*/
public BigInteger negate() {
}
/**
* Returns the signum function of this BigInteger.
*
* @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
* positive.
*/
public int signum() {
return this.signum;
}
// Modular Arithmetic Operations
/**
* Returns a BigInteger whose value is {@code (this mod m}). This method
* differs from {@code remainder} in that it always returns a
* <i>non-negative</i> BigInteger.
*
* @param m the modulus.
* @return {@code this mod m}
* @throws ArithmeticException {@code m <= 0}
* @see #remainder
*/
if (m.signum <= 0)
throw new ArithmeticException("BigInteger: modulus not positive");
}
/**
* Returns a BigInteger whose value is
* <tt>(this<sup>exponent</sup> mod m)</tt>. (Unlike {@code pow}, this
* method permits negative exponents.)
*
* @param exponent the exponent.
* @param m the modulus.
* @return <tt>this<sup>exponent</sup> mod m</tt>
* @throws ArithmeticException {@code m <= 0}
* @see #modInverse
*/
if (m.signum <= 0)
throw new ArithmeticException("BigInteger: modulus not positive");
// Trivial cases
return ZERO;
boolean invertResult;
? this.mod(m) : this);
} else {
/*
* Even modulus. Tear it into an "odd part" (m1) and power of two
* (m2), exponentiate mod m1, manually exponentiate mod m2, and
* use Chinese Remainder Theorem to combine results.
*/
// Tear m apart into odd part (m1) and power of 2 (m2)
int p = m.getLowestSetBit(); // Max pow of 2 that divides m
// Calculate new base from m1
// Caculate (base ** exponent) mod m1.
// Calculate (this ** exponent) mod m2
// Combine results using Chinese Remainder Theorem
}
}
/**
* Returns a BigInteger whose value is x to the power of y mod z.
* Assumes: z is odd && x < z.
*/
/*
* The algorithm is adapted from Colin Plumb's C library.
*
* The window algorithm:
* The idea is to keep a running product of b1 = n^(high-order bits of exp)
* and then keep appending exponent bits to it. The following patterns
* apply to a 3-bit window (k = 3):
* To append 0: square
* To append 1: square, multiply by n^1
* To append 10: square, multiply by n^1, square
* To append 11: square, square, multiply by n^3
* To append 100: square, multiply by n^1, square, square
* To append 101: square, square, square, multiply by n^5
* To append 110: square, square, multiply by n^3, square
* To append 111: square, square, square, multiply by n^7
*
* Since each pattern involves only one multiply, the longer the pattern
* the better, except that a 0 (no multiplies) can be appended directly.
* We precompute a table of odd powers of n, up to 2^k, and can then
* multiply k bits of exponent at a time. Actually, assuming random
* exponents, there is on average one zero bit between needs to
* multiply (1/2 of the time there's none, 1/4 of the time there's 1,
* 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
* you have to do one multiply per k+1 bits of exponent.
*
* The loop walks down the exponent, squaring the result buffer as
* it goes. There is a wbits+1 bit lookahead buffer, buf, that is
* filled with the upcoming exponent bits. (What is read after the
* end of the exponent is unimportant, but it is filled with zero here.)
* When the most-significant bit of this buffer becomes set, i.e.
* (buf & tblmask) != 0, we have to decide what pattern to multiply
* by, and when to do it. We decide, remember to do it in future
* after a suitable number of squarings have passed (e.g. a pattern
* of "100" in the buffer requires that we multiply by n^1 immediately;
* a pattern of "110" calls for multiplying by n^3 after one more
* squaring), clear the buffer, and continue.
*
* When we start, there is one more optimization: the result buffer
* is implcitly one, so squaring it or multiplying by it can be
* optimized away. Further, if we start with a pattern like "100"
* in the lookahead window, rather than placing n into the buffer
* and then starting to square it, we have already computed n^2
* to compute the odd-powers table, so we can place that into
* the buffer and save a squaring.
*
* This means that if you have a k-bit window, to compute n^z,
* where z is the high k bits of the exponent, 1/2 of the time
* it requires no squarings. 1/4 of the time, it requires 1
* squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
* And the remaining 1/2^(k-1) of the time, the top k bits are a
* 1 followed by k-1 0 bits, so it again only requires k-2
* squarings, not k-1. The average of these is 1. Add that
* to the one squaring we have to do to compute the table,
* and you'll see that a k-bit window saves k-2 squarings
* as well as reducing the multiplies. (It actually doesn't
* hurt in the case k = 1, either.)
*/
// Special case for exponent of one
return this;
// Special case for base of zero
if (signum==0)
return ZERO;
// Select an appropriate window size
int wbits = 0;
// if exponent is 65537 (0x10001), use minimum window size
wbits++;
}
}
// Calculate appropriate table size
// Allocate table for precomputed odd powers of base in Montgomery form
for (int i=0; i<tblmask; i++)
// Compute the modular inverse
// Convert base to Montgomery form
MutableBigInteger q = new MutableBigInteger(),
a2 = new MutableBigInteger(a),
// Pad table[0] with leading zeros so its length is at least modLen
}
// Set b to the square of the base
// Set t to high half of b
int[] t = new int[modLen];
for(int i=0; i<modLen; i++)
t[i] = b[i];
// Fill in the table with odd powers of the base
for (int i=1; i<tblmask; i++) {
}
// Pre load the window that slides over the exponent
int buf = 0;
int eIndex = 0;
for (int i = 0; i <= wbits; i++) {
bitpos >>>= 1;
if (bitpos == 0) {
eIndex++;
elen--;
}
}
// The first iteration, which is hoisted out of the main loop
ebits--;
boolean isone = true;
buf >>>= 1;
multpos++;
}
buf = 0;
isone = false;
// The main loop
while(true) {
ebits--;
// Advance the window
buf <<= 1;
if (elen != 0) {
bitpos >>>= 1;
if (bitpos == 0) {
eIndex++;
elen--;
}
}
// Examine the window for pending multiplies
buf >>>= 1;
multpos++;
}
buf = 0;
}
// Perform multiply
if (isone) {
isone = false;
} else {
t = b;
t = a; a = b; b = t;
}
}
// Check if done
if (ebits == 0)
break;
// Square the input
if (!isone) {
t = b;
a = squareToLen(t, modLen, a);
t = a; a = b; b = t;
}
}
// Convert result out of Montgomery form and return
for(int i=0; i<modLen; i++)
for(int i=0; i<modLen; i++)
t2[i] = b[i];
}
/**
* Montgomery reduce n, modulo mod. This reduces modulo mod and divides
* by 2^(32*mlen). Adapted from Colin Plumb's C library.
*/
int c=0;
int offset=0;
do {
offset++;
} while(--len > 0);
while(c>0)
return n;
}
/*
* Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
* equal to, or greater than arg2 up to length len.
*/
for (int i=0; i<len; i++) {
return -1;
return 1;
}
return 0;
}
/**
* Subtracts two numbers of same length, returning borrow.
*/
long sum = 0;
while(--len >= 0) {
}
return (int)(sum >> 32);
}
/**
* Multiply an array by one word k and add to result, return the carry
*/
long carry = 0;
}
return (int)carry;
}
/**
* Add one word to the number a mlen words into a. Return the resulting
* carry.
*/
a[offset] = (int)t;
if ((t >>> 32) == 0)
return 0;
while (--mlen >= 0) {
return 1;
} else {
a[offset]++;
if (a[offset] != 0)
return 0;
}
}
return 1;
}
/**
* Returns a BigInteger whose value is (this ** exponent) mod (2**p)
*/
/*
* Perform exponentiation using repeated squaring trick, chopping off
* high order bits as indicated by modulus.
*/
int expOffset = 0;
if (this.testBit(0))
expOffset++;
}
return result;
}
/**
* Returns a BigInteger whose value is this mod(2**p).
* Assumes that this {@code BigInteger >= 0} and {@code p > 0}.
*/
private BigInteger mod2(int p) {
if (bitLength() <= p)
return this;
// Copy remaining ints of mag
for (int i=0; i<numInts; i++)
// Mask out any excess bits
}
/**
* Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
*
* @param m the modulus.
* @return {@code this}<sup>-1</sup> {@code mod m}.
* @throws ArithmeticException {@code m <= 0}, or this BigInteger
* has no multiplicative inverse mod m (that is, this BigInteger
* is not <i>relatively prime</i> to m).
*/
if (m.signum != 1)
throw new ArithmeticException("BigInteger: modulus not positive");
return ZERO;
// Calculate (this mod m)
BigInteger modVal = this;
return ONE;
MutableBigInteger b = new MutableBigInteger(m);
}
// Shift Operations
/**
* Returns a BigInteger whose value is {@code (this << n)}.
* The shift distance, {@code n}, may be negative, in which case
* this method performs a right shift.
* (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
*
* @param n shift distance, in bits.
* @return {@code this << n}
* @see #shiftRight
*/
public BigInteger shiftLeft(int n) {
if (signum == 0)
return ZERO;
if (n==0)
return this;
if (n<0)
return shiftRight(-n);
int nInts = n >>> 5;
int nBits = n & 0x1f;
if (nBits == 0) {
for (int i=0; i<magLen; i++)
} else {
int i = 0;
if (highBits != 0) {
} else {
}
int j=0;
while (j < magLen-1)
}
}
/**
* Returns a BigInteger whose value is {@code (this >> n)}. Sign
* extension is performed. The shift distance, {@code n}, may be
* negative, in which case this method performs a left shift.
* (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.)
*
* @param n shift distance, in bits.
* @return {@code this >> n}
* @see #shiftLeft
*/
public BigInteger shiftRight(int n) {
if (n==0)
return this;
if (n<0)
return shiftLeft(-n);
int nInts = n >>> 5;
int nBits = n & 0x1f;
// Special case: entire contents shifted off the end
if (nBits == 0) {
for (int i=0; i<newMagLen; i++)
} else {
int i = 0;
if (highBits != 0) {
} else {
}
int j=0;
}
if (signum < 0) {
// Find out whether any one-bits were shifted off the end.
boolean onesLost = false;
if (onesLost)
}
}
int[] javaIncrement(int[] val) {
int lastSum = 0;
if (lastSum == 0) {
}
return val;
}
// Bitwise Operations
/**
* Returns a BigInteger whose value is {@code (this & val)}. (This
* method returns a negative BigInteger if and only if this and val are
* both negative.)
*
* @param val value to be AND'ed with this BigInteger.
* @return {@code this & val}
*/
}
/**
* Returns a BigInteger whose value is {@code (this | val)}. (This method
* returns a negative BigInteger if and only if either this or val is
* negative.)
*
* @param val value to be OR'ed with this BigInteger.
* @return {@code this | val}
*/
}
/**
* Returns a BigInteger whose value is {@code (this ^ val)}. (This method
* returns a negative BigInteger if and only if exactly one of this and
* val are negative.)
*
* @param val value to be XOR'ed with this BigInteger.
* @return {@code this ^ val}
*/
}
/**
* Returns a BigInteger whose value is {@code (~this)}. (This method
* returns a negative value if and only if this BigInteger is
* non-negative.)
*
* @return {@code ~this}
*/
public BigInteger not() {
}
/**
* Returns a BigInteger whose value is {@code (this & ~val)}. This
* method, which is equivalent to {@code and(val.not())}, is provided as
* a convenience for masking operations. (This method returns a negative
* BigInteger if and only if {@code this} is negative and {@code val} is
* positive.)
*
* @param val value to be complemented and AND'ed with this BigInteger.
* @return {@code this & ~val}
*/
}
// Single Bit Operations
/**
* Returns {@code true} if and only if the designated bit is set.
* (Computes {@code ((this & (1<<n)) != 0)}.)
*
* @param n index of bit to test.
* @return {@code true} if and only if the designated bit is set.
* @throws ArithmeticException {@code n} is negative.
*/
public boolean testBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
}
/**
* Returns a BigInteger whose value is equivalent to this BigInteger
* with the designated bit set. (Computes {@code (this | (1<<n))}.)
*
* @param n index of bit to set.
* @return {@code this | (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger setBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
}
/**
* Returns a BigInteger whose value is equivalent to this BigInteger
* with the designated bit cleared.
* (Computes {@code (this & ~(1<<n))}.)
*
* @param n index of bit to clear.
* @return {@code this & ~(1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger clearBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
}
/**
* Returns a BigInteger whose value is equivalent to this BigInteger
* with the designated bit flipped.
* (Computes {@code (this ^ (1<<n))}.)
*
* @param n index of bit to flip.
* @return {@code this ^ (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger flipBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
}
/**
* Returns the index of the rightmost (lowest-order) one bit in this
* BigInteger (the number of zero bits to the right of the rightmost
* one bit). Returns -1 if this BigInteger contains no one bits.
* (Computes {@code (this==0? -1 : log2(this & -this))}.)
*
* @return index of the rightmost one bit in this BigInteger.
*/
public int getLowestSetBit() {
lsb = 0;
if (signum == 0) {
lsb -= 1;
} else {
// Search for lowest order nonzero int
int i,b;
;
}
}
return lsb;
}
// Miscellaneous Bit Operations
/**
* Returns the number of bits in the minimal two's-complement
* representation of this BigInteger, <i>excluding</i> a sign bit.
* For positive BigIntegers, this is equivalent to the number of bits in
* the ordinary binary representation. (Computes
* {@code (ceil(log2(this < 0 ? -this : this+1)))}.)
*
* @return number of bits in the minimal two's-complement
* representation of this BigInteger, <i>excluding</i> a sign bit.
*/
public int bitLength() {
if (n == -1) { // bitLength not initialized yet
int[] m = mag;
if (len == 0) {
n = 0; // offset by one to initialize
} else {
// Calculate the bit length of the magnitude
if (signum < 0) {
// Check if magnitude is a power of two
} else {
n = magBitLength;
}
}
bitLength = n + 1;
}
return n;
}
/**
* Returns the number of bits in the two's complement representation
* of this BigInteger that differ from its sign bit. This method is
* useful when implementing bit-vector style sets atop BigIntegers.
*
* @return number of bits in the two's complement representation
* of this BigInteger that differ from its sign bit.
*/
public int bitCount() {
// Count the bits in the magnitude
if (signum < 0) {
// Count the trailing zeros in the magnitude
int magTrailingZeroCount = 0, j;
magTrailingZeroCount += 32;
}
}
return bc;
}
// Primality Testing
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite. If
* {@code certainty} is {@code <= 0}, {@code true} is
* returned.
*
* @param certainty a measure of the uncertainty that the caller is
* willing to tolerate: if the call returns {@code true}
* the probability that this BigInteger is prime exceeds
* (1 - 1/2<sup>{@code certainty}</sup>). The execution time of
* this method is proportional to the value of this parameter.
* @return {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite.
*/
public boolean isProbablePrime(int certainty) {
if (certainty <= 0)
return true;
BigInteger w = this.abs();
return true;
return false;
}
// Comparison Operations
/**
* Compares this BigInteger with the specified BigInteger. This
* method is provided in preference to individual methods for each
* of the six boolean comparison operators ({@literal <}, ==,
* {@literal >}, {@literal >=}, !=, {@literal <=}). The suggested
* idiom for performing these comparisons is: {@code
* (x.compareTo(y)} <<i>op</i>> {@code 0)}, where
* <<i>op</i>> is one of the six comparison operators.
*
* @param val BigInteger to which this BigInteger is to be compared.
* @return -1, 0 or 1 as this BigInteger is numerically less than, equal
* to, or greater than {@code val}.
*/
switch (signum) {
case 1:
return compareMagnitude(val);
case -1:
return val.compareMagnitude(this);
default:
return 0;
}
}
}
/**
* Compares the magnitude array of this BigInteger with the specified
* BigInteger's. This is the version of compareTo ignoring sign.
*
* @param val BigInteger whose magnitude array to be compared.
* @return -1, 0 or 1 as this magnitude array is less than, equal to or
* greater than the magnitude aray for the specified BigInteger's.
*/
return -1;
return 1;
for (int i = 0; i < len1; i++) {
int a = m1[i];
int b = m2[i];
if (a != b)
}
return 0;
}
/**
* Compares this BigInteger with the specified Object for equality.
*
* @param x Object to which this BigInteger is to be compared.
* @return {@code true} if and only if the specified Object is a
* BigInteger whose value is numerically equal to this BigInteger.
*/
// This test is just an optimization, which may or may not help
if (x == this)
return true;
if (!(x instanceof BigInteger))
return false;
return false;
int[] m = mag;
return false;
for (int i = 0; i < len; i++)
if (xm[i] != m[i])
return false;
return true;
}
/**
* Returns the minimum of this BigInteger and {@code val}.
*
* @param val value with which the minimum is to be computed.
* @return the BigInteger whose value is the lesser of this BigInteger and
* {@code val}. If they are equal, either may be returned.
*/
}
/**
* Returns the maximum of this BigInteger and {@code val}.
*
* @param val value with which the maximum is to be computed.
* @return the BigInteger whose value is the greater of this and
* {@code val}. If they are equal, either may be returned.
*/
}
// Hash Function
/**
* Returns the hash code for this BigInteger.
*
* @return hash code for this BigInteger.
*/
public int hashCode() {
int hashCode = 0;
}
/**
* Returns the String representation of this BigInteger in the
* given radix. If the radix is outside the range from {@link
* Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
* it will default to 10 (as is the case for
* {@code Integer.toString}). The digit-to-character mapping
* provided by {@code Character.forDigit} is used, and a minus
* sign is prepended if appropriate. (This representation is
* compatible with the {@link #BigInteger(String, int) (String,
* int)} constructor.)
*
* @param radix radix of the String representation.
* @return String representation of this BigInteger in the given radix.
* @see Integer#toString
* @see Character#forDigit
* @see #BigInteger(java.lang.String, int)
*/
if (signum == 0)
return "0";
radix = 10;
// Compute upper bound on number of digit groups and allocate space
// Translate number to string, a digit group at a time
int numGroups = 0;
MutableBigInteger q = new MutableBigInteger(),
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
}
// Put sign (if any) and first digit group into result buffer
if (signum<0)
// Append remaining digit groups padded with leading zeros
// Prepend (any) leading zeros for this digit group
if (numLeadingZeros != 0)
}
}
/* zero[i] is a string of i consecutive zeros. */
static {
zeros[63] =
"000000000000000000000000000000000000000000000000000000000000000";
for (int i=0; i<63; i++)
}
/**
* Returns the decimal String representation of this BigInteger.
* The digit-to-character mapping provided by
* {@code Character.forDigit} is used, and a minus sign is
* prepended if appropriate. (This representation is compatible
* with the {@link #BigInteger(String) (String)} constructor, and
* allows for String concatenation with Java's + operator.)
*
* @return decimal String representation of this BigInteger.
* @see Character#forDigit
* @see #BigInteger(java.lang.String)
*/
return toString(10);
}
/**
* Returns a byte array containing the two's-complement
* representation of this BigInteger. The byte array will be in
* <i>big-endian</i> byte-order: the most significant byte is in
* the zeroth element. The array will contain the minimum number
* of bytes required to represent this BigInteger, including at
* least one sign bit, which is {@code (ceil((this.bitLength() +
* 1)/8))}. (This representation is compatible with the
* {@link #BigInteger(byte[]) (byte[])} constructor.)
*
* @return a byte array containing the two's-complement representation of
* this BigInteger.
* @see #BigInteger(byte[])
*/
public byte[] toByteArray() {
if (bytesCopied == 4) {
bytesCopied = 1;
} else {
nextInt >>>= 8;
bytesCopied++;
}
}
return byteArray;
}
/**
* Converts this BigInteger to an {@code int}. This
* conversion is analogous to a <a
* href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
* primitive conversion</i></a> from {@code long} to
* {@code int} as defined in the <a
* href="http://java.sun.com/docs/books/jls/html/">Java Language
* Specification</a>: if this BigInteger is too big to fit in an
* {@code int}, only the low-order 32 bits are returned.
* Note that this conversion can lose information about the
* overall magnitude of the BigInteger value as well as return a
* result with the opposite sign.
*
* @return this BigInteger converted to an {@code int}.
*/
public int intValue() {
int result = 0;
return result;
}
/**
* Converts this BigInteger to a {@code long}. This
* conversion is analogous to a <a
* href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
* primitive conversion</i></a> from {@code long} to
* {@code int} as defined in the <a
* href="http://java.sun.com/docs/books/jls/html/">Java Language
* Specification</a>: if this BigInteger is too big to fit in a
* {@code long}, only the low-order 64 bits are returned.
* Note that this conversion can lose information about the
* overall magnitude of the BigInteger value as well as return a
* result with the opposite sign.
*
* @return this BigInteger converted to a {@code long}.
*/
public long longValue() {
long result = 0;
for (int i=1; i>=0; i--)
return result;
}
/**
* Converts this BigInteger to a {@code float}. This
* conversion is similar to the <a
* href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
* primitive conversion</i></a> from {@code double} to
* {@code float} defined in the <a
* href="http://java.sun.com/docs/books/jls/html/">Java Language
* Specification</a>: if this BigInteger has too great a magnitude
* to represent as a {@code float}, it will be converted to
* {@link Float#NEGATIVE_INFINITY} or {@link
* Float#POSITIVE_INFINITY} as appropriate. Note that even when
* the return value is finite, this conversion can lose
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code float}.
*/
public float floatValue() {
// Somewhat inefficient, but guaranteed to work.
}
/**
* Converts this BigInteger to a {@code double}. This
* conversion is similar to the <a
* href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
* primitive conversion</i></a> from {@code double} to
* {@code float} defined in the <a
* href="http://java.sun.com/docs/books/jls/html/">Java Language
* Specification</a>: if this BigInteger has too great a magnitude
* to represent as a {@code double}, it will be converted to
* {@link Double#NEGATIVE_INFINITY} or {@link
* Double#POSITIVE_INFINITY} as appropriate. Note that even when
* the return value is finite, this conversion can lose
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code double}.
*/
public double doubleValue() {
// Somewhat inefficient, but guaranteed to work.
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroInts(int val[]) {
int keep;
// Find first nonzero byte
;
}
/**
* Returns the input array stripped of any leading zero bytes.
* Since the source is trusted the copying may be skipped.
*/
private static int[] trustedStripLeadingZeroInts(int val[]) {
int keep;
// Find first nonzero byte
;
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroBytes(byte a[]) {
int byteLength = a.length;
int keep;
// Find first nonzero byte
;
// Allocate new array and copy relevant part of input array
int b = byteLength - 1;
result[i] = a[b--] & 0xff;
result[i] |= ((a[b--] & 0xff) << j);
}
return result;
}
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero bytes) unsigned whose value is -a.
*/
private static int[] makePositive(byte a[]) {
int keep, k;
int byteLength = a.length;
// Find first non-sign (0xff) byte of input
;
/* Allocate output array. If all non-sign bytes are 0x00, we must
* allocate space for one extra output byte. */
;
/* Copy one's complement of input into output, leaving extra
* byte (if it exists) == 0x00 */
int b = byteLength - 1;
result[i] = a[b--] & 0xff;
if (numBytesToTransfer < 0)
numBytesToTransfer = 0;
result[i] |= ((a[b--] & 0xff) << j);
// Mask indicates which bits must be complemented
}
// Add one to one's complement to generate two's complement
if (result[i] != 0)
break;
}
return result;
}
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero ints) unsigned whose value is -a.
*/
private static int[] makePositive(int a[]) {
int keep, j;
// Find first non-sign (0xffffffff) int of input
;
/* Allocate output array. If all non-sign ints are 0x00, we must
* allocate space for one extra output int. */
;
/* Copy one's complement of input into output, leaving extra
* int (if it exists) == 0x00 */
// Add one to one's complement to generate two's complement
;
return result;
}
/*
* The following two arrays are used for fast String conversions. Both
* are indexed by radix. The first is the number of digits of the given
* radix that can fit in a Java long without "going negative", i.e., the
* highest integer n such that radix**n < 2**63. The second is the
* "long radix" that tears each number into "long digits", each of which
* consists of the number of digits in the corresponding element in
* digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
* nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
* used.
*/
62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
valueOf(0x41c21cb8e1000000L)};
/*
* These two arrays are the integer analogue of above.
*/
11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
};
/**
* These routines provide access to the two's complement representation
* of BigIntegers.
*/
/**
* Returns the length of the two's complement representation in ints,
* including space for at least one sign bit.
*/
private int intLength() {
}
/* Returns sign bit */
private int signBit() {
}
/* Returns an int of sign bits */
private int signInt() {
}
/**
* Returns the specified int of the little-endian two's complement
* representation (int 0 is the least significant). The int number can
* be arbitrarily high (values are logically preceded by infinitely many
* sign ints).
*/
private int getInt(int n) {
if (n < 0)
return 0;
return signInt();
}
/**
* Returns the index of the int that contains the first nonzero int in the
* little-endian binary representation of the magnitude (int 0 is the
* least significant). If the magnitude is zero, return value is undefined.
*/
private int firstNonzeroIntNum() {
fn = 0;
// Search for the first nonzero int
int i;
;
}
return fn;
}
/** use serialVersionUID from JDK 1.1. for interoperability */
private static final long serialVersionUID = -8287574255936472291L;
/**
* Serializable fields for BigInteger.
*
* @serialField signum int
* signum of this BigInteger.
* @serialField magnitude int[]
* magnitude array of this BigInteger.
* @serialField bitCount int
* number of bits in this BigInteger
* @serialField bitLength int
* the number of bits in the minimal two's-complement
* representation of this BigInteger
* @serialField lowestSetBit int
* lowest set bit in the twos complement representation
*/
private static final ObjectStreamField[] serialPersistentFields = {
new ObjectStreamField("magnitude", byte[].class),
};
/**
* Reconstitute the {@code BigInteger} instance from a stream (that is,
* deserialize it). The magnitude is read in as an array of bytes
* for historical reasons, but it is converted to an array of ints
* and the byte array is discarded.
* Note:
* The current convention is to initialize the cache fields, bitCount,
* bitLength and lowestSetBit, to 0 rather than some other marker value.
* Therefore, no explicit action to set these fields needs to be taken in
* readObject because those fields already have a 0 value be default since
* defaultReadObject is not being used.
*/
/*
* In order to maintain compatibility with previous serialized forms,
* the magnitude of a BigInteger is serialized as an array of bytes.
* The magnitude field is used as a temporary store for the byte array
* that is deserialized. The cached computation fields should be
* transient but are serialized for compatibility reasons.
*/
// prepare to read the alternate persistent fields
// Read the alternate persistent fields that we care about
// Validate signum
message = "BigInteger: Signum not present in stream";
}
message = "BigInteger: Magnitude not present in stream";
}
// Commit final fields via Unsafe
// Calculate mag field from magnitude and discard magnitude
}
// Support for resetting final fields while deserializing
private static final long signumOffset;
private static final long magOffset;
static {
try {
}
}
/**
* Save the {@code BigInteger} instance to a stream.
* The magnitude of a BigInteger is serialized as a byte array for
* historical reasons.
*
* @serialData two necessary fields are written as well as obsolete
* fields for compatibility with older versions.
*/
// set the values of the Serializable fields
// The values written for cached fields are compatible with older
// versions, but are ignored in readObject so don't otherwise matter.
// save them
s.writeFields();
}
/**
* Returns the mag array as an array of bytes.
*/
private byte[] magSerializedForm() {
i>=0; i--) {
if (bytesCopied == 4) {
bytesCopied = 1;
} else {
nextInt >>>= 8;
bytesCopied++;
}
}
return result;
}
}