The comment thread in this post has over 30 entries now! Something that did come up in those discussions is why not cache the Dijkstra recursion so it goes really fast, and how does that compare to the F(a+b) calculator.
For a fixed F(k), it seemed that caching Dijkstra made it run faster than F(a+b), even when F(a+b) was allowed to cache everything. So, to determine whether this is true in general, I did a random F(k) test.
The task is to calculate F(k) Fibonacci numbers with k in this array, and in the order shown:
#(1702587 1848601 135328 1144978 183508 1421520 734333 200747 1750499 1795081 307556 1726299 1911101 1997485 521440 1954962 979243 1793538 1633868 323412 1866722 612481 1155724 441908 1135563 1338921 815458 520627 873849 432030)
These numbers, between 0 and 2049151, were devised using the MinimumStandardRandom (Park-Miller) RNG in VW 7.4.1. So here we go. The first run time numbers are:
- Non cached Dijkstra: 191.4 seconds.
- Cached Dijkstra: 162.5 seconds.
- Cached F(a+b): 158.2 seconds.
- Cached and Greedy F(a+b): 156.2 seconds.
- Cached F(a+b): 148.2 seconds.
At this point, it may be useful to examine how many entries the cached calculators have in their caches.
- Cached Dijkstra: 1116 entries.
- Cached and Greedy F(a+b): 1117 entries.
- Cached F(a+b): 107 entries.
As such I'd be inclined to say that, for general F(k) calculation use, the cached F(a+b) is a good first choice.
Update: I also tried Hakmem item #12, but it seems considerably slower than F(a+b) and Dijkstra's method.