[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

## 11.3 An Example

A function which computes the nth Fibonacci number can be written as follows.

#include <cln/integer.h> #include <cln/real.h> using namespace cln; // Returns F_n, computed as the nearest integer to // ((1+sqrt(5))/2)^n/sqrt(5). Assume n>=0. const cl_I fibonacci (int n) { // Need a precision of ((1+sqrt(5))/2)^-n. float_format_t prec = float_format((int)(0.208987641*n+5)); cl_R sqrt5 = sqrt(cl_float(5,prec)); cl_R phi = (1+sqrt5)/2; return round1( expt(phi,n)/sqrt5 ); }

Let’s explain what is going on in detail.

The include file `<cln/integer.h>`

is necessary because the type
`cl_I`

is used in the function, and the include file `<cln/real.h>`

is needed for the type `cl_R`

and the floating point number functions.
The order of the include files does not matter. In order not to write
out `cln::`

`foo` in this simple example we can safely import
the whole namespace `cln`

.

Then comes the function declaration. The argument is an `int`

, the
result an integer. The return type is defined as ‘`const cl_I`’, not
simply ‘`cl_I`’, because that allows the compiler to detect typos like
‘`fibonacci(n) = 100`’. It would be possible to declare the return
type as `const cl_R`

(real number) or even `const cl_N`

(complex
number). We use the most specialized possible return type because functions
which call ‘`fibonacci`’ will be able to profit from the compiler’s type
analysis: Adding two integers is slightly more efficient than adding the
same objects declared as complex numbers, because it needs less type
dispatch. Also, when linking to CLN as a non-shared library, this minimizes
the size of the resulting executable program.

The result will be computed as expt(phi,n)/sqrt(5), rounded to the nearest integer. In order to get a correct result, the absolute error should be less than 1/2, i.e. the relative error should be less than sqrt(5)/(2*expt(phi,n)). To this end, the first line computes a floating point precision for sqrt(5) and phi.

Then sqrt(5) is computed by first converting the integer 5 to a floating point number and than taking the square root. The converse, first taking the square root of 5, and then converting to the desired precision, would not work in CLN: The square root would be computed to a default precision (normally single-float precision), and the following conversion could not help about the lacking accuracy. This is because CLN is not a symbolic computer algebra system and does not represent sqrt(5) in a non-numeric way.

The type `cl_R`

for sqrt5 and, in the following line, phi is the only
possible choice. You cannot write `cl_F`

because the C++ compiler can
only infer that `cl_float(5,prec)`

is a real number. You cannot write
`cl_N`

because a ‘`round1`’ does not exist for general complex
numbers.

When the function returns, all the local variables in the function are automatically reclaimed (garbage collected). Only the result survives and gets passed to the caller.

The file `fibonacci.cc`

in the subdirectory `examples`

contains this implementation together with an even faster algorithm.

[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

This document was generated on *August 27, 2013* using *texi2html 5.0*.