446,234 Members | 1,889 Online Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

# Steve Summit C Notes {Anticipating the next one}

 P: n/a /* ** Direct computation of Fibonacci numbers. ** ** Input: index of Fibonacci number to compute (n) ** ** Returns: nth Fibonacci number. */ #include double fibonacci(unsigned n) { /* isf is 1/sqrt(5) */ static const double isf = 0.447213595499957939281834733746255247088123671922 31; /* gr is golden ratio */ static const double gr = 1.618033988749894848204586834365638117720309179805 7; double x, xx; x = pow(gr, n) * isf; xx = floor(x); if (x - xx 0.5) xx += 1; return xx; } #ifdef UNIT_TEST #include int main(void) { unsigned i; double dfib; for (i = 0; i <= 42; i++) { dfib = fibonacci(i); printf("fibonacci(%d) = %.0f\n", i, dfib); } return 0; } #endif /* dcorbit@DCORBIT64 /c/tmp \$ gcc -std=c99 -Wall -pedantic -Wextra -DUNIT_TEST fib.c dcorbit@DCORBIT64 /c/tmp \$ ./a fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = 1 fibonacci(3) = 2 fibonacci(4) = 3 fibonacci(5) = 5 fibonacci(6) = 8 fibonacci(7) = 13 fibonacci(8) = 21 fibonacci(9) = 34 fibonacci(10) = 55 fibonacci(11) = 89 fibonacci(12) = 144 fibonacci(13) = 233 fibonacci(14) = 377 fibonacci(15) = 610 fibonacci(16) = 987 fibonacci(17) = 1597 fibonacci(18) = 2584 fibonacci(19) = 4181 fibonacci(20) = 6765 fibonacci(21) = 10946 fibonacci(22) = 17711 fibonacci(23) = 28657 fibonacci(24) = 46368 fibonacci(25) = 75025 fibonacci(26) = 121393 fibonacci(27) = 196418 fibonacci(28) = 317811 fibonacci(29) = 514229 fibonacci(30) = 832040 fibonacci(31) = 1346269 fibonacci(32) = 2178309 fibonacci(33) = 3524578 fibonacci(34) = 5702887 fibonacci(35) = 9227465 fibonacci(36) = 14930352 fibonacci(37) = 24157817 fibonacci(38) = 39088169 fibonacci(39) = 63245986 fibonacci(40) = 102334155 fibonacci(41) = 165580141 fibonacci(42) = 267914296 dcorbit@DCORBIT64 /c/tmp */ Mar 17 '07 #1
9 Replies

 P: n/a On Mar 17, 2:11 pm, "user923005" double fibonacci(unsigned n) { /* isf is 1/sqrt(5) */ static const double isf = 0.447213595499957939281834733746255247088123671922 31; /* gr is golden ratio */ static const double gr = 1.618033988749894848204586834365638117720309179805 7; double x, xx; x = pow(gr, n) * isf; xx = floor(x); if (x - xx 0.5) xx += 1; return xx; } #ifdef UNIT_TEST #include int main(void) { unsigned i; double dfib; for (i = 0; i <= 42; i++) { dfib = fibonacci(i); printf("fibonacci(%d) = %.0f\n", i, dfib); } return 0; } #endif /* dcorbit@DCORBIT64 /c/tmp \$ gcc -std=c99 -Wall -pedantic -Wextra -DUNIT_TEST fib.c dcorbit@DCORBIT64 /c/tmp \$ ./a fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = 1 fibonacci(3) = 2 fibonacci(4) = 3 fibonacci(5) = 5 fibonacci(6) = 8 fibonacci(7) = 13 fibonacci(8) = 21 fibonacci(9) = 34 fibonacci(10) = 55 fibonacci(11) = 89 fibonacci(12) = 144 fibonacci(13) = 233 fibonacci(14) = 377 fibonacci(15) = 610 fibonacci(16) = 987 fibonacci(17) = 1597 fibonacci(18) = 2584 fibonacci(19) = 4181 fibonacci(20) = 6765 fibonacci(21) = 10946 fibonacci(22) = 17711 fibonacci(23) = 28657 fibonacci(24) = 46368 fibonacci(25) = 75025 fibonacci(26) = 121393 fibonacci(27) = 196418 fibonacci(28) = 317811 fibonacci(29) = 514229 fibonacci(30) = 832040 fibonacci(31) = 1346269 fibonacci(32) = 2178309 fibonacci(33) = 3524578 fibonacci(34) = 5702887 fibonacci(35) = 9227465 fibonacci(36) = 14930352 fibonacci(37) = 24157817 fibonacci(38) = 39088169 fibonacci(39) = 63245986 fibonacci(40) = 102334155 fibonacci(41) = 165580141 fibonacci(42) = 267914296 dcorbit@DCORBIT64 /c/tmp */ i am working on Section 3 of Steve Summit notes, so i am not confronted with thsese "static int", "unsigned int", "#ifdef" and UNIT TEST kind of things. i will start chapter 4 now Mar 17 '07 #2

 P: n/a arnuld wrote: On Mar 17, 2:11 pm, "user923005" i am working on Section 3 of Steve Summit notes, so i am not confronted with thsese "static int", "unsigned int", "#ifdef" and UNIT TEST kind of things. Surely you knew about the first two when you were going through K&R a while back? And the #ifdef for UNIT_TEST can be safely removed from the code. Don't forget to remove the corresponding #endif. Mar 17 '07 #3

 P: n/a On Mar 17, 11:53 pm, "santosh"

 P: n/a user923005 wrote: /* ** Direct computation of Fibonacci numbers. ** ** Input: index of Fibonacci number to compute (n) ** ** Returns: nth Fibonacci number. */ #include double fibonacci(unsigned n) { /* isf is 1/sqrt(5) */ static const double isf = 0.447213595499957939281834733746255247088123671922 31; /* gr is golden ratio */ static const double gr = 1.618033988749894848204586834365638117720309179805 7; [ snip ] 4.4721359549995793e-01 is as close as you can get to 1.0/sqrt(5.0) with a 64-bit double. All those other digits are nonsense. -- Joe Wright "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Mar 18 '07 #5

 P: n/a Joe Wright /*** Direct computation of Fibonacci numbers.**** Input: index of Fibonacci number to compute (n)**** Returns: nth Fibonacci number.*/#include double fibonacci(unsigned n){ /* isf is 1/sqrt(5) */ static const double isf = 0.447213595499957939281834733746255247088123671922 31; /* gr is golden ratio */ static const double gr = 1.618033988749894848204586834365638117720309179805 7; [ snip ] 4.4721359549995793e-01 is as close as you can get to 1.0/sqrt(5.0) with a 64-bit double. All those other digits are nonsense. They're nonsense *unless* the platform's double type happens to be bigger than 64 bits. (It's actually the size of the significand, of of the full type, that's significant.) The constants shown have about 166 significant bits. On a typical platform with 64-bit doubles, the extra digits will be quietly ignored, and no harm done -- but the program will also work correctly on platforms with larger doubles. But it will break down on platforms where double is *really really* big. Theoretically, there's no upper bound on the precision of the floating-point types, so no constant can really have enough digits. If you actually want to use all the precision available, the best approach is to compute your constants at run time (or possibly at compile time if your compiler is sufficiently clever). For example: const double isf = 1.0/sqrt(5.0); const double gr = (sqrt(5.0) + 1.0) / 2.0; You'll want to do these computations only once, not every time the function is called, since sqrt() might be expensive. And you can't have a function call in the initializer for a static object, so it's a little harder to encapsulate the declarations. For a small program, it's reasonable to declare them as "globals" (objects with file scope and static storage duration); you just have to remember to initialize them before using them. For a larger program, it probably makes sense to provide a header containing declarations of the objects and an initialization routine. Finally, you should consider using long double if you want as much precision as possible. And if "as much precision as possible" isn't good enough, there are extended-precision math packages, like the GNU GMP bignum library. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Mar 18 '07 #6

 P: n/a On Mar 19, 8:39 am, Keith Thompson

 P: n/a Old Wolf said: There is a simpler way to compute the sequence of Fibonacci numbers ! usernnnnn's solution looked pretty simple to me. What way did you have in mind that is simpler? If it involves recursion or iteration, you'll have your work cut out justifying that "simpler" claim. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Mar 19 '07 #8

 P: n/a Richard Heathfield There is a simpler way to compute the sequence of Fibonacci numbers ! usernnnnn's solution looked pretty simple to me. What way did you have in mind that is simpler? If it involves recursion or iteration, you'll have your work cut out justifying that "simpler" claim. If you want the sequence, then recursion or iteration might really be simpler. If you just want one value at a specified place in the sequence, then it's easier to use the closed form. -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton Mar 19 '07 #9

 P: n/a On Mar 18, 8:50 pm, Ben Pfaff

### This discussion thread is closed

Replies have been disabled for this discussion. 