Note: you may want to read the extensive comment chain as it has much more information than the original post.
So I went looking around to see what other people had done to calculate Fibonacci numbers exactly. I saw plenty of naive implementations (F(n) = F(n-1) + F(n-2)). Wikipedia has plenty of sample code, but none seemed interesting the first time I went through the page (although it does have valuable things, see below). Wolfram (Mathematica) didn't say much (or I missed it if it did). Then I run into this page, and Dijkstra's recursion:
- F(2n) = (2 F(n-1) + F(n)) * F(n)
- F(2n-1) = F(n-1)^2 + F(n)^2
As it turns out, Dijkstra's recursion is extremely fast. However, it is not as fast as the cached calculator can be. And in fact, the presence of the cache is the difference: by design, Dijkstra's recursion is difficult to cache because the indices that would be cached change with every F(k). On the other hand, by using F(a+b), one can choose which indices will be cached in advance, and therefore it is possible to use the same cache for all F(k).
Measurements show that F(15625) is calculated by the cached calculator about 2x faster than Dijkstra's method --- but only after the cache is filled. With F(390625), this advantage is reduced to a factor of about 1.4x.
How about F(1953125)? Dijkstra's method crunches this monster of a number, complete with its 408179 decimal digits, in 16.5 seconds. The cached calculator, after the cache is filled, does the same in 14.7 seconds. At first sight it appears that as the Fibonacci index increases, the methods become more and more similar. Maybe there is an asymptotical advantage towards Dijkstra's method (for example, multiplication is most efficient when squaring), although it's hard to tell at first sight.
Where the cached calculator does leave Dijkstra's recursion in the dust is when calculating F(k) mod: m. The caching proves too much, and F(15625) reveals a runtime difference of 12x.
Fun, isn't it? :)
PS1: at first I thought Wikipedia's alternate expressions for Dijkstra's recursion (under J, double recursion) would be faster, but measurements reveal that they are slightly slower than Dijkstra's original recursion.
PS2: unhappy with a couple things, I made a few changes to the cached calculator so its execution context is more aware of what is going on. This results is a speedup of a few percent compared to the code I posted earlier.