#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)
{
// 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!
//cout << "using" << x << " " << answer << endl;
}
else
{
// go figure it out!
if (x > 2)
{
}

//save it for next time:
if (x < MAXFIB)
{
}
}

}

// 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;

} 