com.dautelle.math.numbers
Class LargeInteger

java.lang.Object
  java.lang.Number
      com.dautelle.math.numbers.RealtimeNumber
          com.dautelle.math.numbers.LargeInteger

All Implemented Interfaces:

java.lang.Comparable, Operable, Realtime, Representable, java.io.Serializable

public final class LargeInteger

extends RealtimeNumber

implements java.lang.Comparable

This class represents an immutable integer number of arbitrary size.

It has the following advantages over the java.math.BigInteger class:

• Optimized for 64 bits architectures. But still runs significantly faster on 32 bits processors.
• Real-time compliant for improved performance and predictability. No temporary object allocated on the heap and no garbage collection if executions are performed within a PoolContext (e.g. add operation 5x faster).
• Implements the Operable interface for modular arithmetic and can be used in conjonction with the Matrix class to resolve modulo equations (ref. number theory).
• Improved algorithms (e.g. Concurrent Karabutsa multiplication in O(n^Log3) instead of O(n²).

Version:

6.0, June 6, 2004

Author:

Jean-Marie Dautelle

See Also:

setModulus, Karatsuba Multiplication -- from MathWorld, Serialized Form

Nested Class Summary

static class

LargeInteger.Value This inner class represents a mutable image of an immutable LargeInteger.

Nested classes inherited from class com.dautelle.math.numbers.RealtimeNumber

RealtimeNumber.Factory

Field Summary

static LargeInteger	ONE The large integer representing the multiplicative identity.
static LargeInteger	ZERO The large integer representing the additive identity.

Method Summary

LargeInteger	abs() Returns the absolute value of this large integer.
LargeInteger	add(LargeInteger that) Returns the sum of this large integer with the one specified.
java.lang.StringBuffer	appendTo(java.lang.StringBuffer sb, int radix) Appends the text representation of this large integer in the specified radix to the StringBuffer argument.
int	bitLength() Returns the minimal number of bits to represent this large integer in the minimal two's-complement (sign excluded).
int	compareTo(java.lang.Object that) Compares two large integer numerically.
LargeInteger	divide(int i) Returns this large integer divided by the specified int.
LargeInteger	divide(LargeInteger that) Returns this large integer divided by the one specified (integer division).
double	doubleValue() Returns the value of this large integeras a double.
LargeInteger	E(int n) Returns the product of this large integer with specified power of 10.
boolean	equals(java.lang.Object that) Compares this large integer against the specified object.
java.lang.Object	export() Exports this object out of the current pool context.
float	floatValue() Returns the value of this large integer as a float.
LargeInteger	gcd(LargeInteger that) Returns the greatest common divisor of this large integer and the one specified.
LargeInteger	getRemainder() Returns the final undivided part after division that is less or of lower degree than the divisor.
int	hashCode() Returns the hash code for this large integer number.
int	intValue() Returns the low order bits of this large integer as an int.
LargeInteger	inverseScaled(int precision) Returns a scaled approximation of 1 / this.
boolean	isLargerThan(LargeInteger that) Indicates if this large integer is larger than the one specified in absolute value.
boolean	isNegative() Indicates if this large integer is less than ZERO.
boolean	isPositive() Indicates if this large integer is greater than ZERO (ZEROis not included).
boolean	isZero() Indicates if this large integer is equal to ZERO.
long	longValue() Returns the low order bits of this large integer as a long.
LargeInteger	mod(LargeInteger m) Returns this large integer modulo the specified large integer.
LargeInteger	multiply(LargeInteger that) Returns the product of this large integer with the one specified.
LargeInteger	multiply(long l) Returns the product of this large integer with the specified long.
LargeInteger	negate() Returns the negation of this large integer.
Operable	opposite() Returns the additive inverse of this object.
Operable	plus(Operable that) Returns the sum of this object with the one specified.
Operable	reciprocal() Returns the modular inverse of this large integer.
static void	setModulus(LargeInteger modulus) Sets the context local modulus for modular arithmetic (used by Operable operations only).
LargeInteger	shiftLeft(int n) Returns the value of this large integer after performing a binary shift to left.
LargeInteger	shiftRight(int n) Returns the value of this large integer after performing a binary shift to right with sign extension (-1 >> 1 == -1).
LargeInteger	subtract(LargeInteger that) Returns the difference between this large integer and the one specified.
Operable	times(Operable that) Returns the product of this object with the one specified.
int	toByteArray(byte[] bytes, int offset) Returns the two's-complement binary representation of this large integer.
java.lang.Object	toHeap() Moves this object to the heap.
java.lang.String	toString() Returns the decimal text representation of this large integer.
java.lang.String	toString(int radix) Returns the text representation of this large integer in the specified radix.
void	toXml(XmlElement xml) Sets the attributes and content of the XML element corresponding to this object.
static LargeInteger	valueOf(java.math.BigInteger bigInteger) Returns the large integer corresponding to the specified BigInteger instance.
static LargeInteger	valueOf(byte[] bytes, int offset, int length) Returns the large integer of specified two's-complement binary representation.
static LargeInteger	valueOf(java.lang.CharSequence chars) Returns the large integer for the specified character sequence in decimal number.
static LargeInteger	valueOf(java.lang.CharSequence chars, int radix) Returns the large integer for the specified character sequence stated in the specified radix.
static LargeInteger	valueOf(long value) Returns the large integer of specified long value.
static LargeInteger	valueOf(XmlElement xml) XML factory method.

Methods inherited from class com.dautelle.math.numbers.RealtimeNumber

clone, isLocalObject, isPoolObject, pow, recycle

Methods inherited from class java.lang.Number

byteValue, shortValue

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

ZERO

public static final LargeInteger ZERO

The large integer representing the additive identity.

ONE

public static final LargeInteger ONE

The large integer representing the multiplicative identity.

Method Detail

valueOf

public static LargeInteger valueOf(long value)

Returns the large integer of specified long value.

Parameters:

value - the long value.

Returns:

the corresponding large integernumber.

valueOf

public static LargeInteger valueOf(byte[] bytes,
                                   int offset,
                                   int length)

Returns the large integer of specified two's-complement binary representation. The input array is assumed to be in big-endian byte-order: the most significant byte is at the offset position.

Note: This representation is consitent with java.lang.BigInteger byte array representation and can be used for conversion between the two classes.

Parameters:

bytes - the binary representation (two's-complement).

offset - the offset at which to start reading the bytes.

length - the maximum number of bytes to read.

Returns:

the corresponding large integer number.

Throws:

java.lang.IndexOutOfBoundsException - if offset + length > bytes.length

See Also:

toByteArray(byte[], int)

valueOf

public static LargeInteger valueOf(java.lang.CharSequence chars)

Returns the large integer for the specified character sequence in decimal number.

Parameters:

chars - the character sequence.

Returns:

valueOf(chars, 10)

valueOf

public static LargeInteger valueOf(java.lang.CharSequence chars,
                                   int radix)

Returns the large integer for the specified character sequence stated in the specified radix. The characters must all be digits of the specified radix, except the first character which may be a plus sign '+' or a minus sign '-'.

Parameters:

chars - the character sequence to parse.

radix - the radix to be used while parsing.

Returns:

the corresponding large integer.

Throws:

java.lang.NumberFormatException - if the specified character sequence does not contain a parsable large integer.

valueOf

public static LargeInteger valueOf(java.math.BigInteger bigInteger)

Returns the large integer corresponding to the specified BigInteger instance.

Parameters:

bigInteger - the big integer instance.

Returns:

the large integer having the same value.

valueOf

public static LargeInteger valueOf(XmlElement xml)

XML factory method.

Parameters:

xml - the XML element describing the integer to return (e.g. <math:Integer value="0"/>).

Returns:

a new integer number as described by the specified xml element.

See Also:

valueOf(CharSequence)

isPositive

public boolean isPositive()

Indicates if this large integer is greater than ZERO (ZEROis not included).

Returns:

this > ZERO

isNegative

public boolean isNegative()

Indicates if this large integer is less than ZERO.

Returns:

this < ZERO

isZero

public boolean isZero()

Indicates if this large integer is equal to ZERO.

Returns:

this == ZERO

getRemainder

public LargeInteger getRemainder()

Returns the final undivided part after division that is less or of lower degree than the divisor. This value is only set by the divide(int) operation and is not considered as part of this large integer (ignored by all methods).

Returns:

the remainder of the division for which this large integer is the quotient.

isLargerThan

public boolean isLargerThan(LargeInteger that)

Indicates if this large integer is larger than the one specified in absolute value.

Parameters:

that - the integer to be compared with.

Returns:

this.abs().compareTo(that.abs()) > 0.

toByteArray

public int toByteArray(byte[] bytes,
                       int offset)

Returns the two's-complement binary representation of this large integer. The output array is in big-endian byte-order: the most significant byte is at the offset position.

Note: This representation is consitent with java.lang.BigInteger byte array representation and can be used for conversion between the two classes.

Parameters:

bytes - the bytes to hold the binary representation (two's-complement) of this large integer.

offset - the offset at which to start writing the bytes.

Returns:

the number of bytes written.

Throws:

java.lang.IndexOutOfBoundsException - if bytes.length < (bitLength() >> 3) + 1

See Also:

valueOf(byte[], int, int), bitLength()

bitLength

public int bitLength()

Returns the minimal number of bits to represent this large integer in the minimal two's-complement (sign excluded).

Returns:

the length of this integer in bits (sign excluded).

negate

public LargeInteger negate()

Returns the negation of this large integer.

Returns:

-this.

add

public LargeInteger add(LargeInteger that)

Returns the sum of this large integer with the one specified.

Parameters:

that - the integer to be added.

Returns:

this + that.

subtract

public LargeInteger subtract(LargeInteger that)

Returns the difference between this large integer and the one specified.

Parameters:

that - the integer to be subtracted.

Returns:

this - that.

multiply

public LargeInteger multiply(long l)

Returns the product of this large integer with the specified long.

Parameters:

l - the long multiplier.

Returns:

this * l.

multiply

public LargeInteger multiply(LargeInteger that)

Returns the product of this large integer with the one specified.

Parameters:

that - the large integer multiplier.

Returns:

this * that.

divide

public LargeInteger divide(int i)

Returns this large integer divided by the specified int. The remainder of this division is accessible using getRemainder().

Parameters:

i - the int divisor.

Returns:

this / i and this % i (getRemainder())

Throws:

java.lang.ArithmeticException - if i == 0

divide

public LargeInteger divide(LargeInteger that)

Returns this large integer divided by the one specified (integer division). This operation is independant from the current modulo (unlike reciprocal()). The remainder of this division is accessible using getRemainder().

Parameters:

that - the integer divisor.

Returns:

this / that and this % that (getRemainder())

Throws:

java.lang.ArithmeticException - if that.equals(ZERO)

inverseScaled

public LargeInteger inverseScaled(int precision)

Returns a scaled approximation of 1 / this.

Parameters:

precision - the requested precision (reciprocal error being ± 1).

Returns:

2(precision + this.bitLength()) / this

Throws:

java.lang.ArithmeticException - if this.isZero()

mod

public LargeInteger mod(LargeInteger m)

Returns this large integer modulo the specified large integer. This method always returns a positive number.

Parameters:

m - the modulus.

Returns:

this mod m

Throws:

java.lang.ArithmeticException - if !m.isPositive()

gcd

public LargeInteger gcd(LargeInteger that)

Returns the greatest common divisor of this large integer and the one specified.

Parameters:

that - the other number to compute the GCD with.

Returns:

a positive number or ZERO if (this.isZero() && that.isZero()).

abs

public LargeInteger abs()

Returns the absolute value of this large integer.

Returns:

abs(this).

shiftLeft

public LargeInteger shiftLeft(int n)

Returns the value of this large integer after performing a binary shift to left. The shift distance, n, may be negative, in which case this method performs a right shift.

Parameters:

n - the shift distance, in bits.

Returns:

this << n.

See Also:

shiftRight(int)

shiftRight

public LargeInteger shiftRight(int n)

Returns the value of this large integer after performing a binary shift to right with sign extension (-1 >> 1 == -1). The shift distance, n, may be negative, in which case this method performs a left shift.

Parameters:

n - the shift distance, in bits.

Returns:

this >> n.

See Also:

shiftLeft(int)

E

public LargeInteger E(int n)

Returns the product of this large integer with specified power of 10. For example:

     LargeInteger billion = LargeInteger.ONE.E(9); // 1E9
     LargeInteger million = billion.E(-3);

Parameters:

n - the decimal exponent.

Returns:

this * 10n

appendTo

public java.lang.StringBuffer appendTo(java.lang.StringBuffer sb,
                                       int radix)

Appends the text representation of this large integer in the specified radix to the StringBuffer argument.

Parameters:

sb - the StringBuffer to append.

radix - the radix of the representation.

Returns:

the specified StringBuffer.

toString

public java.lang.String toString()

Returns the decimal text representation of this large integer.

Returns:

the text representation of this integer number.

toString

public java.lang.String toString(int radix)

Returns the text representation of this large integer in the specified radix.

Parameters:

radix - the radix of the representation.

Returns:

the text representation of this integer number.

equals

public boolean equals(java.lang.Object that)

Compares this large integer against the specified object.

Parameters:

that - the object to compare with.

Returns:

true if the objects are the same; false otherwise.

hashCode

public int hashCode()

Returns the hash code for this large integer number.

Returns:

the hash code value.

intValue

public int intValue()

Returns the low order bits of this large integer as an int.

Note: This conversion can lose information about the overall magnitude of the integer value and may return a result with the opposite sign.

Returns:

the numeric value represented by this integer after conversion to type int.

longValue

public long longValue()

Returns the low order bits of this large integer as a long.

Note: This conversion can lose information about the overall magnitude of the integer value and may return a result with the opposite sign.

Returns:

the numeric value represented by this integer after conversion to type long.

floatValue

public float floatValue()

Returns the value of this large integer as a float.

Returns:

the numeric value represented by this integer after conversion to type float.

doubleValue

public double doubleValue()

Returns the value of this large integeras a double.

Returns:

the numeric value represented by this integer after conversion to type double.

compareTo

public int compareTo(java.lang.Object that)

Compares two large integer numerically.

Specified by:

compareTo in interface java.lang.Comparable

Parameters:

that - the integer to compare with.

Returns:

-1, 0 or 1 as this integer is numerically less than, equal to, or greater than that.

Throws:

java.lang.ClassCastException - that is not a large integer.

setModulus

public static void setModulus(LargeInteger modulus)

Sets the context local modulus for modular arithmetic (used by Operable operations only). If the modulus is not set the reciprocal() operation raises IllegalStateException.

Parameters:

modulus - the new modulus or null to unset the modulus.

Throws:

java.lang.IllegalArgumentException - if modulus <= 0

See Also:

LocalContext, plus, opposite, times, reciprocal

plus

public Operable plus(Operable that)

Description copied from interface: Operable

Returns the sum of this object with the one specified.

Specified by:

plus in interface Operable

Parameters:

that - the object to be added.

Returns:

this + that.

opposite

public Operable opposite()

Description copied from interface: Operable

Returns the additive inverse of this object. It is the object such as this.plus(this.opposite()) == ZERO, with ZERO being the additive identity.

Specified by:

opposite in interface Operable

Returns:

-this.

times

public Operable times(Operable that)

Description copied from interface: Operable

Returns the product of this object with the one specified.

Specified by:

times in interface Operable

Parameters:

that - the object multiplier.

Returns:

this * that.

reciprocal

public Operable reciprocal()

Returns the modular inverse of this large integer.

Specified by:

reciprocal in interface Operable

Returns:

a large integer such as this.times(this.reciprocal()) modulo m = ONE m being the local modulus.

Throws:

java.lang.IllegalStateException - if the modulus is not set.

See Also:

setModulus(com.dautelle.math.numbers.LargeInteger)

toXml

public void toXml(XmlElement xml)

Description copied from interface: Representable

Sets the attributes and content of the XML element corresponding to this object.

Specified by:

toXml in interface Representable

Parameters:

xml - the XML element to set according to this object's desired XML representation.

export

public java.lang.Object export()

Description copied from interface: Realtime

Exports this object out of the current pool context. Realtime members are exported as well (recursion). This method affects only objects belonging to the current pool context. To avoid pool depletion, a "free" object from the outer pool is moved to replace the object being exported.

Specified by:

export in interface Realtime

Overrides:

export in class RealtimeNumber

toHeap

public java.lang.Object toHeap()

Description copied from interface: Realtime

Moves this object to the heap. Realtime members are moved to the heap as well (recursion). This method affects only objects belonging to a pool context (current or not).

Specified by:

toHeap in interface Realtime

Overrides:

toHeap in class RealtimeNumber