Class BigInt

Class BigInt 

java.lang.Object
   |
   +----java.lang.Number
           |
           +----BigInt
final class BigInt
extends Number
Multiple precision integer arithmetic.

The BigInt class implements integers with unbounded precision. BigInts support the Classical Algorithms of addition, subtraction, multiplication and division giving a quotient and remainder.

BigInts are a subclass of java.lang.Number so they support the conversion operations intValue(), doubleValue etc., just like the other forms of `boxed' number (classes Integer, Float, Long and Double). It is a pity that `Integer' was used as the name for a boxed int. `Int' would have been a more regular name, and it would have left the name `Integer' open for multiple precision integers which better model the mathematical notion of integer.

The algorithms are taken from Knuth, Donald E., "The Art of Computer Programming", volume 2, "Seminumerical Algorithms" section 4.3.1, "Multiple-Precision Arithmetic". The addition, subtraction and multiplication algorithms are relatively simple, but you will probably want to read this text before trying to understand the division algorithm.

BigInts behave like numbers in that they are never modified after creation. For example 

BigInt x = BigInt.valueOf("1000000000000000");
BigInt y = x.add(BigInt.ONE);
System.out.println(x);
prints 1000000000000000.

Operations do not always return new BigInt objects. For example, when adding zero to a thousand digit number, it is more efficient to return the thousand digit number than to make a copy. You should never rely on Java's pointer equality operator (==) to compare BigInts in any way. Implementing these algorithms in Java is quite slow. Ideally, the core methods should be native methods. A Just-In-Time compiler would help, but unless it could lift array bounds checking out of loops, native methods would win every time.

See Also:
Number

Variable Index

o NEGATIVE_ONE
o ONE
o ZERO

Constructor Index

o BigInt(long)
Construct a BigInt with a given long value.

Method Index

o abs()
Return the integer with the same magnitude and positive sign.
o add(BigInt)
Return the sum of two BigInts.
o add(BigInt, BigInt)
Return the sum of two BigInts.
o compare(BigInt)
Compare to another BigInt.
o compare(BigInt, BigInt)
Compare two BigInt
o dbg()
o divide(BigInt, BigInt)
Divide two BigInts, producing the quotient and remainder.
o doubleValue()
Returns the value of the number as a double.
o equals(Object)
Compare two BigInts for numerical equality.
o floatValue()
Returns the value of the number as a float.
o hashCode()
o intValue()
Returns the value of the number as an int.
o lessThan(BigInt)
Ordering comparison.
o longValue()
Returns the value of the number as a long.
o multiply(BigInt)
Return this scaled by multiplicand.
o multiply(long)
Return this scaled by multiplicand.
o multiply(BigInt, BigInt)
Return product of two BigInts.
o negate()
Return the integer with the same magnitude and opposite sign.
o quotient(BigInt, BigInt)
Divide two BigInts, producing the quotient.
o random(Random, BigInt)
Generate a random BigInt.
o random_digit_exponential(Random, BigInt)
Used for testing divide.
o remainder(BigInt, BigInt)
Divide two BigInts, returning the remainder
o subtract(BigInt)
Return the difference of two BigInts.
o subtract(BigInt, BigInt)
Return the difference of two BigInts.
o test()
Test the sign of BigInt.
o toString()
Convert to a radix-10 String.
o toString(int)
Convert to a String.
o valueOf(String)
Convert the String into a BigInt integer.
o valueOf(String, int)
Convert the String into a BigInt integer.

Variables

o ZERO 
  public final static BigInt ZERO
o ONE 
  public final static BigInt ONE
o NEGATIVE_ONE 
  public final static BigInt NEGATIVE_ONE

Constructors

o BigInt 
  public BigInt(long n)
Construct a BigInt with a given long value. 
  BigInt fifty = new BigInt(50);
See Also:
valueOf

Methods

o hashCode 
  public int hashCode()
Overrides:
hashCode in class Object
o equals 
  public boolean equals(Object obj)
Compare two BigInts for numerical equality.

Note: equals will return false if obj is not a BigNum, even if obj makes sense as an integer: 

  BigInt.valueOf("100").equals(BigInt.valueOf("100"))    true
  BigInt.valueOf("100").equals(Integer.valueOf("100"))   false
Overrides:
equals in class Object
o lessThan 
  public boolean lessThan(BigInt comparand)
Ordering comparison.
o test 
  public int test()
Test the sign of BigInt.
Returns:
-1 if it is negative, 0 if it is zero, and 1 if it is positive.
o compare 
  public int compare(BigInt comparand)
Compare to another BigInt.
Parameters:
comparand - a BigInt to compare against.
Returns:
-1 if less than comparand, 0 if equal to comparand, and 1 if greater than comparand.
o compare 
  public static int compare(BigInt x,
                            BigInt y)
Compare two BigInt
Parameters:
x - first BigInt
y - second BigInt
Returns:
-1 if x<y, 0 if x=y, and 1 if x>y
o add 
  public BigInt add(BigInt addend)
Return the sum of two BigInts.
o add 
  public static BigInt add(BigInt x,
                           BigInt y)
Return the sum of two BigInts.
o negate 
  public BigInt negate()
Return the integer with the same magnitude and opposite sign.
o abs 
  public BigInt abs()
Return the integer with the same magnitude and positive sign.
o subtract 
  public BigInt subtract(BigInt y)
Return the difference of two BigInts.
o subtract 
  public static BigInt subtract(BigInt x,
                                BigInt y)
Return the difference of two BigInts.
o multiply 
  public BigInt multiply(BigInt multiplicand)
Return this scaled by multiplicand.
o multiply 
  public BigInt multiply(long multiplicand)
Return this scaled by multiplicand.
o multiply 
  public static BigInt multiply(BigInt x,
                                BigInt y)
Return product of two BigInts.
o divide 
  public static BigInt[] divide(BigInt numerator,
                                BigInt denominator)
Divide two BigInts, producing the quotient and remainder. This is more efficient than computing the values separately.
Returns:
an array of two BigInts, with the quotient at index 0, and the remainder at index 1.
o quotient 
  public static BigInt quotient(BigInt numerator,
                                BigInt denominator)
Divide two BigInts, producing the quotient.
See Also:
divide
o remainder 
  public static BigInt remainder(BigInt numerator,
                                 BigInt denominator)
Divide two BigInts, returning the remainder
See Also:
divide
o valueOf 
  public static BigInt valueOf(String s) throws NumberFormatException
Convert the String into a BigInt integer. The radix is assumed to be 10.
Parameters:
s - the String containing the number
Throws: NumberFormatException
The String cannot be parsed as an integer.
o valueOf 
  public static BigInt valueOf(String s,
                               int radix) throws NumberFormatException
Convert the String into a BigInt integer.
Parameters:
s - the String containing the number
radix - the radix to be used
Throws: NumberFormatException
The String cannot be parsed as an integer.
o toString 
  public String toString()
Convert to a radix-10 String.
Overrides:
toString in class Object
o toString 
  public String toString(int radix)
Convert to a String.
Parameters:
radix - the radix to be used
o dbg 
  public String dbg()
o intValue 
  public int intValue()
Returns the value of the number as an int.
Throws: ArithmeticException
The number is too great to be represented as an int.
Overrides:
intValue in class Number
o longValue 
  public long longValue()
Returns the value of the number as a long.
Throws: ArithmeticException
The number is too big to be represented as a long.
Overrides:
longValue in class Number
o floatValue 
  public float floatValue()
Returns the value of the number as a float. This may involve loss of precision or overflow.
Overrides:
floatValue in class Number
o doubleValue 
  public double doubleValue()
Returns the value of the number as a double. This may involve loss of precision or overflow.
Overrides:
doubleValue in class Number
o random 
  public static BigInt random(Random rng,
                              BigInt limit)
Generate a random BigInt.
Parameters:
rng - the random number generator to use. It is called an unspecified number of times.
limit - specifies the range of the result.
Returns:
a BigInt in the range 0..limit-1 inclusive.
o random_digit_exponential 
  public static BigInt random_digit_exponential(Random rng,
                                                BigInt limit)
Used for testing divide. Generates numbers with an exponential-like distribution. Not otherwise useful.