Now we've seen a slow way to generate the fibonacci numbers, and we've seen why its so slow, now we'll try to do better. Here's my proposed improvement to our recursive function that we made the first day:
static long Fibo(long n)
{
//
// check the base cases
//
if (n <= 1)
return 0;
if (n == 2)
return 1;
//
// initialize our array of fibonacci numbers
//
long[] numbers = new long[n];
numbers[0] = 0;
numbers[1] = 1;
//
// calculate the 2nd through nth
// fibonacci numbers in the array
//
for (long i = 2; i < n; i++)
{
numbers[i] = numbers[i - 1] + numbers[i - 2];
}
return numbers[n - 1];
}
So what we're doing here is that instead of making recursive calls to the Fibo function, we are just storing the fibonacci numbers in an array of length n. We don't have the recursion tree at all now, as there are no recursive calls. All we have is the overhead of the array, and a loop that will loop n times. During each loop interation, we simply add the two previous numbers in the array, and put the result in the current array position. Using this function we can easily get the 50th, 100th, or 1000000th fibonacci number, no problem. Go ahead, try it! The response is nearly immediate! However, there is one more little thing we can change to make the function even better.
In the code above, we maintain an array of the 0 to nth fibonacci numbers, when really, all we need is the current number, and the previous number, in order to generate the next one. So we can remove the overhead costs that are associated with the array:
static long Fibo(long n)
{
//
// check the base cases
//
if (n <= 1)
return 0;
if (n == 2)
return 1;
//
// initialize our loop varibles
//
long x = 0;
long y = 1;
long current = 0;
//
// calculate the 2nd through nth
// fibonacci numbers, but without
// the array overheard
//
for (long i = 2; i < n; i++)
{
current = x + y;
x = y;
y = current;
}
return current;
}
Here, instead of an array of length n, we simply have x, y, and current. We still have the loop that will iterate n times, but each time the loop adds x and y and then puts the value of y into x, and the new value into y. We can store all the values we need in just three variables!
I ran some tests and compared the results of the 3 different functions, heres what I found:
| | 10 | 20 | 30 | 40 | 50 |
| Slow | 125000 | 62500 | 312500 | 37484375 | 4.18E+09 |
| Better | 140625 | 78125 | 31250 | 31250 | 0 |
| Best | 93750 | 109375 | 46875 | 78125 | 0 |
So you can see that the difference in the functions is trivial when finding the 10th or 20th fibonacci number. However, the difference becomes very noticeable when generating the 40th number, and once we get to the 50th, the difference is staggering. I went and ate dinner while the slow function was processing the 50th number! The numbers provided are the number of "ticks" the functions took. I ran each function 10 times for each value. The difference between the faster two functions is negligible, as the only optimization we used there was to reduce the amount of memory needed, not processing time. These results clearly show how much slower tree recursion can be than an iterative function.
Thanks for reading, I hope you've enjoyed the series!