Fibonacci Numbers in C/C++
Here’s another demonstration on how slow recursive functions are. I wrote three functions in C++ that calculates Fibonacci numbers in integer type. Since my computer only supports 32bit integers, I calculated up to the forty-second Fibonacci number, which is 26,7914,296.
Implementations #
Our first function uses a recursive definition:
int f1( int n ) {
if (n < 1)
return f1(n-1)+f1(n-2);
else if (n == 1)
return 1;
else
return 0;
}
The second function uses the closed form of the Fibonacci number. Although fast, this function doesn’t necessarily give you the right answer due to rounding errors:
int f2( int n ) {
double sqrt5 = sqrt((double)5);
return (pow((1 + sqrt5) / 2,n) - pow((1 - sqrt5) / 2,n)) / sqrt5;
}
And finally, the third function uses simple addition:
int f3( int n ) {
int v_prev = 1;
int v_beforeprev = 0;
int v = 1;
if (n == 0)
return 0;
while (--n) {
v = v_prev + v_beforeprev;
v_beforeprev = v_prev;
v_prev = v;
}
return v;
}
Performance Comparisons #
I first measured the time each function took to calculate Fibonacci numbers from 0 to 42. Note that all results reported here are obtained on a machine with an AMD Athlon 64 processor. The results show that you should never use the recursive version:
function | 1st trial (ms) | 2nd trial (ms) | 3rd trial (ms) | Average (ms) |
---|---|---|---|---|
f1 | 73497 | 74589 | 76209 | 74765 |
f2 | 0 | 0 | 0 | 0 |
f3 | 0 | 0 | 0 | 0 |
If thought I made some mistake in my program and didn't really execute f2 and f3 functions properly, take a look at the followings results, in which f2 and f3 did the same calculation 1 million times:
function | 1st trial (ms) | 2nd trial (ms) | 3rd trial (ms) | Average (ms) |
---|---|---|---|---|
f2 | 24918 | 24587 | 25625 | 25043 |
f3 | 9053 | 8894 | 9160 | 9036 |
These results imply that f2 is
Note that f2 is much faster in calculating a very large Fibonacci numbers such as 100th Fibonacci number although it is nonsensical to use any one of functions written above since each function converts the results into a 32-bit integer. Nevertheless, this tiny experiment indicates how reckless use of recursion could go wrong.