Java Big Integers

2010-02-22T09:39:40Z

Newacct:

==What Are They?==

(From sun.com) "Immutable arbitrary-precision integers."
(From Answers.com) Immutable: "Incapable of changing or being modified", meaning the precision cannot be changed (any one else have a better.. desc?)

In 'Laymans' terms, they are very large 'integer' type variables, with the capacity to hold as many digits as your RAM will fit.

==When Should You Use Them?==

They should be used whenever you need to handle very large numbers, anything larger then 'long' variables. Long's have a max a max value of 9223372036854775807. As well, BigInteger provides some useful functions for bit manipulation, GCD, random number, and primality testing and generation.

==Do I Need To Import Anything?==

Yes, add this import line at the top of your java file
Java:
<pre>
import java.math.*;
</pre>

==Declaring A BigInteger Variable (4 Examples)==

Java:
<pre>
BigInteger bigInt0 = BigInteger.ZERO;
BigInteger bigInt1 = BigInteger.ONE;
BigInteger bigInt3 = new BigInteger ("3");
BigInteger bigInt5 = BigInteger.valueOf(5);
</pre>

Note: You cannot pass an int/long into a BigInteger directly, the easiest way to do this it to pass it as a static BigInteger using valueOf, Thank You "OneOffDriveByPoster" for that method.

Java:
<pre>
long num = 9876543210;
BigInteger bigInt123 = BigInteger.valueOf (num);
</pre>

==So, How Do I Use Them?==

Well, BigIntegers contain all the regular math functions, plus more, the main difference is, it does not use symbols such as '*', '+','=','>' etc. rather it uses words (multiply,add,equals,compareTo). Examples;

To Multiply:
Java:
<pre>
bigInt1.multiply(bigInt3);
</pre>
Returns: A Big Integer With Value 3 (1*3)
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Subtract:
Java:
<pre>
bigInt1.subtract(bigInt3);
</pre>
Returns: A BigInteger with value -2 (3-1)
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Compare:
Java:
<pre>
bigInt1.compareTo(bigInt3);
</pre>
Returns: An Integer with a negative value (Less Than), 0 (Equal), positive value (Greater Than), in this case, it will be negative since 1 is less then 3.
Whereas, bigInt1 and bigInt3 are both BigInteger's

To Check If Equal:
Java:
<pre>
bigInt1.equals(bigInt3);
</pre>
Returns: A boolean with a value of false since 1 != 3
Whereas, bigInt1 and bigInt3 are both BigInteger's

You'll notice, its just like dealing with strings (equals, compareTo)...

As well, you can create a new BigInteger inline (outputs 8)
Java:
<pre>
System.out.println ("2**3 = "+new BigInteger("2").pow(3));
</pre>

Note: I Used this as a special example, 'pow', raises the BigInteger '2' to the power of a regular integer '3'. Most of the math methods need BigIntegers as the initial and secondary values but this is a worthy exception to point out.

==Can I Make An Array?==

Sure, why not, arrays can be made of any object/class. Both arrays have a length of 10, both have been initialized to value '1'
Java:
<pre>
//------Example One-------//
BigInteger i = BigInteger.ONE;
BigInteger [] biggg = {i,i,i,i,i,i,i,i,i,i};
</pre>

<pre>
//------Example Two-------//
BigInteger [] biggg = new BigInteger [10];
for (int c = 0; c < biggg.length; c ++){
biggg [c] = BigInteger.ONE;
}
</pre>

==Primality Testing==
You Mentioned Primality Testing...

Checking if a number is prime is easy with BigIntegers,
Java:
<pre>
if (new BigInteger("17").isProbablePrime(5)){
System.out.println("17 Is Prime!");
}
</pre>
Note: The 5 is the certainty that the number is prime, this value reflects how long it takes to complete, for small primes, a value of 1-5 works, but bigger numbers may return false positives unless certainty is >= 5.

==Bit Manipulation==
I'm A 'Bit' Hungry, Let's Do Bit Manipulation!

One of the most used is XOR, in encryption methods. Eg: 65 XOR 42 = 107, and 107 XOR 42 = 65. The work behind this is, it converts the numbers to binary (1's, 0's), and compares the bits in each position, if they are different, bit = 1, if they are the same, bit = 0
Kevin wrote:
<pre>
65: 1000001_______107: 1101011
XOR______________XOR
42: 0101010_______42: 0101010
=________________=
107: 1101011______65: 1000001
</pre>

Java:
<pre>
System.out.println ("65 XOR 42 = "+new BigInteger("65").xor(new BigInteger("42"));
</pre>

==Constant Recomendations==

Seeing how it takes quite a bit of typing to make a new BigInteger every time you say want to multiply something by two... bigInt.multiply (new BigInteger("2");.. etc.. I recommend making some constants at the top of your program for the most common numbers as follows:

Java:
<pre>
BigInteger TWO = new BigInteger ("2");
BigInteger THREE = new BigInteger ("3");
BigInteger FIVE = new BigInteger ("5");
BigInteger TEN = new BigInteger ("10");
...
System.out.println ("2 * 10 = "+TWO.multiply(TEN));
</pre>

==For Loops==
What About For Loops, Can BigIntegers Be Used?[b]

They can be, but it's inadvisable as it will be extremely slow, unless incrementing by say 100 or 1000... (bellow I used 1 for increment)...

Java:
<pre>
for (BigInteger bigCount = BigInteger.ZERO; bigCount.compareTo(new BigInteger ("99999999999999999")) < 0; bigCount = bigCount.add(BigInteger.ONE)){
System.out.println ("Big:"+bigCount);
}
</pre>

==Example Program==
Can I See A Full Program Using BigIntegers?

Sure...A Method To Evaluate Factorials! I used BigInteger for the result, because even 25! uses 26 digits, far larger then the max 'long' capacity.

Java:
<pre>
public static BigInteger factorial(int n){
/* n must be >= 0, 0! = 1, eg: n=5 returns (5x4x3x2x1) */

/* Holds the value of the factorial, in BigInteger form */
BigInteger product = BigInteger.ONE;

/* Inform User that n was erroneous parameter */
if (n < 0){
System.out.println ("Factorial Error! n = "+n);
return new BigInteger ("-1");
}

/* Chain Multiply from 'n' to '1' */
for (int c = n; c > 0; c --){
product = product.multiply(BigInteger.valueOf(c));
}

System.out.println ("Factorial "+n+"! = "+product);

/* Return a BigInteger with the product from n! */
return product;
}// end factorial
</pre>

==For More Information==
For More Information & Complete Method List

Check Out Sun's Java Docs On BigInteger. BigInteger @ Sun.com
(I Highly Recommend You Read Through The Whole Method Summary Section)

As well, for the decimal equivalent, check out 'BigDecimal' BigDecimal @ Sun.com
BigDecimal's use the same concepts as BigInteger, so I wont go into much detail, but if you have questions about BigDecimals, ask away.

If you have any questions, comments, or things to add, feel free to leave a message, or pm me. -Kevin

==Credits==

Author: [[the_short1]]

Added to Wiki by: [[TheFerret]]

Compsci.ca Wiki - User contributions [en]

Java Big Integers