5 ms·
Why do people think that computing Fibonacci numbers recursively is a good benchmark of anything? Doesn't it require O(n^2) function calls for something that c
by carlob 14y ago
Why do people think that computing Fibonacci numbers recursively is a good benchmark of anything?
Doesn't it require O(n^2) function calls for something that can be computed in O(1)?
- lukev 14y agoActually 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.
- baddox 14y agoAlso, 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.
- Jabbles 14y agoIt 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).
- kragen 14y agoIf the compiler deals with arithmetic in a very inefficient way, that will also show up.
- codeflo 14y agoNote to self: If I ever implement a compiler, I'll include a special Fibonacci detection pass in the optimizer.
- mjn 14y agoThat 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.
- spitfire 14y agoBoth 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.
- lliiffee 14y agoActually, it takes real effort to make GCC not completely optimize-away this kind of stuff for C: https://github.com/JuliaLang/julia/issues/1325 https://github.com/JuliaLang/julia/issues/1325
- smosher 14y agoThere's a simple solution to that: use Ackermann instead. It measures the same thing and is a function of its own time complexity to boot.
- jules 14y agoIt actually requires O(fib(n)) function calls, or equivalently about O(1.62^n) function calls.
- mikeash 14y agoFibonacci 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.
- carlob 14y agoCan't you do it in O(1) if you limit yourself to floats? Arbitrary n but not arbitrary precision?
- mikeash 14y agoI imagine the table would still be of reasonable size then. Of course, this is still technically restricting the output to 32 or 64-bit numbers.
- gamegoblin 14y agoNo 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. http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
- kragen 14y agoThere'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.
- StefanKarpinski 14y agoYou 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: cfib(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5)) Let's see how it works: julia> cfib(1) 1.0 julia> cfib(2) 1.0 julia> cfib(3) 2.0 Great! But let's look at a few more: julia> cfib(4) 3.0000000000000004 julia> cfib(5) 5.000000000000001 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.
- dagw 14y agoFibonacci numbers cannot be computed in O(1), only estimated. All closed form algorithms start giving imprecise answers after some value of n.