Fast Fibonacci

16 April 2012

If you’re not aware,or need a refresher… What’s a fibonacci number?

Usually a question asked in interviews to prompt the responder to talk about recursion and show how they would implement it like that fib(n) = fib(n - 1) + fib(n - 2). In short it’s not the best solution (hint: performance)… and that’s all i’m going to say about that.

The Solution

Solving fibonacci has been done to death. I’m sure somebody else has already written up a similar solution, maybe even verbatim… either way, the following is based on what’s in my mind hole and i just wanted to put it out there.

var fib = (function () {
    var  cache = [0,1];
    return function (n) {
        var i = cache.length, 
            il = n + 1;
        for (; i < il; i += 1) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
        return cache[n];
    }
}());

You did what now?

  • Run an anonymous function

    • It creates a closure for cache and initialises the array to [0,1] (the first 2 values of fibonacci).
    • It then returns a function, which becomes fib. The cache of fibonacci values can be accessed in the returned function.
  • When we call fib(n)

    • It cycles through the loop starting at the length of the cache array until it’s reached, but not evaluated n + 1.
    • It then returns the nth number from cache.

What makes this good?

  • The calculation is linear. Using an array to calculate the current value based on the sum of the previous 2 values, the performance is linear (it takes as long as one for loop takes to get to n).
  • It “learns” by storing the calculated values in cache which is accessible every time you call fib with any value. Which means you’ll get a performance increase the more times you run it. ie. If you’ve already run fib(10) and then you run fib(6) it won’t run the for loop at all, and will just return the value of cache[6]

Here are it’s negatives, (from what i can see)

  • The anonymous function is always run, even if you don’t use fib(n)
  • cache could become a large array and wont ever get garbage collected (unless you destroy fib, fib = null). Pretty negligible in my mind, as the setup cost is almost none and the size of the array will hardly have an affect on modern day machines.

Matt Sain

Ramblings of a developer, designer and child subscribe

This blog is a public GitHub repository. If you find an error I will not be surprised... but if you fork and edit the blog and send me a pull request you'd be pretty awesome in my book.

Featured Repos