Introducing BigInteger

Most ordinary-scale programs don’t use very large numbers, but today I’ll show you how to use Java to do some more serious calculating, with the Fibonacci numbers as an example:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

The numbers in this sequence always get larger, so you don’t need to be a software engineer to see that int and long wont be big enough. Just to highlight the problem, here is a naive approach to listing the Fibonacci numbers:

class FibonacciLong {
	static long solutions = 0;

	public static void main(String[] args) {
		long num1 = 0;
		long num2 = 1;
		long tmp;
		solution(num1);
		solution(num2);
		while(true) {
			tmp = num1 + num2;
			solution(tmp);
			num1 = num2;
			num2 = tmp;
		}
	}

	static void solution(long number) {
		solutions++;
		System.out.println(solutions + "t" + number);
	}
}

The output of this program overflows after the 93^rd term. Java only uses signed integer types, so we end up with a negative number:

1	0
2	1
3	1
4	2
5	3
6	5
....
92	4660046610375530309
93	7540113804746346429
94	-6246583658587674878

To find larger values, we can use the BigInteger class, under java.math. They are constructed like this:

BigInteger num1 = new BigInteger("0");

They don’t really work like the primitive types. They are manipulated with methods like .add() and .subtract(), rather than the operators that we are accustomed to: + - * / %.

The below code has been written with BigInteger instead of long. It will return the n^th term of the Fibonacci sequence, or enumerate solutions until the cows come home.

import java.math.BigInteger;

class FibonacciBigInteger {
	static long solutions = 0;
	static long find = 0;

	public static void main(String[] args) {
		if(args.length >= 1) {
			find = Long.parseLong(args[0]);
		}
		BigInteger num1 = new BigInteger("0");
		BigInteger num2 = new BigInteger("1");
		BigInteger tmp;
		solution(num1);
		solution(num2);

		while(true) {
			tmp = num1.add(num2);
			solution(tmp);
			num1 = num2;
			num2 = tmp;
		}
	}

	static void solution(BigInteger number) {
		solutions++;
		if(find == 0 || solutions == find) {
			System.out.println(number.toString());
			if(find != 0) { System.exit(0); }
		}
	}
}

The good news is that this program is now capable of working with numbers too large to say aloud. So today is a good day to start using Unix’s wc program to appreciate how big these numbers actually are:

mike~$ java FibonacciBigInteger 420000 | wc -m
87776

Subtract one character because there is an end-of-line in the output— and this means that the 420,000^th Fibonacci number is 8775 digits long. We have discovered a new fact!

Note: There is still one variable in the program above that will overflow eventually, so you should also convert that to a BigInteger if you are hoping to calculate past about the nine quintillionth Fibonacci number (which you would be crazy to do with this method).

Related