Home
Question: Write a function that computes the list of the first 100 Fibonacci numbers.
Related Tags:
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.
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);
}
}
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);
}
}
Came up with a better solution or have a question? Comment below!
Next Challenge: Project Euler Problem 27: Quadratic Primes