Joe Wright <jo********@comcast.netwrites:

user923005 wrote:
>/*

** 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.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 <http://www.ghoti.net/~kst>

San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>

"We must do something. This is something. Therefore, we must do this."

-- Antony Jay and Jonathan Lynn, "Yes Minister"