Differences

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

Link to this comparison view

cs-142:fibonacci [2014/10/02 15:18] (current)
kseppi created
Line 1: Line 1:
 +<code cpp> 
 +#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; 
 +  
 +
 +</​code>​
cs-142/fibonacci.txt · Last modified: 2014/10/02 15:18 by kseppi
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0