First 100 of Fibonacci

Related Tags:

Use BigInteger

Java's int type is a 32-bit sized primitive type that has a maximum of 2,147,483,647. Since our fibonacci sequence values will be bigger than this, we have to use a BigInteger class. BigInteger is implemented using an int[], so the maximum is 2^{32Integer.MAX_VALUE}.

A naive approach

We could naively use a recursion method, but for each call that would branch out another 2 recursive calls. Effectively, this would have a O(2ⁿ) runtime.

static BigInteger fibSlow(int n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

Memoization

Thus, we need to store the already-calculated elements into a list, then retrieve it when needed. The process of storing and retrieving already-calculated values is termed memoization.

import java.util.ArrayList;
import java.math.BigInteger;

public class Fibonacci100 {

	static ArrayList<BigInteger> fib100 = new ArrayList<>();

	public static void main(String[] args) {

		fib100.add(BigInteger.ZERO);
		fib100.add(BigInteger.ONE);
		fib(100);
		
		for (BigInteger n : fib100) {
			System.out.println(n);
		}
	}

	static BigInteger fib(int n) {

		if (n >= fib100.size()) {
			fib100.add(n, fib(n-1).add(fib(n-2)));
		}

		return fib100.get(n);

	}

}

Sources

Came up with a better solution or have a question? Comment below!