To answer your (possible rhetorical) question literally, the requirement here isn’t that it generate Fibonacci numbers efficiently, it’s that it implement the recursive algorithm efficiently.

It’s true that another algorithm will be much faster, but that deprives us of the opportunity to discuss how this implementation of the recursive algorithm delivers much higher performance than a naïve implementation.

The back story is that an abrasive blog post asserted that Node.js was a terrible platform for certain types of problems, and this algorithm was given as an example. The author here is simply showing that with care, Node.js will not be the problem.

For shits and giggles, here’s another Fib algorithm, chosen strictly for the pleasure of implementing it:

https://github.com/raganwald/homoiconic/blob/master/2008-12-...

The specific point is that the evented model is not designed as a "one size fits all" solution. It's great for certain scenarios, not very good for certain others.

Basically, the original blog post tries to get to this, remarking on node.js is sold as if it was the silver bullet of web servers, that will scale to anything for anything you .

Of course, you can try to adapt most problems into something that would work in an evented model, but you have to know VERY WELL what you're doing.

IMO the solution is simple: polyglotism. Have parts of your app in node. Other parts in python. Others in ruby. Whatever works best for each specific small part :)

Node is not useless, but it's definitely not my choice to program everything and anything. Same thing with, for example, Rails :)

It’s tangential to this thread, but since it’s a topic close to my heart:

If you just implement this formula using doubles then it only gives the correct answer for input values up to about 70. Yes it’s pretty fast, but a static table of the first 70 Fibonacci numbers would be even faster. If you’re only interested in the first few dozen Fibonacci numbers then it doesn’t really matter what algorithm you use, as long as it isn’t naive recursion.

If you want to get correct answers for larger Fibonacci numbers, you need to work harder to use this equation. You need some sort of multiple-precision floating point arithmetic library, for example.

And once you’ve done that, the resulting algorithm is quite a lot slower than the best integer methods.

I wrote a big blog post about this back in July: http://bosker.wordpress.com/2011/07/27/computing-fibonacci-n...

That formula fails for fib(71) with double precision floating point arithmetic:

    In [1]: def fib(n):
       ...:     a,b = 0,1
       ...:     for i in range(0,n): a,b = b,a+b
       ...:     return a
       ...: 

    In [2]: def fib2(n):
       ...:     phi = (1+sqrt(5))/2
       ...:     return round(phi**n / sqrt(5))
       ...: 

    In [3]: fib2(71)
    Out[3]: 308061521170130.0

    In [4]: fib(71)
    Out[4]: 308061521170129L

And it's not that the latter is not exactly representable as a floating point number:

    In [5]: float(_)
    Out[5]: 308061521170129.0

So you'd have to use bigger precision numbers. How many digits are you going to use? You have to use enough not to produce a wrong result and not too many to slow down the algorithm. I bet that the resulting algorithm is slower than the standard [1 1; 1 0]^n matrix exponentiation. Note that your formula comes from the eigenvalue expansion of this matrix exponentiation, which -- despite what you might hear from undergraduate linear algebra courses -- is not a good method for matrix exponentiation. On the contrary, finding eigenvalues is done by a process analogous to matrix exponentiation: http://en.wikipedia.org/wiki/Power_iteration

Would be cheating, man. Micro-benchmarking is all about using fictitious tests to show off fake performance in blog posts.

Or, for that matter, using fictitious tests to show of fake lack-of-performance in blog posts.

Why would you want to use that formula? The doubling identities are faster and avoid floating-point arithmetic.

I just tried this:

    Math.round(Math.pow((1 + Math.sqrt(5))/2, n) / Math.sqrt(5))

But it starts returning incorrect results at fib(76), presumably due to floating point calculations lacking enough precision.

That's actually pretty good. Double precision floating point (IEEE format, anyway), can represent all positive integers up to 9007199254740990, which takes you up to Fib(78), so the fact that you can get up to Fib(76) means you are getting close to the top. Good enough for most work.

After 9007199254740990, double precision only represents even integers. Fib(79) is odd, so can't be represented. Fib(80) would be representable though, as will be every other Fibonacci number for a while. Then comes a range where only multiples of 4 can be represented, and then a range with multiple of 8, and so on, so while there will be representable Fibonacci numbers in those ranges, more and more will be omitted.

By using a field extension over √5, you can evaluate this exactly without rounding or resorting to floating point.

I think that's a very sharp observation. I tried it, but in order to exponentiate the vectors (instead of floating point numbers) I end up with the original matrix algorithm (pre-eigenvalues)...