Large Fibonacci Numbers in Java

The Fibonacci Sequence is a series of numbers that increases at a highly exponential rate. Implementing a Fibonacci algorithm is a classic computer science programming exercise as it touches on many important concepts. The standard implementation involves a recursive function and looks something like this:
static int fib(int n) {
return n <= 2 ? 1 : fib(n-1) + fib(n-2);
}
Whilst this works and is all very exciting at first, the implementation introduces two classic programming errors:
  1. Integer Overflow: The Fibonacci sequence expands rapidly and will quickly throw an integer overflow error if trying to compute for numbers greater than 46 (i.e. fib(47) will throw an error or cause an overflow).
  2. Recursive Blowout: Notice that for numbers greater than two, each function call makes two recursive calls. This leads to an exponential number of recursive function calls which will cause a stack overflow for large numbers (this depends on the execution environment).
In Java, the first problem can be improved by first using a long instead of an int which will increase the overflow limit. The real solution however is to use the BigInteger class which handles arbitrarily large numbers.

The second problem requires a bit more though. Notice that the standard recursive implementation is performing a lot of unnecessary work. Computing fib(50) will first compute fib(49) + fib(48). Computing fib(51) will compute fib(50) + fib(49)...but we already calculated those values once, why should we do it again? One solution would be to cache the answers into a global list or array such as:

static BigInteger fib(long num) {
return new Object() {
private Map cache = new HashMap();
public BigInteger computeFib(long k) {
for(long i = 0; i <= k; i++) cache.put(i, fib(i));
return (BigInteger)cache.get(k);
}
public BigInteger fib(long k) {
if(k == 0) return new BigInteger("0");
else if(k <= 2) return new BigInteger("1");
else return ((BigInteger)cache.get(k-1)).add((BigInteger)cache.get(k-2));
}
}.computeFib(num);
}

This will let you compute the Fibonacci sequence for any number less then Long.MAX_VALUE. The function is bound only by the memory heap-space available to the Java JVM, i.e. the more RAM, the bigger the Fibonacci sequence you can compute. Setting -Xmx1024m on my 2GB 1.2GHz laptop, fib(150000) computes in ~8 seconds and results in this 31348 digit long answer.

The implementation however is still flawed. We are now storing the whole Fibonacci sequence in a Map in memory. There's no real reason why we need to do this if all we're interested in is the final result. Instead of storying everything in memory, all we really need to compute the next number is the last two numbers. A revised solution may look as follows (note that this will also account for negative inputs):
static BigInteger fib(long k) {
BigInteger answer = null;
boolean negative = k < 0;
if(k == 0) answer = new BigInteger("0");
else if(Math.abs(k) <= 2) answer = new BigInteger("1");
else {
BigInteger k_minus_one = new BigInteger("1");
BigInteger k_minus_two = new BigInteger("1");
for(int i = 3; i <= Math.abs(k); i++) {
answer = k_minus_one.add(k_minus_two);
k_minus_two = k_minus_one;
k_minus_one = answer;
}
}
return negative ? answer.multiply(new BigInteger("-1")) : answer;
}

This computes fib(150000) in ~4 seconds, but we're now no longer memory bound by the large array/map. We can now compute the sequence until the BigInteger number overflows the heap. The Fibonacci sequence of 1 million is 208988 digits long and took just under 3 minutes to compute on my laptop.

Can this be improved upon even more? Hmm, maybe if you multi-thread the computation to take advantage of multi-core CPUs, but I don't think that's mathematically possible as each operation depends on the result of the last so there's no way to run two additions in parallel. This is ironic as I started writing this function to compare the performance of a single-threaded vs. a multi-threaded algorithm on a dual-core machine...but it turns out the most efficient implementation is non-threadable :(

Comments

  1. Re "multi-threaded algorithm" ... have you tried computing vector (F[k+1], F[k]) from (F[k-1], F[k-2])? It implies using a matrix multiplication, which can be parallelised. You can do same trick with vectors of dimensions >=2 as well.

    ReplyDelete
  2. What about F(n) = floor( ( phi^n / sqrt(5) ) + 0.5), where phi = 1/2 + sqrt(5)/ 2 ???

    ReplyDelete

Post a Comment

Popular posts from this blog

Wkhtmltopdf font and sizing issues

Import Google Contacts to Nokia PC Suite

Can't delete last blank page from Word