This posts combines the results of the last two posts. I thought it would be interesting to compare the actual run times of the three methods of calculating Fibonacci numbers so I put together a Babel table like the one in the Calling Babel From A Table post and ran the experiment. The results were a little disappointing because they didn’t really give me much information. The table below gives the times (in 100 Hz timer ticks) that the 3 methods took to calculate fibn for various values of n. (The code is the same as in the Calculating the Fibonacci Numbers post.)
| n | Recursive | Iterative | Logarithmic |
|---|---|---|---|
| 10 | 0 | 0 | 0 |
| 20 | 0 | 0 | 0 |
| 30 | 15 | 0 | 0 |
| 40 | 1899 | 0 | 0 |
| 50 | 234539 | 0 | 0 |
| 100 | Too Long | 0 | 0 |
| 1000 | Too Long | 0 | 0 |
| 10000 | Too Long | 1 | 0 |
| 100000 | Too Long | 40 | 0 |
| 1000000 | Too Long | 8952 | 5 |
As expected, the recursive method quickly becomes impractical, taking 39 minutes to calculate fib50. The iterative method doesn’t register any time at all until fib10000 and is still under half a second for fib100000. The time for the iterative method to calculate fib1000000 is misleading because the wall clock time was much longer. The reason for that was that it used up all the memory (4 Gigs) and spent a lot of time swapping. Presumably this was the result of the big nums representations taking up memory. Interestingly, I could watch the garbage collector at work. The free memory would get down to a few MB and then start to climb again. Then it would drop again. This happened several times.
The results for the logarithmic method don’t provide much information other than that if you want to calculate fibn for large n you should use that method.