Google Git
Sign in
android / platform / dalvik / 48b6cd7fae6174bb9ac816a162518f8e855a8c90 / . / libcore / math / src / main / java / java / math / BigInteger.java
blob: adef53436d817af6b7734cd837e971fdf4a412a0 [file] [log] [blame]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
// BEGIN android-note
// Since the original Harmony Code of the BigInteger class was strongly modified,
// in order to use the more efficient OpenSSL BIGNUM implementation,
// no android-modification-tags were placed, at all.
// END android-note
package java.math;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Random;
import java.io.Serializable;
/**
* This class represents immutable integer numbers of arbitrary length. Large
* numbers are typically used in security applications and therefore BigIntegers
* offer dedicated functionality like the generation of large prime numbers or
* the computation of modular inverse.
* <p>
* Since the class was modeled to offer all the functionality as the {@link Integer}
* class does, it provides even methods that operate bitwise on a two's
* complement representation of large integers. Note however that the
* implementations favors an internal representation where magnitude and sign
* are treated separately. Hence such operations are inefficient and should be
* discouraged. In simple words: Do NOT implement any bit fields based on
* BigInteger.
* <p>
* <b>Implementation Note:</b> <br>
* The native OpenSSL library with its BIGNUM operations covers all the
* meaningful functionality (everything but bit level operations).
*/
public class BigInteger extends Number implements Comparable<BigInteger>,
Serializable {
/** This is the serialVersionUID used by the sun implementation. */
private static final long serialVersionUID = -8287574255936472291L;
transient BigInt bigInt;
transient private boolean bigIntIsValid = false;
transient private boolean oldReprIsValid = false;
void establishOldRepresentation(String caller) {
if (!oldReprIsValid) {
sign = bigInt.sign();
if (sign != 0) digits = bigInt.littleEndianIntsMagnitude();
else digits = new int[] { 0 };
numberLength = digits.length;
oldReprIsValid = true;
}
}
// The name is confusing:
// This method is called whenever the old representation has been written.
// It ensures that the new representation will be established on demand.
//
BigInteger withNewRepresentation(String caller) {
bigIntIsValid = false;
return this;
}
void validate(String caller, String param) {
if (bigIntIsValid) {
if (bigInt == null)
System.out.print("Claiming bigIntIsValid BUT bigInt == null, ");
else if (bigInt.getNativeBIGNUM() == 0)
System.out.print("Claiming bigIntIsValid BUT bigInt.bignum == 0, ");
}
else {
if (oldReprIsValid) { // establish new representation
if (bigInt == null) bigInt = new BigInt();
bigInt.putLittleEndianInts(digits, (sign < 0));
bigIntIsValid = true;
}
else {
throw new IllegalArgumentException(caller + ":" + param);
}
}
}
static void validate1(String caller, BigInteger a) {
a.validate(caller, "1");
}
static void validate2(String caller, BigInteger a, BigInteger b) {
a.validate(caller, "1");
b.validate(caller, "2");
}
static void validate3(String caller, BigInteger a, BigInteger b, BigInteger c) {
a.validate(caller, "1");
b.validate(caller, "2");
c.validate(caller, "3");
}
static void validate4(String caller, BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
a.validate(caller, "1");
b.validate(caller, "2");
c.validate(caller, "3");
d.validate(caller, "4");
}
/** The magnitude of this in the little-endian representation. */
transient int digits[];
/** The length of this in measured in ints. Can be less than digits.length(). */
transient int numberLength;
/** The sign of this. */
transient int sign;
/**
* The {@code BigInteger} constant 0.
*/
public static final BigInteger ZERO = new BigInteger(0, 0);
/**
* The {@code BigInteger} constant 1.
*/
public static final BigInteger ONE = new BigInteger(1, 1);
/**
* The {@code BigInteger} constant 10.
*/
public static final BigInteger TEN = new BigInteger(1, 10);
/** The {@code BigInteger} constant -1. */
static final BigInteger MINUS_ONE = new BigInteger(-1, 1);
/** The {@code BigInteger} constant 0 used for comparison. */
static final int EQUALS = 0;
/** The {@code BigInteger} constant 1 used for comparison. */
static final int GREATER = 1;
/** The {@code BigInteger} constant -1 used for comparison. */
static final int LESS = -1;
/** All the {@code BigInteger} numbers in the range [0,10] are cached. */
static final BigInteger[] SMALL_VALUES = { ZERO, ONE, new BigInteger(1, 2),
new BigInteger(1, 3), new BigInteger(1, 4), new BigInteger(1, 5),
new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8),
new BigInteger(1, 9), TEN };
/**/
private transient int firstNonzeroDigit = -2;
/** sign field, used for serialization. */
private int signum;
/** absolute value field, used for serialization */
private byte[] magnitude;
/** Cache for the hash code. */
private transient int hashCode = 0;
BigInteger(BigInt a) {
bigInt = a;
bigIntIsValid = true;
validate("BigInteger(BigInt)", "this");
// !oldReprIsValid
}
BigInteger(int sign, long value) {
bigInt = new BigInt();
bigInt.putULongInt(value, (sign < 0));
bigIntIsValid = true;
// !oldReprIsValid
}
/**
* Constructs a number without creating new space. This construct should be
* used only if the three fields of representation are known.
*
* @param sign
* the sign of the number.
* @param numberLength
* the length of the internal array.
* @param digits
* a reference of some array created before.
*/
BigInteger(int sign, int numberLength, int[] digits) {
this.sign = sign;
this.numberLength = numberLength;
this.digits = digits;
oldReprIsValid = true;
withNewRepresentation("BigInteger(int sign, int numberLength, int[] digits)");
}
/**
* Constructs a random non-negative {@code BigInteger} instance in the range
* [0, 2^(numBits)-1].
*
* @param numBits
* maximum length of the new {@code BigInteger} in bits.
* @param rnd
* is an optional random generator to be used.
* @throws IllegalArgumentException
* if {@code numBits} < 0.
*/
public BigInteger(int numBits, Random rnd) {
if (numBits < 0) {
throw new IllegalArgumentException("numBits must be non-negative");
}
if (numBits == 0) {
sign = 0;
numberLength = 1;
digits = new int[] { 0 };
} else {
sign = 1;
numberLength = (numBits + 31) >> 5;
digits = new int[numberLength];
for (int i = 0; i < numberLength; i++) {
digits[i] = rnd.nextInt();
}
// Using only the necessary bits
digits[numberLength - 1] >>>= (-numBits) & 31;
cutOffLeadingZeroes();
}
oldReprIsValid = true;
withNewRepresentation("BigInteger(int numBits, Random rnd)");
}
/**
* Constructs a random {@code BigInteger} instance in the range [0,
* 2^(bitLength)-1] which is probably prime. The probability that the
* returned {@code BigInteger} is prime is beyond (1-1/2^certainty).
* <p>
* <b>Implementation Note:</b>
* Currently {@code rnd} is ignored. The implementation always uses
* method {@code bn_rand} from the OpenSSL library. {@code bn_rand}
* generates cryptographically strong pseudo-random numbers.
* @see <a href="http://www.openssl.org/docs/crypto/BN_rand.html">
* Specification of random generator used from OpenSSL library</a>
*
* @param bitLength
* length of the new {@code BigInteger} in bits.
* @param certainty
* tolerated primality uncertainty.
* @param rnd
* is an optional random generator to be used.
* @throws ArithmeticException
* if {@code bitLength} < 2.
*/
public BigInteger(int bitLength, int certainty, Random rnd) {
if (bitLength < 2) {
throw new ArithmeticException("bitLength < 2");
}
bigInt = BigInt.generatePrimeDefault(bitLength, rnd, null);
bigIntIsValid = true;
// !oldReprIsValid
}
/**
* Constructs a new {@code BigInteger} instance from the string
* representation. The string representation consists of an optional plus or minus
* sign followed by a non-empty sequence of decimal digits.
* Digits are interpreted as if by {@code Character.digit(char, 10)}.
*
* @param val
* string representation of the new {@code BigInteger}.
* @throws NullPointerException
* if {@code val == null}.
* @throws NumberFormatException
* if {@code val} is not a valid representation of a {@code
* BigInteger}.
*/
public BigInteger(String val) {
bigInt = new BigInt();
bigInt.putDecString(val);
bigIntIsValid = true;
// !oldReprIsValid
}
/**
* Constructs a new {@code BigInteger} instance from the string
* representation. The string representation consists of an optional plus or minus
* sign followed by a non-empty sequence of digits in the specified radix.
* Digits are interpreted as if by {@code Character.digit(char, radix)}.
*
* @param val
* string representation of the new {@code BigInteger}.
* @param radix
* the base to be used for the conversion.
* @throws NullPointerException
* if {@code val == null}.
* @throws NumberFormatException
* if {@code val} is not a valid representation of a {@code
* BigInteger} or if {@code radix < Character.MIN_RADIX} or
* {@code radix > Character.MAX_RADIX}.
*/
public BigInteger(String val, int radix) {
if (val == null) {
throw new NullPointerException();
}
if (radix == 10) {
bigInt = new BigInt();
bigInt.putDecString(val);
bigIntIsValid = true;
// !oldReprIsValid
} else if (radix == 16) {
bigInt = new BigInt();
bigInt.putHexString(val);
bigIntIsValid = true;
// !oldReprIsValid
} else {
if ((radix < Character.MIN_RADIX) || (radix > Character.MAX_RADIX)) {
throw new NumberFormatException("Radix out of range");
}
if (val.length() == 0) {
throw new NumberFormatException("Zero-length BigInteger");
}
BigInteger.setFromString(this, val, radix);
// oldReprIsValid == true;
}
}
/**
* Constructs a new {@code BigInteger} instance with the given sign and the
* given magnitude. The sign is given as an integer (-1 for negative, 0 for
* zero, 1 for positive). The magnitude is specified as a byte array. The
* most significant byte is the entry at index 0.
*
* @param signum
* sign of the new {@code BigInteger} (-1 for negative, 0 for
* zero, 1 for positive).
* @param magnitude
* magnitude of the new {@code BigInteger} with the most
* significant byte first.
* @throws NullPointerException
* if {@code magnitude == null}.
* @throws NumberFormatException
* if the sign is not one of -1, 0, 1 or if the sign is zero and
* the magnitude contains non-zero entries.
*/
public BigInteger(int signum, byte[] magnitude) {
if (magnitude == null) {
throw new NullPointerException();
}
if (signum < -1 || signum > 1) {
throw new NumberFormatException("Invalid signum value");
}
if (signum == 0) {
for (byte element : magnitude) {
if (element != 0) {
throw new NumberFormatException("signum-magnitude mismatch");
}
}
}
bigInt = new BigInt();
bigInt.putBigEndian(magnitude, (signum < 0));
bigIntIsValid = true;
}
/**
* Constructs a new {@code BigInteger} from the given two's complement
* representation. The most significant byte is the entry at index 0. The
* most significant bit of this entry determines the sign of the new {@code
* BigInteger} instance. The given array must not be empty.
*
* @param val
* two's complement representation of the new {@code BigInteger}.
* @throws NullPointerException
* if {@code val == null}.
* @throws NumberFormatException
* if the length of {@code val} is zero.
*/
public BigInteger(byte[] val) {
if (val.length == 0) {
throw new NumberFormatException("Zero-length BigInteger");
}
bigInt = new BigInt();
bigInt.putBigEndianTwosComplement(val);
bigIntIsValid = true;
}
/**
* Creates a new {@code BigInteger} whose value is equal to the specified
* {@code long} argument.
*
* @param val
* the value of the new {@code BigInteger}.
* @return {@code BigInteger} instance with the value {@code val}.
*/
public static BigInteger valueOf(long val) {
if (val < 0) {
if(val != -1) {
return new BigInteger(-1, -val);
}
return MINUS_ONE;
} else if (val <= 10) {
return SMALL_VALUES[(int) val];
} else {// (val > 10)
return new BigInteger(1, val);
}
}
/**
* Returns the two's complement representation of this BigInteger in a byte
* array.
*
* @return two's complement representation of {@code this}.
*/
public byte[] toByteArray() {
return twosComplement();
}
/**
* Returns a (new) {@code BigInteger} whose value is the absolute value of
* {@code this}.
*
* @return {@code abs(this)}.
*/
public BigInteger abs() {
validate1("abs()", this);
if (bigInt.sign() >= 0) return this;
else {
BigInt a = bigInt.copy();
a.setSign(1);
return new BigInteger(a);
}
}
/**
* Returns a new {@code BigInteger} whose value is the {@code -this}.
*
* @return {@code -this}.
*/
public BigInteger negate() {
validate1("negate()", this);
int sign = bigInt.sign();
if (sign == 0) return this;
else {
BigInt a = bigInt.copy();
a.setSign(-sign);
return new BigInteger(a);
}
}
/**
* Returns a new {@code BigInteger} whose value is {@code this + val}.
*
* @param val
* value to be added to {@code this}.
* @return {@code this + val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger add(BigInteger val) {
validate2("add", this, val);
if (val.bigInt.sign() == 0) return this;
if (bigInt.sign() == 0) return val;
return new BigInteger(BigInt.addition(bigInt, val.bigInt));
}
/**
* Returns a new {@code BigInteger} whose value is {@code this - val}.
*
* @param val
* value to be subtracted from {@code this}.
* @return {@code this - val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger subtract(BigInteger val) {
validate2("subtract", this, val);
if (val.bigInt.sign() == 0) return this;
else return new BigInteger(BigInt.subtraction(bigInt, val.bigInt));
}
/**
* Returns the sign of this {@code BigInteger}.
*
* @return {@code -1} if {@code this < 0},
* {@code 0} if {@code this == 0},
* {@code 1} if {@code this > 0}.
*/
public int signum() {
// Optimization to avoid unnecessary duplicate representation:
if (oldReprIsValid) return sign;
// else:
validate1("signum", this);
return bigInt.sign();
}
/**
* Returns a new {@code BigInteger} whose value is {@code this >> n}. For
* negative arguments, the result is also negative. The shift distance may
* be negative which means that {@code this} is shifted left.
* <p>
* <b>Implementation Note:</b> Usage of this method on negative values is
* not recommended as the current implementation is not efficient.
*
* @param n
* shift distance
* @return {@code this >> n} if {@code n >= 0}; {@code this << (-n)}
* otherwise
*/
public BigInteger shiftRight(int n) {
return shiftLeft(-n);
}
/**
* Returns a new {@code BigInteger} whose value is {@code this << n}. The
* result is equivalent to {@code this * 2^n} if n >= 0. The shift distance
* may be negative which means that {@code this} is shifted right. The
* result then corresponds to {@code floor(this / 2^(-n))}.
* <p>
* <b>Implementation Note:</b> Usage of this method on negative values is
* not recommended as the current implementation is not efficient.
*
* @param n
* shift distance.
* @return {@code this << n} if {@code n >= 0}; {@code this >> (-n)}.
* otherwise
*/
public BigInteger shiftLeft(int n) {
if (n == 0) return this;
int sign = signum();
if (sign == 0) return this;
if ((sign > 0) || (n >= 0)) {
validate1("shiftLeft", this);
return new BigInteger(BigInt.shift(bigInt, n));
}
else {
// Negative numbers faking 2's complement:
// Not worth optimizing this:
// Sticking to Harmony Java implementation.
//
return BitLevel.shiftRight(this, -n);
}
}
BigInteger shiftLeftOneBit() {
return (signum() == 0) ? this : BitLevel.shiftLeftOneBit(this);
}
/**
* Returns the length of the value's two's complement representation without
* leading zeros for positive numbers / without leading ones for negative
* values.
* <p>
* The two's complement representation of {@code this} will be at least
* {@code bitLength() + 1} bits long.
* <p>
* The value will fit into an {@code int} if {@code bitLength() < 32} or
* into a {@code long} if {@code bitLength() < 64}.
*
* @return the length of the minimal two's complement representation for
* {@code this} without the sign bit.
*/
public int bitLength() {
// Optimization to avoid unnecessary duplicate representation:
if (!bigIntIsValid && oldReprIsValid) return BitLevel.bitLength(this);
// else:
validate1("bitLength", this);
return bigInt.bitLength();
}
/**
* Tests whether the bit at position n in {@code this} is set. The result is
* equivalent to {@code this & (2^n) != 0}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param n
* position where the bit in {@code this} has to be inspected.
* @return {@code this & (2^n) != 0}.
* @throws ArithmeticException
* if {@code n < 0}.
*/
public boolean testBit(int n) {
if (n < 0) {
throw new ArithmeticException("n < 0");
}
int sign = signum();
if ((sign > 0) && bigIntIsValid && !oldReprIsValid) {
validate1("testBit", this);
return bigInt.isBitSet(n);
}
else {
// Negative numbers faking 2's complement:
// Not worth optimizing this:
// Sticking to Harmony Java implementation.
//
establishOldRepresentation("testBit");
if (n == 0) {
return ((digits[0] & 1) != 0);
}
int intCount = n >> 5;
if (intCount >= numberLength) {
return (sign < 0);
}
int digit = digits[intCount];
n = (1 << (n & 31)); // int with 1 set to the needed position
if (sign < 0) {
int firstNonZeroDigit = getFirstNonzeroDigit();
if ( intCount < firstNonZeroDigit ){
return false;
}else if( firstNonZeroDigit == intCount ){
digit = -digit;
}else{
digit = ~digit;
}
}
return ((digit & n) != 0);
}
}
/**
* Returns a new {@code BigInteger} which has the same binary representation
* as {@code this} but with the bit at position n set. The result is
* equivalent to {@code this | 2^n}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param n
* position where the bit in {@code this} has to be set.
* @return {@code this | 2^n}.
* @throws ArithmeticException
* if {@code n < 0}.
*/
public BigInteger setBit(int n) {
establishOldRepresentation("setBit");
if( !testBit( n ) ){
return BitLevel.flipBit(this, n);
}else{
return this;
}
}
/**
* Returns a new {@code BigInteger} which has the same binary representation
* as {@code this} but with the bit at position n cleared. The result is
* equivalent to {@code this & ~(2^n)}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param n
* position where the bit in {@code this} has to be cleared.
* @return {@code this & ~(2^n)}.
* @throws ArithmeticException
* if {@code n < 0}.
*/
public BigInteger clearBit(int n) {
establishOldRepresentation("clearBit");
if (testBit(n)) {
return BitLevel.flipBit(this, n);
} else {
return this;
}
}
/**
* Returns a new {@code BigInteger} which has the same binary representation
* as {@code this} but with the bit at position n flipped. The result is
* equivalent to {@code this ^ 2^n}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param n
* position where the bit in {@code this} has to be flipped.
* @return {@code this ^ 2^n}.
* @throws ArithmeticException
* if {@code n < 0}.
*/
public BigInteger flipBit(int n) {
establishOldRepresentation("flipBit");
if (n < 0) {
throw new ArithmeticException("n < 0");
}
return BitLevel.flipBit(this, n);
}
/**
* Returns the position of the lowest set bit in the two's complement
* representation of this {@code BigInteger}. If all bits are zero (this=0)
* then -1 is returned as result.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @return position of lowest bit if {@code this != 0}, {@code -1} otherwise
*/
public int getLowestSetBit() {
establishOldRepresentation("getLowestSetBit");
if (sign == 0) {
return -1;
}
// (sign != 0) implies that exists some non zero digit
int i = getFirstNonzeroDigit();
return ((i << 5) + Integer.numberOfTrailingZeros(digits[i]));
}
/**
* Use {@code bitLength(0)} if you want to know the length of the binary
* value in bits.
* <p>
* Returns the number of bits in the binary representation of {@code this}
* which differ from the sign bit. If {@code this} is positive the result is
* equivalent to the number of bits set in the binary representation of
* {@code this}. If {@code this} is negative the result is equivalent to the
* number of bits set in the binary representation of {@code -this-1}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @return number of bits in the binary representation of {@code this} which
* differ from the sign bit
*/
public int bitCount() {
establishOldRepresentation("bitCount");
return BitLevel.bitCount(this);
}
/**
* Returns a new {@code BigInteger} whose value is {@code ~this}. The result
* of this operation is {@code -this-1}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @return {@code ~this}.
*/
public BigInteger not() {
this.establishOldRepresentation("not");
return Logical.not(this).withNewRepresentation("not");
}
/**
* Returns a new {@code BigInteger} whose value is {@code this & val}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param val
* value to be and'ed with {@code this}.
* @return {@code this & val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger and(BigInteger val) {
this.establishOldRepresentation("and1");
val.establishOldRepresentation("and2");
return Logical.and(this, val).withNewRepresentation("and");
}
/**
* Returns a new {@code BigInteger} whose value is {@code this | val}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param val
* value to be or'ed with {@code this}.
* @return {@code this | val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger or(BigInteger val) {
this.establishOldRepresentation("or1");
val.establishOldRepresentation("or2");
return Logical.or(this, val).withNewRepresentation("or");
}
/**
* Returns a new {@code BigInteger} whose value is {@code this ^ val}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param val
* value to be xor'ed with {@code this}
* @return {@code this ^ val}
* @throws NullPointerException
* if {@code val == null}
*/
public BigInteger xor(BigInteger val) {
this.establishOldRepresentation("xor1");
val.establishOldRepresentation("xor2");
return Logical.xor(this, val).withNewRepresentation("xor");
}
/**
* Returns a new {@code BigInteger} whose value is {@code this & ~val}.
* Evaluating {@code x.andNot(val)} returns the same result as {@code
* x.and(val.not())}.
* <p>
* <b>Implementation Note:</b> Usage of this method is not recommended as
* the current implementation is not efficient.
*
* @param val
* value to be not'ed and then and'ed with {@code this}.
* @return {@code this & ~val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger andNot(BigInteger val) {
this.establishOldRepresentation("andNot1");
val.establishOldRepresentation("andNot2");
return Logical.andNot(this, val).withNewRepresentation("andNot");
}
/**
* Returns this {@code BigInteger} as an int value. If {@code this} is too
* big to be represented as an int, then {@code this} % 2^32 is returned.
*
* @return this {@code BigInteger} as an int value.
*/
@Override
public int intValue() {
if (bigIntIsValid && (bigInt.twosCompFitsIntoBytes(4))) {
return (int)bigInt.longInt();
}
else {
this.establishOldRepresentation("intValue()");
return (sign * digits[0]);
}
}
/**
* Returns this {@code BigInteger} as an long value. If {@code this} is too
* big to be represented as an long, then {@code this} % 2^64 is returned.
*
* @return this {@code BigInteger} as a long value.
*/
@Override
public long longValue() {
if (bigIntIsValid && (bigInt.twosCompFitsIntoBytes(8))) {
establishOldRepresentation("longValue()");
return bigInt.longInt();
}
else {
establishOldRepresentation("longValue()");
long value = (numberLength > 1) ? (((long) digits[1]) << 32)
| (digits[0] & 0xFFFFFFFFL) : (digits[0] & 0xFFFFFFFFL);
return (sign * value);
}
}
/**
* Returns this {@code BigInteger} as an float value. If {@code this} is too
* big to be represented as an float, then {@code Float.POSITIVE_INFINITY}
* or {@code Float.NEGATIVE_INFINITY} is returned. Note, that not all
* integers x in the range [-Float.MAX_VALUE, Float.MAX_VALUE] can be
* represented as a float. The float representation has a mantissa of length
* 24. For example, 2^24+1 = 16777217 is returned as float 16777216.0.
*
* @return this {@code BigInteger} as a float value.
*/
@Override
public float floatValue() {
establishOldRepresentation("floatValue()");
return (float) doubleValue();
}
/**
* Returns this {@code BigInteger} as an double value. If {@code this} is
* too big to be represented as an double, then {@code
* Double.POSITIVE_INFINITY} or {@code Double.NEGATIVE_INFINITY} is
* returned. Note, that not all integers x in the range [-Double.MAX_VALUE,
* Double.MAX_VALUE] can be represented as a double. The double
* representation has a mantissa of length 53. For example, 2^53+1 =
* 9007199254740993 is returned as double 9007199254740992.0.
*
* @return this {@code BigInteger} as a double value
*/
@Override
public double doubleValue() {
establishOldRepresentation("doubleValue()");
return Conversion.bigInteger2Double(this);
}
/**
* Compares this {@code BigInteger} with {@code val}. Returns one of the
* three values 1, 0, or -1.
*
* @param val
* value to be compared with {@code this}.
* @return {@code 1} if {@code this > val}, {@code -1} if {@code this < val}
* , {@code 0} if {@code this == val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public int compareTo(BigInteger val) {
validate2("compareTo", this, val);
return BigInt.cmp(bigInt, val.bigInt);
}
/**
* Returns the minimum of this {@code BigInteger} and {@code val}.
*
* @param val
* value to be used to compute the minimum with {@code this}.
* @return {@code min(this, val)}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger min(BigInteger val) {
return ((this.compareTo(val) == -1) ? this : val);
}
/**
* Returns the maximum of this {@code BigInteger} and {@code val}.
*
* @param val
* value to be used to compute the maximum with {@code this}
* @return {@code max(this, val)}
* @throws NullPointerException
* if {@code val == null}
*/
public BigInteger max(BigInteger val) {
return ((this.compareTo(val) == 1) ? this : val);
}
/**
* Returns a hash code for this {@code BigInteger}.
*
* @return hash code for {@code this}.
*/
@Override
public int hashCode() {
validate1("hashCode", this);
if (hashCode != 0) {
return hashCode;
}
establishOldRepresentation("hashCode");
for (int i = 0; i < digits.length; i ++) {
hashCode = (int)(hashCode * 33 + (digits[i] & 0xffffffff));
}
hashCode = hashCode * sign;
return hashCode;
}
/**
* Returns {@code true} if {@code x} is a BigInteger instance and if this
* instance is equal to this {@code BigInteger}.
*
* @param x
* object to be compared with {@code this}.
* @return true if {@code x} is a BigInteger and {@code this == x},
* {@code false} otherwise.
*/
@Override
public boolean equals(Object x) {
if (this == x) {
return true;
}
if (x instanceof BigInteger) {
return this.compareTo((BigInteger)x) == 0;
}
return false;
}
/**
* Returns a string representation of this {@code BigInteger} in decimal
* form.
*
* @return a string representation of {@code this} in decimal form.
*/
@Override
public String toString() {
validate1("toString()", this);
return bigInt.decString();
}
/**
* Returns a string containing a string representation of this {@code
* BigInteger} with base radix. If {@code radix < Character.MIN_RADIX} or
* {@code radix > Character.MAX_RADIX} then a decimal representation is
* returned. The characters of the string representation are generated with
* method {@code Character.forDigit}.
*
* @param radix
* base to be used for the string representation.
* @return a string representation of this with radix 10.
*/
public String toString(int radix) {
validate1("toString(int radix)", this);
if (radix == 10) {
return bigInt.decString();
// } else if (radix == 16) {
// return bigInt.hexString();
} else {
establishOldRepresentation("toString(int radix)");
return Conversion.bigInteger2String(this, radix);
}
}
/**
* Returns a new {@code BigInteger} whose value is greatest common divisor
* of {@code this} and {@code val}. If {@code this==0} and {@code val==0}
* then zero is returned, otherwise the result is positive.
*
* @param val
* value with which the greatest common divisor is computed.
* @return {@code gcd(this, val)}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger gcd(BigInteger val) {
validate2("gcd", this, val);
return new BigInteger(BigInt.gcd(bigInt, val.bigInt, null));
}
/**
* Returns a new {@code BigInteger} whose value is {@code this * val}.
*
* @param val
* value to be multiplied with {@code this}.
* @return {@code this * val}.
* @throws NullPointerException
* if {@code val == null}.
*/
public BigInteger multiply(BigInteger val) {
validate2("multiply", this, val);
return new BigInteger(BigInt.product(bigInt, val.bigInt, null));
}
/**
* Returns a new {@code BigInteger} whose value is {@code this ^ exp}.
*
* @param exp
* exponent to which {@code this} is raised.
* @return {@code this ^ exp}.
* @throws ArithmeticException
* if {@code exp < 0}.
*/
public BigInteger pow(int exp) {
if (exp < 0) {
throw new ArithmeticException("exp < 0");
}
validate1("pow", this);
return new BigInteger(BigInt.exp(bigInt, exp, null));
}
/**
* Returns a {@code BigInteger} array which contains {@code this / divisor}
* at index 0 and {@code this % divisor} at index 1.
*
* @param divisor
* value by which {@code this} is divided.
* @return {@code [this / divisor, this % divisor]}.
* @throws NullPointerException
* if {@code divisor == null}.
* @throws ArithmeticException
* if {@code divisor == 0}.
* @see #divide
* @see #remainder
*/
public BigInteger[] divideAndRemainder(BigInteger divisor) {
validate2("divideAndRemainder", this, divisor);
BigInt quotient = new BigInt();
BigInt remainder = new BigInt();
BigInt.division(bigInt, divisor.bigInt, null, quotient, remainder);
BigInteger[] a = new BigInteger[2];
a[0] = new BigInteger(quotient);
a[1] = new BigInteger(remainder);
a[0].validate("divideAndRemainder", "quotient");
a[1].validate("divideAndRemainder", "remainder");
return a;
}
/**
* Returns a new {@code BigInteger} whose value is {@code this / divisor}.
*
* @param divisor
* value by which {@code this} is divided.
* @return {@code this / divisor}.
* @throws NullPointerException
* if {@code divisor == null}.
* @throws ArithmeticException
* if {@code divisor == 0}.
*/
public BigInteger divide(BigInteger divisor) {
validate2("divide", this, divisor);
BigInt quotient = new BigInt();
BigInt.division(bigInt, divisor.bigInt, null, quotient, null);
return new BigInteger(quotient);
}
/**
* Returns a new {@code BigInteger} whose value is {@code this % divisor}.
* Regarding signs this methods has the same behavior as the % operator on
* int's, i.e. the sign of the remainder is the same as the sign of this.
*
* @param divisor
* value by which {@code this} is divided.
* @return {@code this % divisor}.
* @throws NullPointerException
* if {@code divisor == null}.
* @throws ArithmeticException
* if {@code divisor == 0}.
*/
public BigInteger remainder(BigInteger divisor) {
validate2("remainder", this, divisor);
BigInt remainder = new BigInt();
BigInt.division(bigInt, divisor.bigInt, null, null, remainder);
return new BigInteger(remainder);
}
/**
* Returns a new {@code BigInteger} whose value is {@code 1/this mod m}. The
* modulus {@code m} must be positive. The result is guaranteed to be in the
* interval {@code [0, m)} (0 inclusive, m exclusive). If {@code this} is
* not relatively prime to m, then an exception is thrown.
*
* @param m
* the modulus.
* @return {@code 1/this mod m}.
* @throws NullPointerException
* if {@code m == null}
* @throws ArithmeticException
* if {@code m < 0 or} if {@code this} is not relatively prime
* to {@code m}
*/
public BigInteger modInverse(BigInteger m) {
if (m.signum() <= 0) {
throw new ArithmeticException("modulus not positive");
}
validate2("modInverse", this, m);
return new BigInteger(BigInt.modInverse(bigInt, m.bigInt, null));
}
/**
* Returns a new {@code BigInteger} whose value is {@code this^exponent mod
* m}. The modulus {@code m} must be positive. The result is guaranteed to
* be in the interval {@code [0, m)} (0 inclusive, m exclusive). If the
* exponent is negative, then {@code this.modInverse(m)^(-exponent) mod m)}
* is computed. The inverse of this only exists if {@code this} is
* relatively prime to m, otherwise an exception is thrown.
*
* @param exponent
* the exponent.
* @param m
* the modulus.
* @return {@code this^exponent mod val}.
* @throws NullPointerException
* if {@code m == null} or {@code exponent == null}.
* @throws ArithmeticException
* if {@code m < 0} or if {@code exponent<0} and this is not
* relatively prime to {@code m}.
*/
public BigInteger modPow(BigInteger exponent, BigInteger m) {
if (m.signum() <= 0) {
throw new ArithmeticException("modulus not positive");
}
BigInteger base;
if (exponent.signum() < 0) {
base = modInverse(m);
// exponent = exponent.negate(); // Not needed as sign is ignored anyway!
} else {
base = this;
}
validate3("modPow", base, exponent, m);
return new BigInteger(BigInt.modExp(base.bigInt, exponent.bigInt, m.bigInt, null));
}
/**
* Returns a new {@code BigInteger} whose value is {@code this mod m}. The
* modulus {@code m} must be positive. The result is guaranteed to be in the
* interval {@code [0, m)} (0 inclusive, m exclusive). The behavior of this
* function is not equivalent to the behavior of the % operator defined for
* the built-in {@code int}'s.
*
* @param m
* the modulus.
* @return {@code this mod m}.
* @throws NullPointerException
* if {@code m == null}.
* @throws ArithmeticException
* if {@code m < 0}.
*/
public BigInteger mod(BigInteger m) {
if (m.signum() <= 0) {
throw new ArithmeticException("modulus not positive");
}
validate2("mod", this, m);
return new BigInteger(BigInt.modulus(bigInt, m.bigInt, null));
}
/**
* Tests whether this {@code BigInteger} is probably prime. If {@code true}
* is returned, then this is prime with a probability beyond
* (1-1/2^certainty). If {@code false} is returned, then this is definitely
* composite. If the argument {@code certainty} <= 0, then this method
* returns true.
*
* @param certainty
* tolerated primality uncertainty.
* @return {@code true}, if {@code this} is probably prime, {@code false}
* otherwise.
*/
public boolean isProbablePrime(int certainty) {
if (certainty <= 0) {
return true;
}
validate1("isProbablePrime", this);
return bigInt.isPrime(certainty, null, null);
}
/**
* Returns the smallest integer x > {@code this} which is probably prime as
* a {@code BigInteger} instance. The probability that the returned {@code
* BigInteger} is prime is beyond (1-1/2^80).
*
* @return smallest integer > {@code this} which is probably prime.
* @throws ArithmeticException
* if {@code this < 0}.
*/
public BigInteger nextProbablePrime() {
if (sign < 0) {
throw new ArithmeticException("sign < 0");
}
return Primality.nextProbablePrime(this);
}
/**
* Returns a random positive {@code BigInteger} instance in the range [0,
* 2^(bitLength)-1] which is probably prime. The probability that the
* returned {@code BigInteger} is prime is beyond (1-1/2^80).
* <p>
* <b>Implementation Note:</b> Currently {@code rnd} is ignored.
*
* @param bitLength
* length of the new {@code BigInteger} in bits.
* @param rnd
* random generator used to generate the new {@code BigInteger}.
* @return probably prime random {@code BigInteger} instance.
* @throws IllegalArgumentException
* if {@code bitLength < 2}.
*/
public static BigInteger probablePrime(int bitLength, Random rnd) {
return new BigInteger(bitLength, 100, rnd);
}
/* Private Methods */
/**
* Returns the two's complement representation of this BigInteger in a byte
* array.
*
* @return two's complement representation of {@code this}
*/
private byte[] twosComplement() {
establishOldRepresentation("twosComplement()");
if( this.sign == 0 ){
return new byte[]{0};
}
BigInteger temp = this;
int bitLen = bitLength();
int iThis = getFirstNonzeroDigit();
int bytesLen = (bitLen >> 3) + 1;
/* Puts the little-endian int array representing the magnitude
* of this BigInteger into the big-endian byte array. */
byte[] bytes = new byte[bytesLen];
int firstByteNumber = 0;
int highBytes;
int digitIndex = 0;
int bytesInInteger = 4;
int digit;
int hB;
if (bytesLen - (numberLength << 2) == 1) {
bytes[0] = (byte) ((sign < 0) ? -1 : 0);
highBytes = 4;
firstByteNumber++;
} else {
hB = bytesLen & 3;
highBytes = (hB == 0) ? 4 : hB;
}
digitIndex = iThis;
bytesLen -= iThis << 2;
if (sign < 0) {
digit = -temp.digits[digitIndex];
digitIndex++;
if(digitIndex == numberLength){
bytesInInteger = highBytes;
}
for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
bytes[--bytesLen] = (byte) digit;
}
while( bytesLen > firstByteNumber ){
digit = ~temp.digits[digitIndex];
digitIndex++;
if(digitIndex == numberLength){
bytesInInteger = highBytes;
}
for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
bytes[--bytesLen] = (byte) digit;
}
}
} else {
while (bytesLen > firstByteNumber) {
digit = temp.digits[digitIndex];
digitIndex++;
if (digitIndex == numberLength) {
bytesInInteger = highBytes;
}
for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
bytes[--bytesLen] = (byte) digit;
}
}
}
return bytes;
}
static int multiplyByInt(int res[], int a[], final int aSize, final int factor) {
long carry = 0;
for (int i = 0; i < aSize; i++) {
carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL);
res[i] = (int)carry;
carry >>>= 32;
}
return (int)carry;
}
static int inplaceAdd(int a[], final int aSize, final int addend) {
long carry = addend & 0xFFFFFFFFL;
for (int i = 0; (carry != 0) && (i < aSize); i++) {
carry += a[i] & 0xFFFFFFFFL;
a[i] = (int) carry;
carry >>= 32;
}
return (int) carry;
}
/** @see BigInteger#BigInteger(String, int) */
private static void setFromString(BigInteger bi, String val, int radix) {
int sign;
int[] digits;
int numberLength;
int stringLength = val.length();
int startChar;
int endChar = stringLength;
if (val.charAt(0) == '-') {
sign = -1;
startChar = 1;
stringLength--;
} else {
sign = 1;
startChar = 0;
}
/*
* We use the following algorithm: split a string into portions of n
* characters and convert each portion to an integer according to the
* radix. Then convert an exp(radix, n) based number to binary using the
* multiplication method. See D. Knuth, The Art of Computer Programming,
* vol. 2.
*/
int charsPerInt = Conversion.digitFitInInt[radix];
int bigRadixDigitsLength = stringLength / charsPerInt;
int topChars = stringLength % charsPerInt;
if (topChars != 0) {
bigRadixDigitsLength++;
}
digits = new int[bigRadixDigitsLength];
// Get the maximal power of radix that fits in int
int bigRadix = Conversion.bigRadices[radix - 2];
// Parse an input string and accumulate the BigInteger's magnitude
int digitIndex = 0; // index of digits array
int substrEnd = startChar + ((topChars == 0) ? charsPerInt : topChars);
int newDigit;
for (int substrStart = startChar; substrStart < endChar; substrStart = substrEnd, substrEnd = substrStart
+ charsPerInt) {
int bigRadixDigit = Integer.parseInt(val.substring(substrStart,
substrEnd), radix);
newDigit = multiplyByInt(digits, digits, digitIndex, bigRadix);
newDigit += inplaceAdd(digits, digitIndex, bigRadixDigit);
digits[digitIndex++] = newDigit;
}
numberLength = digitIndex;
bi.sign = sign;
bi.numberLength = numberLength;
bi.digits = digits;
bi.cutOffLeadingZeroes();
bi.oldReprIsValid = true;
bi.withNewRepresentation("Cordoba-BigInteger: private static setFromString");
}
/** Decreases {@code numberLength} if there are zero high elements. */
final void cutOffLeadingZeroes() {
while ((numberLength > 0) && (digits[--numberLength] == 0)) {
;
}
if (digits[numberLength++] == 0) {
sign = 0;
}
}
/** Tests if {@code this.abs()} is equals to {@code ONE} */
boolean isOne() {
// System.out.println("isOne");
return ((numberLength == 1) && (digits[0] == 1));
}
int getFirstNonzeroDigit(){
// validate1("Cordoba-BigInteger: getFirstNonzeroDigit", this);
if( firstNonzeroDigit == -2 ){
int i;
if( this.sign == 0 ){
i = -1;
} else{
for(i=0; digits[i]==0; i++)
;
}
firstNonzeroDigit = i;
}
return firstNonzeroDigit;
}
/*
* Returns a copy of the current instance to achieve immutability
*/
// Only used by Primality.nextProbablePrime()
BigInteger copy() {
establishOldRepresentation("copy()");
int[] copyDigits = new int[numberLength];
System.arraycopy(digits, 0, copyDigits, 0, numberLength);
return new BigInteger(sign, numberLength, copyDigits);
}
/**
* Assignes all transient fields upon deserialization of a
* {@code BigInteger} instance.
*/
private void readObject(ObjectInputStream in) throws IOException,
ClassNotFoundException {
in.defaultReadObject();
bigInt = new BigInt();
bigInt.putBigEndian(magnitude, (signum < 0));
bigIntIsValid = true;
// !oldReprIsValid
}
/**
* Prepares this {@code BigInteger} for serialization, i.e. the
* non-transient fields {@code signum} and {@code magnitude} are assigned.
*/
private void writeObject(ObjectOutputStream out) throws IOException {
validate("writeObject", "this");
signum = bigInt.sign();
// if (magnitude == null)
magnitude = bigInt.bigEndianMagnitude();
out.defaultWriteObject();
}
void unCache(){
firstNonzeroDigit = -2;
}
}