# First 100 of Fibonacci

Question: Write a function that computes the list of the first 100 Fibonacci numbers.

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 232Integer.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(2n) 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) {

fib(100);

for (BigInteger n : fib100) {
System.out.println(n);
}
}

static BigInteger fib(int n) {

if (n >= fib100.size()) {
}

return fib100.get(n);

}

}``````

## Sources

Upper bound to a BigInteger

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

Next Challenge: