[Solved]: Calculating Binet's formula for Fibonacci numbers with arbitrary precision

Problem Detail: 

Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error.

Is there a discussion/description somewhere of how to calculate the Fibonacci sequence using Binet's formula (ie not the recurrence relation) and floating point arithmetic which results in no roundoff error?

Asked By : vzn

Answered By : Hendrik Jan

As the comments show, roundig is a respected method for Fibonacci computations. See also "Computation by rounding" in the wiki-lemma.

You avoid roundoff by computing exactly, but using numbers of the form $a+b\sqrt5$: $(a+b\sqrt5)(c+d\sqrt5) = (ac+5bd)+(ad+bc)\sqrt5$. Technically that is $Z[\sqrt5]$ I believe. But I now realise that you also have to take into account that $a,b$ are fractions.

But the recursion is so nice, why not use it? Based on the matrix form you can get the $n$-th Fibo number in a logarithmic number of steps.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7145