24.9.10

Fibonacci

Calculating the n-th Fibonacci in different ways:

// Recursive
function fib(n){
  if (n < 2) return n;
  return fib(n-1) + fib(n-2);
}

// Memoized
function memFib(n){
  return memFib[n] || (memFib[n] = fib(n));
}

// Mathematical
function mathFib(n){
  return Math.floor(Math.pow(Phi, n)/Math.sqrt(5) +.5);
}
How do they compare in speed?
[fib, memFib, mathFib].map(function(fn){
  var t0 = +new Date
  fn(30);
  return +new Date - t0
});
Don't get your panties in a bunch just yet. This is an unfair fight:
  1. fib is simply horrible, performance-wise. It's the easiest to understand and best for demonstrating recursive functions, but that's it.

  2. memFib is a great example for memoization, as it executes almost linearly, except for those numbers which have not been used yet. If you try running memFib with n=40, you will start feeling the pain, but only the first time.

    An important point to make here about memoization is, if your function will be called many times and always returns the same result given the same arguments, memoizing is your friend.

We will approach browser recursion limits quickly, so I will add two more contenders:
// Y-combinator
var Yfib = Y(function(fn){ return (function(n){
  if (n < 2) return n;
  return fn(n-1) + fn(n-2);
}); });

// Memoized Y-combinator
var YmemFib = Ymem(function(fn){ return (function(n){
  if (n < 2) return n;
  return fn(n-1) + fn(n-2);
}); });
This is a whole different game, with n=1000:
[mathFib, YmemFib].map(function(fn){
  var t0 = +new Date
  fn(1000);
  return +new Date - t0
});
Firefox 3.6.10 cries somewhere between n=1000 and n=2000 about too much recursion, and the difference is less than 10 milliseconds in favor of the mathematical formula.
Chrome 6.0.472.63 can handle at least n=6000 before exhausting its stack and has a difference of about 2 milliseconds. BOOM.

The Much Anticipated Morale Of The Leonardo Of Pisa Thingamajigs

  1. Go for the mathematical solution first. If you are not smart enough, ask Google. If Google is not smart enough, ask Tyler. Seriously.

  2. Memoize. Remember this. Get it?

  3. Use a Y-combinator. You don't have to understand how to use it, and good luck trying. Seriously. Here you go:
    function Y(fn) {
      return function(x) {
        return (fn(function(n){
         return (Y(fn))(n);
        }))(x);
      };
    }
    
    To help you understand, try: matt.might.net, fixed point combinator on Wikipedia, Electronics and Computing Systems at the University of Cincinnati, the book To Mock a Mockingbird, and/or some entheogens.

The short answer: wrap this equivalent of bacon around everything.
/**
 * Memoizing Y-combinator (aka triptonomikon).
 */
function Ymem(fn) {
  var mem = this;
  return function(x) {
    return mem[x] || (mem[x] = (fn(function(n){
     return (Ymem.call(mem, fn))(n);
    }))(x));
  };
}

This should keep you busy until the next post.

6 comments:

Autodidactic Asphyxiation said...

To Mock a Mockingbird is awesome, but you can't mention Javascript Y-combinators without mentioning Crock's Little Javascripter:

http://www.crockford.com/javascript/little.html

How does iterative compare with recursive? Also, how does the "miss" case for memoization compare to the recursive? I would guess that it would still be faster, since it converts double recursion to single recursion. You would save stack space to do it iteratively.

My guess is that you'll have a non-toy example for combinators, though, which is exciting.

brito said...

Ah yes, I did forget Crockford's Little Javascripter.

In an attempt to answer your iterative vs. recursive question, I found this page

Indeed, iteratively is much, much faster than recursively. What you mention about stack space is also what I suspect the reason for why Yfib is much faster.

Given that browsers are implementing optimization on their side, it's a bit more difficult to analyze the algorithms on javascript. For example, Chrome would handle n=8000 if I first run n=6000 on a cold start, non-memoized run

You guess correctly, I am working on an application for combinators, as part of a tiny, asynchronous framework.

Do you have any applications in mind?

Autodidactic Asphyxiation said...

Well, function calls are just way more expensive in JS with current JITs, so it might not be the stack per se, but the correlation between large stacks and recursive calls. Actually, TraceMonkey probably could handle this case the best if it traced recurisve calls (I'd guess it doesn't for now).

I don't really do much in JS-land anymore, so I don't really have any ideas for such aync frameworks. Actually, I don't think I really like much of either async or frameworks since I dislike the hollywood protocol (don't call us, we'll call you). I know I'm in the minority in the JS world, especially with JS-based server frameworks gaining some popularity.

I wonder what could be done with WebWorkers, as an alternative.

Anonymous said...

The implementation of Y-Combinator in your post is not in "closed form" because it remains recursive itself.

brito said...

@Anonymous, could you explain a bit the issue with "closed form"?

Anonymous said...

It recursively calls itself while trying to avoid recursion of the Fibonacci function. For instance, non recursive example would be:

var Y = function(f) {
return function(g){
return g(g);
}(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
};