Actually being fast is not the point; naive fib is used because it's a very well known algorithm, easy to implement consistently across multiple languages, that heavily exercises both function calls and numeric addition.
In other words, as much as a 10-line program can be, it's a reasonable proxy for a language's performance on algorithmic code.
Also, it's a reasonable low bar to begin with for a college-educated programmer (not that all programmers need to be college-educated), because the Fibonacci sequence in mathematics (and in everyday language) is commonly defined in its recursive form, so it's likely that people will be familiar with it.
That kind of thing does happen when the stakes get high enough. There are a lot of rumors (and some evidence) of special-cased "cheating" on commonly used benchmarks, including the 3dMark GPU benchmarks, SPEC CPU benchmarks, even SunSpider JS benchmarks.
Both Nvidia and ATI have been caught cheating at graphics benchmarks. Their drivers would detect when the benchmark programs were being run, and go through lower quality fast paths. You can google "quack.exe" for details on one particularly famous case.
It tests how well the compiler deals with function calls, and that's it. Useless for measuring a language's overall speed (as are all micro-benchmarks).
Fibonacci is O(log n) or so in the best case, not quite O(1). Of course you can do a simple table lookup if you're limiting yourself to 32 or 64-bit numbers, but you can go far beyond that.
There's a formula from analysis that gives you the Nth Fibonacci number in closed form. It involves a couple of exponentials, which you can compute to a given accuracy in bounded time.
You obviously haven't tried doing this or you wouldn't suggest this as a way to actually compute Fibonacci numbers. Here's a definition in Julia (hey, why not) of a closed form Fibonnaci function:
Oops. Those aren't integers. I guess we could round, but at some point we might be rounding to the wrong integer. In fact, once you get up to 63, this happens and worse still, at 64 you get an infinite answer.
Here's a simple, reasonably efficient iterative Fibonacci function in Julia:
function ifib(n)
j, k = 1, 1
for l = 3:n
j, k = k, j+k
end
return k
end
We know this one works up to the limits of Int64 range:
julia> for n = 1:10
println(fib(n))
end
1
1
2
3
5
8
13
21
34
55
Using a doubly recursive algorithm for Fibonacci is indeed silly, but it's a good toy test of recursion performance.
But, although it gives close answers up to cfib(604) (after which it throws an exception) it still gives slightly inexact answers starting at 308061521170129 (cfib(71)), which is between 2⁴⁸ and 2⁴⁹. I'd expect it to make it a few items further before going astray, since it's presumably doing floating-point calculations with 53 bits of mantissa that are supposed to be rounded to less than half an ulp.
For exact answers, you clearly can't do better than O(N) (where N is the magnitude of the input parameter, not its length in bits) because the output is of size O(N). But for approximate answers, you can.
I agree about the uses for doubly recursive Fibonacci!
Unfortunately, this approximate value is off by 1066512995643 (~1 trillion), so it's hard to see how it would be useful. Actually, it's hard to think of good uses for computing Fibonacci numbers in general :-)
No need for a table lookup. There is a closed form formula. Of course this is only as accurate as your float precision. You can get out pretty far, though, with some clever rounding.
Doesn't it require O(n^2) function calls for something that can be computed in O(1)?