Wednesday, July 18, 2012

Fibonacci Numbers

Wrote a couple of versions of Fibonacci number generators.

Interestingly, the numbers become inaccurate at just the 93rd fib number in the sequence: the real numbers begin losing precision on the low end.   I am going to have to figure out how to use one of the bignum libraries in order to work exactly with such large values.  My fear is that the bignum libraries have a substantial performance hit in return for the accurate values.

The recursive version becomes too slow to use at just the 40th number in the sequence, while the non-recursive version fires through thousands of values.

`Fib-recursive.c`
` `
```#include <stdio.h>

/* This program calculates fibonacci sequence using recursion

1 1 2 3 5 8 13 21 34

Starting with 1
Each number in the sequence is created by adding the previous two numbers in sequence.

*/

long double fib(long double value){
if (value <= 2)
return 1;

return (fib(value-1) + fib (value-2));
}

int
main(){

long double i;

for (i = 1; i<1000; i++)
printf ("value is %.0Lf and return value is %.0Lf\n", i, fib(i));

}```
` `
` `
` `
`Fib-nonrecursive.c`
` `
```#include <stdio.h>

/* This program calculates fibonacci sequence using recursion

1 1 2 3 5 8 13 21 34

Starting with 1
Each number in the sequence is created by adding the previous two numbers in sequence.

If you notice, something bad happens when we reach number 93 and we lose precision off the end.
The number is close to the right number but is subtly wrong.

We need to switch to a bignum library to add numbers that large precisely.

Interestingly we can calculate the first thousand numbers in the sequence this way before we can calculate the first 30 numbers recursively.

*/

int
main(){

long double i, j, p1, p2;

p1 = 0;
p2 = 1;
i  = 0;
j = 1;

while (j<1000){
i = p1 + p2;
printf ("\t%.0Lf\t%.0Lf\n", j, i);
p2 = p1;
p1 = i;
j++;
}

} ```
` `
` `