Thread: fibonacci sequence

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

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?

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

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

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.

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.