#include <iostream>
#include <math.h>
#include <ctime>
 
using namespace std;
 
// This is a place for the memoizer to remember stuff in
// unknown fibs are maked with a 0, normally this is bad, but ok here because
// 0 is not a valid value for a fib!
const int MAXFIB = 200;
long long fibs[MAXFIB];
 
// This version of fibonacci number computation is based
//   on the recursive definition of a fibonacci number
//
// Note that all of these examples use "long long" instead of
// "int". A long long holds a really big integer.
long long fib_recursive(int x) {
	long long ans = 1;
	if (x > 2) {
		ans = fib_recursive(x-1)+fib_recursive(x-2);
	}
	return ans;
}
 
// This version is recursive but remembers values as it goes; a "memoizer"
// this makes a big difference!
long long fib_remember(int x) 
{
	long long answer;
	// a good idea in any case, but even better with array
	if (x < 1)
	{
		cout << "There is no such fib!!" << endl;
		return 0;
	}
	if ((x < MAXFIB) && (fibs[x] != 0))
	{
		// I remember!
		answer = fibs[x];
		//cout << "using" << x << " " << answer << endl;
	}
	else
	{
		// go figure it out!
		answer = 1;
		if (x > 2)
		{
			answer = fib_remember(x-2)+fib_remember(x-1);
		}
 
		//save it for next time:
		if (x < MAXFIB)
		{
			fibs[x] = answer;
		}
	}
 
	return answer;
}
 
// This version uses a loop
long long fib_loop(int x) {
	long long ans = 1;
	if (x > 2) {
		long long ultimate_fib = 1;
		long long penultimate_fib = 1;
		for (int i = 2; i < x; i++) {
			ans = ultimate_fib + penultimate_fib;
			penultimate_fib = ultimate_fib;
			ultimate_fib = ans;
		}
	}
	return ans;
}
 
 
// Math to the rescue: This version just uses a formula!
long long fib_formula(int x) {
	double Phi = 1.61803398874989484820458683436563811772030917980576;
	double phi = 1/Phi;
	double sqrt5 = sqrt(5.0);
 
	long long ans = (long long) floor(((pow(Phi,x)-pow(-phi,x))/sqrt5)+.5);
	return ans;
}
 
int main() {
	long long temp; // temp to seperate out io time
	// set up fibs for memoizer
	for (int i = 0; i < MAXFIB; i++)
	{
		fibs[i]=0;
	}
 
	int n = 80; // if you use 80 there are not enough floating point digits
	// to do the math right so it starts to dissagree with the loop and recursive versions.
	// do not try to do this with the recursive version!
	n = 70; // impressive! still do not do this with the recursive version
	n = 103; // memo and loop work, formula overflows
	n = 104; // everyone overflows
	n = 40; // the recursive version works in a few seconds
	clock_t start;
	double elapsed;
 
	// slow, don't wait forever!
	if (n <= 40)
	{
			cout << endl << "Compute by RECURSION" <<endl;
			start = clock();
			temp = fib_recursive(n);
			elapsed = (clock() - start ) / (double)CLOCKS_PER_SEC;
			cout << "The " <<n<< "th fibonacci number is " << temp << endl;
			cout<< "computation Time: "<< elapsed <<'\n';
	}
 
	cout << endl << "Compute by RECURSION with memoization" <<endl;
	start = clock();
	temp = fib_remember(n);
	elapsed = (clock() - start ) / (double)CLOCKS_PER_SEC;
	cout << "The " <<n<< "th fibonacci number is " << temp << endl;
	cout<< "computation Time: "<< elapsed <<'\n';
 
	cout << endl << "Compute by LOOP" <<endl;
	start = clock();
	temp = fib_loop(n);
	elapsed = (clock() - start ) / (double)CLOCKS_PER_SEC;
	cout << "The " <<n<< "th fibonacci number is " << temp << endl;
	cout<< "computation Time: "<< elapsed <<'\n';
 
	cout << endl << "Compute by FORMULA" <<endl;
	start = clock();
	temp = fib_formula(n);
	elapsed = (clock() - start ) / (double)CLOCKS_PER_SEC;
	cout << "The " <<n<< "th fibonacci number is " << temp << endl;
	cout<< "computation Time: "<< elapsed <<'\n';
 
 
	system("pause");
	return 0;
 
}

Back to top