All I have for this one is the code I used...
#include <stdlib.h>
#include <iostream>
#include <time.h>
int fib(int n) {
if(n <= 2) return 1;
else return fib(n - 1) + fib(n - 2);
}
int fastfib(int n) {
int last = 1;
int here = 1;
int next;
while(n >= 3) {
next = last + here;
last = here;
here = next;
n = n - 1;
}
return here;
}
int main(int argc, char **argv) {
int parm = 40; // which Fibonacci to compute
int runslow = 2; // # trials for recursive algorithm
int runfast = 100000; // # trials for dynamic programming algorithm
clock_t start;
int last, j;
last = fastfib(parm);
cout << "answer: " << last << endl;
start = clock();
for(j = 0; j < runslow; j++) {
if(fib(parm) != last) {
cout << "error" << endl;
}
}
cout << "recur: "
<< ((double) (clock() - start) / CLOCKS_PER_SEC / runslow)
<< endl;
start = clock();
for(j = 0; j < runfast; j++) {
if(fastfib(parm) != last) {
cout << "error" << endl;
}
}
cout << "dynpn: "
<< ((double) (clock() - start) / CLOCKS_PER_SEC / runfast)
<< endl;
return 0;
}