# fibonacci sequence

Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last
• 10-16-2008
cph
fibonacci sequence
hello, I wrote a code that prints a fibonacci sequence
Code:

```#include <math.h> #include <stdio.h> /* http://goldennumber.net/five(5).htm */ #define PHI pow(M_E, asinh(0.5)) /* http://goldennumber.net/five(5).htm */ double fib (unsigned int n) {     return((pow(PHI, (double)n)) / sqrt(5.0)); } int main (void) {     int x;  /* counter */     for (x = 0; x < 100; ++x) {         printf("%5d%40.0f\n", x, fib(x));     }     return(0); }```
the problem is, when x=71 it prints incorrect result (f[n] != f[n-1] + f[n-2]), it also prints incorrect result for x=76 and after x=79.

can anyone help me with this problem?
• 10-16-2008
QuantumPete
That's because you're not calculating the Fibonacci series. The fibonacci series is simply starting with 1 and 1 and every subsequent number in the series is the sum of the preceding two. You definitly don't need pow, sqrt or doubles to accomplish that. At its simplest it's just a recursive algorithm.

QuantumPete
• 10-16-2008
cph
Quote:

Originally Posted by QuantumPete
That's because you're not calculating the Fibonacci series. The fibonacci series is simply starting with 1 and 1 and every subsequent number in the series is the sum of the preceding two. You definitly don't need pow, sqrt or doubles to accomplish that. At its simplest it's just a recursive algorithm.

QuantumPete

actually I've tried that (slow) recursive fibonacci algorithm (and the problem is it's too slow).
• 10-16-2008
matsp
Of course, if you want to calculate all fibonacci numbers from fib(1) to fib(n) where n is a relatively large number, you may want to solve the problem in a different way than recursively - for example, you could store the previous results in an array (or just keep the last two values) - that way, you don't need to calculate ALL the values from fib(1) to fib(x-1) before you get fib(x).

--
Mats
• 10-16-2008
matsp
Just to confirm, calculating every fib(n) for 0..4999999 takes 0.11 seconds using an array to store the previous values [I doubt that the higher numbers are actually correct, as my math uses integers to calculate the fibonacci values - and at some point pretty soon the integer values overflow - I just went that far to get past 0.0 seconds].

--
Mats
• 10-16-2008
MK27
Quote:

Originally Posted by cph
actually I've tried that (slow) recursive fibonacci algorithm (and the problem is it's too slow).

Oh malarky

Code:

```#include <stdio.h> int main () {         int a=0, b=1, n=a+b,i,ii;         puts("Number of iterations");         scanf("&#37;d",&ii);         printf("%d %d ",a,b);         for (i=0;i<ii;i++) {                 n=a+b;                 printf("%d ",n);                 a=b;b=n;         } }```
I don't know much math, so I'd be really interested to read how you could make this computation "more efficient".

 i guess this is actually iterative, and not recursive
• 10-16-2008
matsp
Quote:

Originally Posted by MK27
Oh malarky

Code:

```#include <stdio.h> int main () {         int a=0, b=1, n=a+b,i,ii;         puts("Number of iterations");         scanf("%d",&ii);         printf("%d %d ",a,b);         for (i=0;i<ii;i++) {                 n=a+b;                 printf("%d ",n);                 a=b;b=n;         } }```
I don't know much math, so I'd be really interested to read how you could make this computation "more efficient".

Well, of course, if you ONLY want to know what fibonacci number 43 is, you will have to loop around. On my machine, using the recursive method, it takes 621 seconds to do the first 50 - but that's not the time it takes to do one number.

--
Mats
• 10-16-2008
MK27
Quote:

Originally Posted by matsp
On my machine, using the recursive method, it takes 621 seconds to do the first 50 - but that's not the time it takes to do one number.

I think what matsp means is that he's on the machine, and it took him ten minutes.
• 10-16-2008
matsp
Quote:

Originally Posted by MK27
I think what matsp means is that he's on the machine, and it took him ten minutes.

No, my machine takes 10 minutes for the first 50 numbers, when using the trivial recursive method. Iteratively, it is very much faster.

--
Mats
• 10-16-2008
QuantumPete
Quote:

Originally Posted by matsp
No, my machine takes 10 minutes for the first 50 numbers, when using the trivial recursive method. Iteratively, it is very much faster.

--
Mats

Probably due to the overhead of creating stack frames and the like. I'm guessing what the OP is trying to do is to generate an approximation to the right number.

QuantumPete
• 10-16-2008
MK27
Quantum Pete and I are in the same iterative boat, I think.

What would the "trivial recursive method" look like?
• 10-16-2008
QuantumPete
Code:

```int fib (int num) {     if (num < 2) {       return 1;     }     return fib (num-1) + fib(num-2); }```
Something like that. I haven't tested it.

QuantumPete
• 10-16-2008
MK27
[QUOTE=QuantumPete;797086]
Code:

```int fib (int num) {     if (num < 2) {       return 1;     }     return fib (num-1) + fib(num-2); }```
If num = 3, it will take even more than ten minutes...it could take forever.
• 10-16-2008
QuantumPete
Quote:

Originally Posted by MK27
If num = 3, it will take even more than ten minutes...it could take forever.

I just tested it and though it should be an "<=" instead of just "<", it does work properly and returns immediately.

QuantumPete
• 10-16-2008
QuantumPete
This is what I get:
Code:

``` time ./fib.tsk 50 Result = -298632863 real    13m27.65s user    11m42.11s sys    0m4.31s```
Obviously it's wrapped around, since i'm only using ints instead of unsigned long longs. I've also got a version that uses a run-time populated table to speed up calculation.

Code:

``` time ./fib_table.tsk 50 Fib for 50 = -298632863 real    0m0.02s user    0m0.01s sys    0m0.01s```
QuantumPete
Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last