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 won’t be big enough. Just to highlight the problem, here is a naive approach to listing the Fibonacci numbers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
 2
 3
 4
 5
 6
 7
 8
 9
10


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:

1

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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:

1
2


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).