Fun with Fibonacci

A snippet of code that is dear to my heart is Fibonacci. The problem can easily be solved recursively and iteratively, but you must have at least a solid understanding of programming to implement it. I ask it in almost every interview.

The other day I was watching a co-worker solve Fibonacci on CodeEval and decided to solve it myself. Here is the function I came up with...

ulong fibonacci(int index) {
   ulong[] numbers = { 0, 1 };
   for (int x = 2; x <= index; x++) {
      numbers[x % 2] = numbers[0] + numbers[1];
   }  
   return numbers[index % 2];
}

The first thing to note is that it is iterative, not recursive. A recursive implementation of Fibonacci is incredibly inefficient as the computer must traverse the tree twice for each index, growing exponentially as it calculates, and quickly overflowing the stack.

Next are those pesky variables. Note that I've used the ulong in my function, which has a range from 0 to 18,446,744,073,709,551,615. Pretty impressive number but since Fibonacci grows almost exponentially, it won't take long to overflow. Here are the indices that overflow common variable types:

int     46
uint    47
long    92
ulong   93

It's a surprising limitation considering such an easy problem.

A last item that I wanted to point out about my solution is that often I'll see people create variables with names like previous1, previous2 and keep changing values each time through the loop. While still much better than recursion, my simple array that holds the previous two index values by modding the index by 2 is a tiny bit cleaner and eliminates an extra swap.

I'd love to see other implementations of Fibonacci. This was a fun exercise and I hope to be able to add more in the near future!

comments powered by Disqus