Thread: fibonacci sequence

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

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

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

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

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.

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.

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.

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

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.

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.