##### Differences

This shows you the differences between two versions of the page.

 — cs-142:fibonacci [2014/10/02 15:18] (current)kseppi created 2014/10/02 15:18 kseppi created 2014/10/02 15:18 kseppi created Line 1: Line 1: + + #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; + + } +
cs-142/fibonacci.txt · Last modified: 2014/10/02 15:18 by kseppi 