2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ anything wrong with keeping enough precision so that the roundoff error is <1/2 and then rounding to the nearest integer? $\endgroup$
    – Sasho Nikolov
    Commented Dec 4, 2012 at 7:12
  • $\begingroup$ 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. $\endgroup$
    – adrianN
    Commented Dec 4, 2012 at 8:42
  • $\begingroup$ 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.... $\endgroup$
    – vzn
    Commented Dec 4, 2012 at 16:00

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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