Saturday, 27 March 2010

practicing with fibonacci

It's Saturday morning, I'm slightly hungover and my wife has gone out shopping with her friend (and my credit card!). What else am I going to do except practice some coding?

I was reading a few academic sources and a lot of them mention Fibonacci sequence and I thought to myself, you know, I've never coded that (I mean, why would I?).

First up, I created a small test harness:

int sequence[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 };


for (int i = 0; i < style="color: #2600c9">length; i++) {

assertEquals("fail " + i, sequence[i], fib(i));

}


And then I knocked out an iterative function in virtually no time:

public long fib(int n) {


if (n < 0) {

throw new IllegalArgumentException(

"Negative numbers are not supported");

}


if (n < 2) {

return 0;

}


long result = 0;

long first = 0;

long second = 1;

for (int i = 0; i < n - 1; i++) {

result = first + second;

first = second;

second = result;

}


return result;

}

It works, and it's fast, I went back to reading.

After a while I found another example of the Fibonacci algorithm:

static long fib(int n) {
return n <= 1 ? n : fib(n-1) + fib(n-2);
}

Oh! Recursion - damn it, of course, it's obvious, but wait ... throw in a big number there and what's going to happen? Well assuming you don't run out of memory (the stack frame should be quite small anyway), that's going to be slow...

For every number up to n where n is greater than 2, it looks like that function gets called 2 * (2 ^ n) times, i.e. O(2^n) - so assuming i throw in 50 that's 2 ^ 50 operations ... i.e. a lot.

Note: Further reading reveals that function actually has a complexity of O(2^0.7n) though I don't know how they worked that out. If anyone can enlighten me, I'd appreciate it as I haven't done this stuff in anger for several years now.

I wrote two more tests in my test harness to see the difference in time and threw in 50. The iterative one always finishes almost instantly - you can see by looking at it that it will run in O(n) time, the recursive one takes around 90 seconds on this computer.

The next problem I encountered was testing with larger numbers - I soon started seeing negative results as the maximum value of long was exceeded and automatically wrapped around. For instance, throwing in 200 yields -1123705814761610347 which isn't much use.

Thankfully Java has something called "BigInteger", which, as the name suggests, lets you use Big numbers. I modified the method to use the BigInteger class as follows:

public BigInteger fibIterative(int n) {


if (n < 0) {

throw new IllegalArgumentException(

"Negative numbers are not supported");

}


if (n < 2) {

return new BigInteger(String.valueOf(n));

}


BigInteger result = null;

BigInteger first = new BigInteger("0");

BigInteger second = new BigInteger("1");

for (int i = 0; i < n - 1; i++) {

result = first.add(second);

first = second;

second = result;

}


return result;

}


Throwing in 200 to that method yields 280571172992510140037611932413038677189525 which looks better, though I will have to take it on faith that it is correct.

No comments: