Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
anything wrong with keeping enough precision so that the roundoff error is <1/2 and then rounding to the nearest integer? –  Sasho Nikolov Dec 4 '12 at 7:12
    
What do you mean by 'no roundoff error'? If you use finite precision you will always have to do some rounding, but for large enough precision the rounding result will always be correct. –  adrianN Dec 4 '12 at 8:42
    
I think @adrianNs comment is closest to my interest. maybe am thinking of a scheme that carries/"remembers" the known uncertainty of all the terms & then gives the final result to the desired/specified uncertainty. or specifically a scheme that guarantees the "nth" (incl fractional) bit of the answer is correct for any "n" given prior to calculation. also if a larger "n" is desired than previously, an answer that builds on the prior result, sort of like a streaming algorithm.... ideally using some general scheme that would be applicable to other similar formulas.... –  vzn Dec 4 '12 at 16:00
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
1  
There is quite a bit known about computing with k-th roots. See for example the implementation in LEDA, explained here –  adrianN Dec 4 '12 at 9:06
1  
There's also quite a bit not known about computing with roots, of course - see, e.g., the sum-of-square-roots problem, cs.smith.edu/~orourke/TOPP/P33.html and cstheory.stackexchange.com/questions/79/… –  Steven Stadnicki Dec 5 '12 at 19:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.