Big Integers

[chili5]

Big Integers

Java provides three main data types for storing integers.

They are:

• short
• int
• long

Each of these values has a range of numbers that they can contain. The short data type is a 16-bit signed integer. It supports a range of -32,768 to 32,767. The int data type is a 32-bit signed integer. It has a range of -2,147,483,648 to 2,147,483,647. This is usually sufficient for most purposes but what if you need more? The long data type is a 64-bit signed integer with a range of -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. That is HUGE!!! What if it is not enough?

In Java, there is no such thing as long long or unsigned data types. This contrasts to C++. So what choices do you have now? You could implement your own Big Integer class (and this is sometimes required) or you could use the BigInteger class in the Java library. This is one of the things that is great about Java that C++ does not have built-in. This class simply does not have a limit that I know of. It can use some really really big numbers really really quickly. Unfortunately, the syntax for basic operations is not pretty.


Creating a Big Integer

First, you need to import the java.math.*; package. You create a new BigInteger object by using the constructor that accepts a string parameter. This string parameter holds the initial number that you want to the big integer to hold.

Example:

BigInteger a = new BigInteger("33333");

Adding Values

To add values we use the add method. This method returns a BigInteger and accepts as a parameter a BigInteger. So generally what I do is in the add method I use a big integer constructor (which takes a string parameter.)

Example:

 BigInteger a = new BigInteger("9999999999999999999999999999999");
 a = a.add(new BigInteger("383333333222222222"));
 System.out.println(a);

The output of this code is:
10000000000000383333333222222221

That is the sum of 9999999999999999999999999999999 + 383333333222222222


Subtraction

Very similar to the above code, we use the .subtract method. It takes the same parameter as the add method and also returns a reference to a BigInteger object.

 BigInteger a = new BigInteger("9999999999999999999999999999999");
 a = a.subtract(new BigInteger("383333333222222222"));
 System.out.println(a);

The output of this code is:
9999999999999616666666777777777

That is the result of 9999999999999999999999999999999 - 383333333222222222.

Multiplication

This method is again similar to the above two lines. You use the .multiply method.

BigInteger a = new BigInteger("9999999999999999999999999999999");
 a = a.multiply(new BigInteger("383333333222222222"));
 System.out.println(a);

Output:
3833333332222222219999999999999616666666777777778

What you are seeing is the result of 9999999999999999999999999999999 * 383333333222222222.

Division

We use the .divide method to divide two big ints together.

Example:

BigInteger a = new BigInteger("9999999999999999999999999999999");
a = a.divide(new BigInteger("383333333222222222"));
System.out.println(a);

The result is:
26086956529300

Powers

I wanted to show you a really huge number but unfortunately this method doesn't support raising powers to big integers yet.

The method prototype we are going to use is:

BigInteger pow(int exponent);

Notice that the exponent is of type "int" which means it is limited to the range that the integer can hold which we saw above was -2,147,483,648 to 2,147,483,647. However, this method does not support negative exponents. Let us instead raise a big number to the power 10.

99999999999999999 ^ 10.

Code:

BigInteger a = new BigInteger("9999999999999999999999999999999");
a = a.pow(10);
System.out.println(a);

The output is:

99999999999999999999999999999900000000000000000000 00000000004499999999999999999999999999998800000000 00000000000000000000020999999999999999999999999999 99748000000000000000000000000000020999999999999999 99999999999999880000000000000000000000000000004499 99999999999999999999999999990000000000000000000000 0000000001

Woah, that number is huge!!!!!!! My computer is years old and that was generated instantly!!!!!!!

Now I tried this on my computer:

BigInteger a = new BigInteger("9999999999999999999999999999999");
a = a.pow(2147483647);
System.out.println(a);

You can try it if you want, but you most likely will not get an answer. I let that code run for 36 seconds and it did not finish computing. Why may you ask? Well think about it, what is that code above doing? It is multiplying 9999999999999999999999999999999 by itself 2147483647 times. How long would that take you?

Hopefully soon we will be able to solve equations like this:
99999999999999999999999 ^ 9999999999999999999999999999999999999999999

The problem with that is how do you efficiently raise a huge number to a really huge number? You should have noticed by now that the above operations are FAST!!!!!!


Other Operations

There are other methods defined in this class including .mod which is the modulus function. Others include: min, max, gcd (greatest common divisor). I'm going to look into the gcd quickly because this is often used as an exercise in recursion. If you shall let me go off from my train of thought for a second, a recursive algorithm for gcd is:

int gcd(int a, int b) {
       if (b == 0) return a;
      return gcd(b,a%b);
}

This is Euclid's algorithm for gcd. What is it is saying is when a%b is 0 the value of b is the gcd of a and b. That isn't the point so I ain't going to go into it but how well would Euclid's algorithm work for finding the gcd of 9999999999999999999999999999999 and say 3? I've browsed around the java code for BigInteger and this function does indeed use Euclid's algorithm (but it is not recursive.)


The biggest point in this lesson is how you can really be efficient. All of the operations above except for power with really big values my computer computed instantly. I hope this lesson has showed you how efficient you can possibly be.


Ugly syntax

Unfortunately the syntax gets really ugly and this is where I absolutely hate Java developers for not allowing us to overload operators. Consider evaluating ((5000000000 + 300000000) / 20000000) ^ 20000.

BigInteger a = new BigInteger("5000000000");

 // ((5000000000 + 300000000) / 20000000) ^ 20000.
 a = a.add(new BigInteger("300000000")).divide(new BigInteger("200000000")).pow(20000);
System.out.println(a);

Notice all the new constructor calls and method calls chained together. That is just a simple expression. What if you wanted to evaluate cubic equations? To simplify things put one operation on a line. Use several lines of code. It will make it easier to read. Also I'm not even sure if the above code is correct regarding the order of operations.

It would be a lot easier to read if we could overload operators.


BigDecimal

The BigDecimal class is similar to the BigInteger class but it allows you to use decimal values. Give this code a shot:

BigDecimal a = new BigDecimal("10333333333333333333300333333333330.9999999993333333333333333333333339999999");
a = a.add(new BigDecimal("838888888333333333333333333333333338888888.33333333333333333"));
System.out.println(a);

Output:

838888898666666666666666666633666672222219.3333333 326666666633333333333333339999999

I don't need to say much because the details are the same as above.


Notes to other programmers

In C++, a library like this simply does not exist. Although you can find decent big integer libraries online. I found this one: C++ Big Integer Library - Matt McCutchen's Web Site. The great thing about the C++ implementations is that the syntax is better. You can overload operators so you do not have to have .add methods and so on.

The python programmers will be happy to know that the long data type in Python actually is a big integer.

test = 5000000000000000000000000L
test = test + 5033333333333333333333333333L
print test

Try it

Resources

The study of number theory is really interesting and the study is what allows for the efficiency that you have seen above.

Arbitrary-precision arithmetic - Wikipedia, the free encyclopedia
Amazon.com: Elementary Number Theory (9783540761976): Gareth A. Jones, Josephine M. Jones: Books
Amazon.com: Number Theory (Dover Books on Advanced Mathematics) (9780486682525): George E. Andrews: Books
The GNU MP Bignum Library

[Jordan]

Another great one! You are creating all kinds of great tutorials. +rep!

[WingedPanther]

This is one of the great examples of why I prefer C++ to Java. I love having a library like GMP in C++, where I can declare my variable and then treat it just like any other integer type, including using the default operations on it.

+rep