Breaking it down with algorithms II: Fibonacci

This series of posts is designed to not only explain how some algorithms work but also how you can think about problems to come up with your own algorithms.

the Fibonacci series is used in teaching Computer Science as it translates well in to a recursive solution - even if the solution is not ideal. The Fibonacci series starts with a 0 and 1, then each following number is worked out by taking the sum of the two previous numbers. This gives us the formula of:

Fib(n) = Fib(n-1) + Fib(n-2)

The reason it's used is because that's already a recursive function and looks something like this:

To look at performance of below solutions you can check out: http://jsperf.com/fibonacci-y-combinator/5

The Recursive Solution:

var Fib = function(n) {
  if (n <= 1)
    return n;
  return Fib(n-1) + Fib(n-2);
}

We can see that if given a formula we can write it out almost as we were give - with the exception of adding in the base conditions. We do have to be careful though as this will duplicate our work, we can see this by putting Fib(n-1) = Fib(n-2) + Fib(n-3) in to our original formula:

Fib(n) = Fib(n-1) + Fib(n-2)
Fib(n) = Fib(n-2) + Fib(n-3) + Fib(n-2)

As you can see we are doing Fib(n-2) more than once, and as we recurse through we will have a lot more duplication of effort. To fix this we instead will memoize our answers so instead of calling back through the recursive chain we will cache answers and return them when we get them back. We can make a general memoize function like so:

var memoize = function(fn) {
  var cache = {};
  return function(arg) {
    if (arg in cache) return cache[arg];
    cache[arg] = fn(arg);
    return cache[arg];
  };
}

So if we do this:

FibMem = memoize(Fib);

We should see a large performance gain. But this basically only puts us on a par with a linear algorithm and we are keeping all of the answers in memory. The great thing about it though is that if we want to work out different numbers several times, at least some of the work will be done for us. However if we want to print out the series of Fibonacci numbers instead of the nth one, then a linear equation should be better.

The Linear Equation

var Fib = function(n) {
var a = 0;
var b = 1;
for(var i = 0; i < n; i++) {
  var temp = b;
  b = a + b;
  a = temp;
}
return a;
}

And this is a good first attempt. For each loop we move along one until we get our answer. This is a pretty easy one to get so I'm going to move on to an optimization that I haven't seen a lot:

The Fast Loop

var Fib = function(n) {
var half = Math.floor((n-1)/2);
for(var i = 0, a = 0, b = 1; i < half; i++,b+=(a+=b)) {}
return n%2==0 ? b : a;
}

or perhaps in a more readable form:

var Fib = function(n) {
var a = 0;
var b = 1;
for(var i = 0; i < n - 2; i += 2) {
  a = a + b;
  b = b + a;
}
if (n % 2)
  return a;
return b;
}

Now first off passing in 0 will give you the wrong number, but we'll ignore that for now. What we've done is change the loop to go two numbers at a time rather than one. Because we do this we can eliminate the need for a temporary variable and we're only doing two assignments to go up two spots rather than three assignments to go up one. If we used destructuring assignment we could change our original algorithm to work without a temporary variable, but because it's not in all versions of javascript it's unlikely you would consider using it as yet (though for those interested it would be [a, b] = [b, a+b]).

The trick with this is to see that once we did a = a + b then we could just do b = b + a to return our a and b to be the smaller and larger numbers respectively. So when you are looping through a series looks for shortcuts, can you calculate more than one variable at a time? if you're going through numbers can you use arithmetic instead of saving a temporary variable?

Divide and Conquer

This is interesting as we've been taught that divide and conquer methods are really good, and that's usually true. The one problem with what I'll show you is that the individual steps are so heavy that for most numbers you'll be calculating up to, it's just not worth it but the higher the number you're calculating the faster it will be and should eventually be faster than the other methods. To do this method we first of all have to know some math.

There is something called the Fibonacci matrix. this matrix will give us the Fibonacci number for N if we multiply itself N times.:

[1, 1] ^ N
[1, 0]

Then it's just a simple matter of using the divide and conquer for powers. The complexity for this algorithm comes in the matrix multiplication and the algorithm goes a little something like this:

//to find the nth number
//fibonacci identity
Fib = [1,1,1,0]
//multiply a 2x2 Matrix
function mult2x2(a,b){
 return(
  [ a[0]*b[0]+a[1]*b[2], a[0]*b[1]+a[1]*b[3],
    a[2]*b[0]+a[3]*b[2], a[2]*b[1]+a[3]*b[3]
  ]
 );
}
function fibRecurse(M,n){
  //if n is one return the identity
  if(n==1)
    return M;
  //get the value of fib^n/2 (divide)
  var fibSoFar = fibRecurse(M,Math.floor(n/2));
  //multiply the two halves (and multiply by 1 more if not an even number) (conquer)
  fibSoFar = mult2x2(fibSoFar,fibSoFar);
  if(n%2==1)
    fibSoFar = mult2x2(fibSoFar,Fib);
  return fibSoFar;
}

Which is far more complicated but will get faster compared to the other algorithms the higher the number.

Conclusion

There are a few other algorithms I won't go through, like the direct formula as it's not as interesting to disect how it works (at least for the purpose of trying to solve a problem) and the Y combinator as it's not generally useful in javascript. I hope that the above has made you think past the usual fibonacci solutions and things like the fast loop method above should make you think about algorithms you were taught and whether or not they are the best method. The more you think about old problems the more likely you will come to new solutions rather than just relying on a memorized method.