Errors in calculating Fibonacci with Binet's Formula

Programming Questions

jda02130

Errors in calculating Fibonacci with Binet's Formula

in Programming Questions • 3 years ago

I'm relatively new to processing so apologies if I've missed something obvious in the following. After combing over the forums I've yet to find a post referencing Binet's -

I'm looking to calculate the Nth Fibonacci number using the following code based on Binet's formula:

int FibN(int FibNum) {
float phi = (1+sqrt(5))/2;
float res = (pow(phi,FibNum)-pow((-1/phi),FibNum)) / sqrt(5);
return int(res);
}

This works great up until the 30th position

FibN(30) = 832040 // Correct
FibN(31) = 1346269 // Correct
FibN(32) = 2178309 // Correct
FibN(33) = 3524579 // Incorrect - should be 3524578
FibN(34) = 5702888 // Incorrect - should be 5702887

As we go higher things are farther and farther off

FibN(46) = 1836312704 // Should be 1836311903

Am I missing something inherent in the data type or the conversions? Is there a more direct processing method to obtain these results without calculating all the proceeding values for the Nth position?

Thanks!

Replies(5)

blindfish

Re: Errors in calculating Fibonacci with Binet's Formula

3 years ago

Looking at the error margin I'd guess it's just an issue with floating point precision...

bjordal

Re: Errors in calculating Fibonacci with Binet's Formula

3 years ago

The square root of 5 is an irrational number meaning it has an infinite amount of decimals. Obviously storing an infinite amount of decimals would require an infinite amount of RAM so sqrt(5) is cut of (rounded) after n amount of decimals (i am not sure how many decimals a float can contain). So, in other words, true irrational numbers cannot exist in a computer and are instead rounded. Your error is due to that fact that the formula that you are using requires that two numbers are truly irrational (i.e not rounded) to output the correct result. To conclude, the formula you are using does not works on computers, it only works in theory.

Now what you have to do is to use the good old recursive formula for finding the nth fib number:

a _n=(a _n-1)+(a _n-2)
where a ₁= a ₂= 1
edit: that's strange - the formatting does not work...

jda02130

Re: Errors in calculating Fibonacci with Binet's Formula

3 years ago

Thanks for the replies - I figured as much, I just didn't realize the float precision would start effecting such an early position.
Thanks bjordal - I'll take the brute force approach and go with the recursive solution.
--
I also noted the exponent formatting doesn't work

PhiLho

Re: Errors in calculating Fibonacci with Binet's Formula

3 years ago

As you shown, float has a quite limited precision, although OK for most Processing needs, and not eating too much memory. That's why all floating point constants in Processing are floats.
But you can use double for a much better precision.
And if you need to go even beyond, you can try and use the BigDecimal API...

" go with the recursive solution"
Well, you also have an iterative solution, that is less likely to blow the stack!

bjordal

Re: Re: Errors in calculating Fibonacci with Binet's Formula

3 years ago

With recursive i of course meant iterative, sorry got words mixed up :)

Top Reply