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?

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

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

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

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

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

[edit] i guess this is actually iterative, and not recursive

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

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.

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

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

Quantum Pete and I are in the same iterative boat, I think.

What would the "trivial recursive method" look like?

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

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

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

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

Quote:

---

Originally Posted by QuantumPete

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

QuantumPete

---

Wow. You are correct (except the first number is 0...).

Using this loop to produce the first 45 (I think it wraps after that) did take more than a minute tho, whereas the iteritive one is instant:

Code:

---

int main (int argc, char *argv[]) {
        int answer,i;
       
        for (i=1;i<=atoi(argv[1]);i++) {
                answer=fib(i);
                printf("%d ", answer);
        }
}

---

Quote:

---

Originally Posted by MK27

Using this loop to produce the first 45 (I think it wraps after that) did take more than a minute tho, whereas the iteritive one is instant:

---

Of course, my code only provides you with a final answer. It's not designed to print out all the fibonacci numbers along the way. That very much depends on the requirements for the program!

QuantumPete

I think we are ALL saying the same thing: don't use recursion alone to calculate fibonaccie sequences. If you only need the ONE value, then calculate it iteratively - it's almost instant for small and large n (at least as long as n is 32-bit integer). If you want a list of the first X numbers, then you will need to store the results as you go along into an array. I wrote a recursive array variant:

Code:

---

#define SIZE 5000000

int fibarr[SIZE];
int maxn = -1;


int fib2(int n)
{
    if (n <= maxn)
    {
        return fibarr[n];
    }
    if (n == 0)
        return fibarr[0] = 0;

    if (n <= 2)
    {
        fibarr[n] = 1;
        return 1;
    }
    fibarr[n] = fib2(n-1) + fib2(n-2);
    if (maxn < n)
        maxn = n;
   
    return fibarr[n];
}

---

--
Mats

Quote:

---

Originally Posted by QuantumPete

Of course, my code only provides you with a final answer.

---

Really it's useless, since you might as well use the iterative approach and just limit the output to the final loop (as matsp just noted).

But it's very clever -- I could not even have thought that one up, and am still staring at it and inserting printf's to figure out what's going on. My eyes tell me it should have either looped forever, or always returned 2.

Quote:

---

Originally Posted by MK27

Really it's useless, since you might as well use the iterative approach and just limit the output to the final loop (as matsp just noted).

---

That's "useless" too, since you might as well use the formula ;)

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats

This is similar to what matsp posted, except it will take arbitrary numbers:

Code:

---

typedef unsigned long long ull;

ull fib_t (int num, ull * precalc) {
    if (num <= 2) {
        return 1;
    }
    if (precalc[num] == 0) {
        precalc[num] =  fib_t(num-1, precalc) + fib_t (num-2, precalc);
        printf ("&#37;d = %llu\n", num, precalc[num]);
    }
    return precalc[num];
}

int main (int argc, char ** argv) {
    int num = 0;
    ull * table = 0;
    if (argc != 2) {
        printf ("You must specifiy a number\n");
        return 1;
    }

    num = atoi (argv[1]);
    table = calloc (num+1, sizeof (ull));
    if (table == 0) {
        printf ("malloc failed!\n");
        return 1;
    }

    printf ("Fibonacci Number for %d = %llu\n", num, fib_t(num, table));
    free (table);
    return 0;
}

---

It even prints out all the numbers as it computes them :)

QuantumPete

Quote:

---

Originally Posted by MK27

But it's very clever -- I could not even have thought that one up, and am still staring at it and inserting printf's to figure out what's going on. My eyes tell me it should have either looped forever, or always returned 2.

---

Checking the Wikipedia entry on the Fibonacci numbers, I see that one can actually derive it directly from the recurrence relation presented there. I also recall that it was the introductory example of at least one algorithms textbook. Consequently, I suggest that you work through such a text to help you understand recursion better.

Quote:

---

Originally Posted by matsp

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

---

Yes, I think so too.

Quote:

---

Originally Posted by matsp

Except the original poster is complaining that the result is inexact - I suspect it's simply that the double precision isn't good enough...

--
Mats

---

True, but why use an approximation, when a computed-table approach will get you the result almost as fast?

QuantumPete

Quote:

---

Originally Posted by QuantumPete

True, but why use an approximation, when a computed-table approach will get you the result almost as fast?

---

If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.

Quote:

---

Originally Posted by laserlight

If a formula that is not difficult to implement produces the result as fast and as accurately as using memoization, I would certainly prefer the formula since it has constant space complexity.

---

But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?

QuantumPete

Quote:

---

Originally Posted by QuantumPete

But that formula can only be an approximation; true it depends on the requirements, but in the end iterative, recursive and computed-table are the only ways to implement the original fibonacci series correctly, no?

---

Mathematically, the formula is indeed another way to compute the nth number in the original Fibonacci series, but in practice, it is an approximation since we do not have infinite precision floating point arithmetic. On the other hand, the approximation can be accurate, since we are dealing with integers in the end.

Okay, I'm really busted by this one! Short of reading the recommended book, can anyone help explain it? I used the following

Code:

---

#include <stdio.h>

int fib (int num) {
        int x, y;
        printf("fib: %d\n", num);
        if (num <= 2) {
                return 1;
        }
        x=fib(num-1); y=fib(num-2);
        printf("x: %d y: %d\n", num);
        fflush(stdout);
        return x+y;
}

int main (int argc, char *argv[]) {
        int answer,i;
       
        for (i=1;i<=atoi(argv[1]);i++) {
                printf("\nto fib: %d\n", i);
                answer=fib(i);
                printf("answer: %d\n", answer);
        }
}

---

./a.out 3
to fib: 1
fib: 1
answer: 1

to fib: 2
fib: 2
answer: 1

to fib: 3
fib: 3
fib: 2
fib: 1
x: 3 y: 0
answer: 2

How does x end up as 3, y as 0, and the answer as 2?

Because your printf isn't being given the right data:

Code:

---

printf("x: %d y: %d\n", num);

---

If it's gcc, -Wall will tell you that you have one too few arguments, even if it is not telling you that num isn't x or y.

--
Mats

Yeah that was dumb. I'm staring at the real output now.

I still don't get it....[later] maybe I do...

to fib: 5 okay
fib: 5 right...
fib: 4
fib: 3
fib: 2
fib: 1
x: 1 y: 1 that makes sense
fib: 2 and this
x: 2 y: 1 so finally x's x is 2 (1+1)
fib: 3 y's x (?)
fib: 2
fib: 1
x: 1 y: 1
x: 3 y: 2 x is 2+1, y is 1+1
answer: 5

Is that right? I'm shaky about the last bit.

You probably want to instrument each of the return lines to show what they are actually returning, but 2 + 3 is fib(3) + fib(4) -> fib(5).

--
Mats

Quote:

---

Originally Posted by matsp

You probably want to instrument each of the return lines to show what they are actually returning

---

Wouldn't that be x+y?

Quote:

---

Originally Posted by MK27

Wouldn't that be x+y?

---

Yes, or 1.

--
Mats

Alright, I finally solved this for myself and anyone else who may have been baffled by QuantumPete's wizardry.

Using:

Code:

---

#include <stdio.h>

int fib (int num, char *side) {
        int x=-1, y=-1;
        printf("fib: %d %s\n", num, side);
        if (num <= 2) {
                printf("done %s\n", side);       
                return 1;
        }
        x=fib(num-1,"X"); y=fib(num-2,"Y");
        printf("x: %d y: %d %s\n", x, y, side);
        return x+y;
}

int main (int argc, char *argv[]) {
        printf("answer: %d\n", fib(atoi(argv[1]), "start"));
}

---

./a.out 5

Code:

---

fib: 5 start        calculation of fib(5)
fib: 4 X          recursion for X: fib(5-1)
fib: 3 X                recursion for x of X: fib(4-1)
fib: 2 X                recursion for x of x of X: fib(3-1)
done  X                equals 2, return 1 for x of X.
fib: 1 Y            y of x of X
done  Y                ...will be 1
x: 1 y: 1 X      so x of X is 2
fib: 2 Y           
done  Y                and y of X is 1
x: 2 y: 1 X        so X will be 3
fib: 3 Y              recursion for Y: fib(5-2)
fib: 2 X                recursion for x of Y: fib(3-1)       
done X                is 2, so return 1
fib: 1 Y                recursion for y of Y: fib(3-2)
done Y                returns 1 also
x: 1 y: 1 Y        so Y will be 2
x: 3 y: 2 start
answer: 5                okay!

---

No wonder it takes so long -- it's essentially adding 1+1+1+1+1+1...

I am looking at some equations for calculating arbitrary fibonacci numbers and I am not seeing anything terribly like the one which you are using. Your equation itself is wrong. That is why your output is wrong. And as its been said several times over, iteratively calculating these numbers is not a terrible chore and it need only be done once, tabled, and used on-demand.

Quote:

---

Originally Posted by master5001

I am looking at some equations for calculating arbitrary fibonacci numbers and I am not seeing anything terribly like the one which you are using. Your equation itself is wrong. That is why your output is wrong. And as its been said several times over, iteratively calculating these numbers is not a terrible chore and it need only be done once, tabled, and used on-demand.

---

You're a nut. None of the output from any of these solutions was ever wrong and nobody ever claimed that either...

I was talking to the original poster, and I never said I was a nut, but I am saying I am not wrong. The OP asked how come his output was wrong, and I am stating why.

Quote:

---

Originally Posted by master5001

I was talking to the original poster, and I never said I was a nut, but I am saying I am not wrong. The OP asked how come his output was wrong, and I am stating why.

---

All apologies. And by "nut" I meant interesting...

:) Well I am a nut. And its all good. I took out my calculator and tried some stuff with his equation by hand, and it doesn't even calculate the third number correctly :(

Quote:

---

I took out my calculator and tried some stuff with his equation by hand, and it doesn't even calculate the third number correctly

---

Good for you. I couldn't even get it to compile since M_E is undefined for me :(

That said, going by the webpage referenced, the formula is correct (though that webpage's formula is itself an approximation, not the full formula).

Quote:

---

Originally Posted by QuantumPete

That's because you're not calculating the Fibonacci series.

---

But that's what it calculates. The fibbonacci series does have a closed form representation. Off the top of my head I'm not sure if the formula implemented here is the correct one, but I suspect that it is, given that things don't go wrong until the 71st element.

I'd attribute the problem to simple floating point inaccuracy.

#include <math.h>, laserlight. I will double check, but unless I did something else wrong, I didn't get the formula to work correctly. The point is moot though, since its not the most efficient way of solving this. Plus it would only be beneficial to use a formula like this to solve an arbitrarily high number, which cannot be done due to accuracy issues, apparently.

[edit]Wtf... *#include <float.h> I mean[/edit]

I am still not getting this to work. I get what the derivation is saying and all, and it looks fascinating. Perhaps I am just not doing it correctly. asinh() is a bastard to do on my calc.. But still, I did it correctly -_-

Quote:

---

I will double check, but unless I did something else wrong, I didn't get the formula to work correctly.

---

Perhaps you would like to try this, using just square root computation instead of a trigonometric function:

Code:

---

#include <math.h>
#include <stdio.h>

unsigned int fib(unsigned int n)
{
    double sqrt5 = sqrt(5.0);
    double phi = (1.0 + sqrt5) / 2.0;
    return (unsigned int)((pow(phi, n) / sqrt5) + 0.5);
}

int main(void)
{
    int x;

    for (x = 0; x < 48; ++x)
    {
        printf("&#37;u: %u\n", x, fib(x));
    }

    return 0;
}

---

Ideally, we should only compute sqrt5 and phi once, but anyway...

Quote:

---

The point is moot though, since its not the most efficient way of solving this.

---

That depends on what factors you are considering for efficiency.

Quote:

---

Plus it would only be beneficial to use a formula like this to solve an arbitrarily high number, which cannot be done due to accuracy issues, apparently.

---

Yes, and it is not as efficient as memoization when you want to generate all the Fibonacci numbers up to some limit, like what cph was trying to do.

You know what laserlight, I had an unfortunate IO error (That would be "Idiot Operator" not "Input/Output"). Yeah it works fine.. I am just a boob sometimes.

And yeah I tried the non-trigonometric version when I was looking at the derivation which is why I wasn't following how come my results weren't working. But it works fine.

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("&#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".

[edit] i guess this is actually iterative, and not recursive

---

That was a challenge! Here is my contest entry:

Code:

---

int fib(int n) {
int a[2] = { 0, 1 }, i;
for (i = n + 1 >> 1 ; i; i--)
    a[0] += a[1] += a[0];
return a[n & 1]; }

---

This takes about 1/2 the time yours does. But caution: highest legit value is 64. Gives 1,640,636,603 which is the largest integer that fits into 32 bit. I could go 64-bit but for timing purposes I just threw the two functions into another loop - executing factorial(64) 10,000,000 times.

Yours took about 12-13 seconds.
Mine is around 6-7 seconds.
(Mac laptop 1.33 GHz PowerPC G4)

Code:

---

a[0] += a[1] += a[0];

---

isn't that UB?

Code:

---

i = (n + 1) >> 1

---

??

--
Mats

um, excuse me, may I rephrase my question?

Code:

---

/* 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));
}

---

I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

Quote:

---

Originally Posted by cph

I need to get the right result from the function fib(), because when n=71, n=76, and after n=79 the function returns incorrect result (f[n]!=f[n-1]+f[n-2]).

---

64-bit numbers?
GMP?

You are asking how to reach above and beyond a hardware limitation. You are asking how to make your computer do something that is beyond the implementation of your algorithm. Right? I mean you see how I arrive at that conclusion, right?

Quote:

---

Originally Posted by matsp

Code:

---

a[0] += a[1] += a[0];

---

isn't that UB?

Code:

---

i = (n + 1) >> 1

---

??

--
Mats

---

+= associativity is right-to-left just as any assignment, so I assume it is executed in that order.

(n + 1) >> 1 - true, but I abhor extra parenthesis when they're not needed. Operator precedence is such that addition is done before the shift.

Quote:

---

Originally Posted by nonoob

I abhor extra parenthesis when they're not needed.

---

They do add to clarity though, and your post was a good example of that.

QuantumPete

Quote:

---

Originally Posted by nonoob

+= associativity is right-to-left just as any assignment, so I assume it is executed in that order.

---

Order of evaluation and associativity are not the same thing. However, I think that matsp is wrong - there is no undefined behaviour as far as I can tell. I recall a thread some time ago where the conclusion was that the XOR swap of a and b written as a ^= b ^= a ^= b; resulted in undefined behaviour, but I believe that is because a is modified twice within consecutive sequence points. In your code, however, both a[0] and a[1] are modified exactly once within consecutive sequence points.

Thanks for that explanation, laserlight. i was starting to get worried that I am misunderstanding associativity in any standard precedence chart. What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.

Quote:

---

Originally Posted by nonoob

What is it then if "right-to-left" is not related to execution order? The right argument is evaluated first, I thought.

---

The order of evaluation of operands is unspecified. In this case, it does not matter, but consider this contrived example:

Code:

---

#include <stdio.h>

int *foo(int *x, int y)
{
    printf("&#37;d\n", y);
    return x;
}

int main(void)
{
    int a = 1;
    int b = 2;
    *foo(&a, 1) += *foo(&b, 2) += *foo(&a, 3);
    return 0;
}

---

It is possible that on one implementation the output is "1\n2\n3\n" while on another it is "3\n2\n1\n".

Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.

First of all, the problem with this method posted above:

Code:

---

pow(PHI, n) / sqrt(5.0)

---

is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.

The correct way would be:

Code:

---

int Fib( int n )
{
  static const double s = sqrt(5.0);
  return int( (pow(1+s,n)-pow(1-s,n))/(pow(2.0,n)*s) );
}

---

(use long long instead of int for large n, as the result will obviously not fit in 32 bit integers).

There is, however, an even much faster way. After quite some experimenting with several approaches and lotsa optimizing, this is imho the ultimate solution: (besides using a direct lookup or caching table of course)

Code:

---

unsigned int Fib( unsigned int n )
{
  n--;
  unsigned int a=1,b=0,c=1,p=1,t;
  while (p<=n) p += p;
  do
  {
    p >>= 1;
    t = b*b;
    b *= a+c;
    a = a*a + t;
    c = c*c + t;   
    if (n&p)
    {
      c = b;
      b = a;
      a += c;
    }
  }
  while (p>1);
  return a;
}

---

This performs about 3 times as fast as the pow / √5 method. Of course, again, use long long for large n.

Quote:

---

Originally Posted by Phuzzillogic

Sorry to bump an old thread, but I came accross this accidentally and wanted to share my thoughts.

---

That is okay; I maintain that it is fine to post in an ancient thread when you have something worthwhile to contribute, especially if it is an important correction.

Quote:

---

Originally Posted by Phuzzillogic

is that it's simply incorrect, or incomplete. It's only half of the Fibonacci recurrence relation.

---

It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.

Quote:

---

Originally Posted by laserlight

It is not incorrect in its idea since the idea is that the other half can be ignored as it has negligible contribution in the approximation. I demonstrated a correct way to perform this approximation in post #45.

---

Ah I see, you're right, the correction you applied indeed makes up for the missing term.

Nonetheless, when I compare this "single pow" method to my integer version, the latter is still almost 15% faster.