Steve Summit C Notes {Anticipating the next one}

[user923005]

/*
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
#include <math.h>
double fibonacci(unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;
double x,
xx;

x = pow(gr, n) * isf;
xx = floor(x);
if (x - xx > 0.5)
xx += 1;
return xx;
}

#ifdef UNIT_TEST
#include <stdio.h>
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
*/

 

[arnuld]

/*
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
#include <math.h>
double fibonacci(unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;
double x,
xx;

x = pow(gr, n) * isf;
xx = floor(x);
if (x - xx > 0.5)
xx += 1;
return xx;

}

#ifdef UNIT_TEST
#include <stdio.h>
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

 

[santosh]

On Mar 17, 2:11 pm, "user923005" <[email protected]> wrote:

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.

 

[arnuld]

Surely you knew about the first two when you were going through K&R a
while back?

only "unsigned int", i did not encounter "static int" there.

And the #ifdef for UNIT_TEST can be safely removed from
the code. Don't forget to remove the corresponding #endif.

ok, fine

 

[Joe Wright]

/*
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
#include <math.h>
double fibonacci(unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;

[ 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.

 

[Keith Thompson]

/*
** Direct computation of Fibonacci numbers.
**
** Input: index of Fibonacci number to compute (n)
**
** Returns: nth Fibonacci number.
*/
#include <math.h>
double fibonacci(unsigned n)
{
/* isf is 1/sqrt(5) */
static const double isf =
0.44721359549995793928183473374625524708812367192231;
/* gr is golden ratio */
static const double gr =
1.6180339887498948482045868343656381177203091798057;

[ 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.

 

[Old Wolf]

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.

There is a simpler way to compute the sequence of Fibonacci numbers !

 

[Richard Heathfield]

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.

 

[Ben Pfaff]

Old Wolf said:

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.

 

[user923005]

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 all of my replies, I tried to make the examples something that were
generally useful. That is why the solutions use function calls and
are not simply inlined main() routines (except the even/odd thing
which was totally trivial and not worth the bother).

In other words, it does not simply solve the problem at hand for a
given value, but solves the problem in a general sense. (AKA
'reusable').

That is the chief distraction I see from most of the other solutions.
They solve the exact given instance of the problem but not the general
case, so the only utility of the code presented is to solve the single
problem posed -- and not having usages for future problems of a
similar nature. I think that is a very bad way to code. I think it
even worse to teach it to a beginner. But you have to start
somewhere.

IMO-YMMV.