4
$\begingroup$

With regards to project Euler, problem 104: https://projecteuler.net/problem=104

The essence of the question here is how to keep track of the 9 most significant digits of a Fibonacci series (Keeping the 9 least significant digit is easy, just do all calculation mod $10^9$).

Since the answer requires adding huge numbers ($F_{>100,000}$ with similar amount of digits),most people got the answer by only keeping track of the 20 most significant digits, once the number has more than 20 digits.

In no answer I could find a proof that a rounding error can "bubble up" from the 21st digit up to the 9th digit. Is that a fair assumption? Were they just lucky, or you can prove that no Fibonacci number has 11 consecutive zeros in places 10 to 20?

$\endgroup$
  • $\begingroup$ Among the infinite number of Fibonacci numbers, it is highly likely that some have $11$ consecutive zeros in places $10$ to $20$ $\endgroup$ – Henry Apr 3 '16 at 9:29
2
$\begingroup$

If you imagine each step as roughly corresponding to a multiplication by $\phi$ with a relative rounding error of less than $10^{-19}$ (we are only interested in the error)

then taking logarithms base $e$ you could see this related to adding about $\log_e \phi$ to the logarithm of the Fibonacci number each time with an absolute error of less than $10^{-19}$ (again, we are only interested in the error)

and doing this up to $10^6$ times means the cumulative absolute errors on the logarithms cannot be more than $10^{-13}$ (and are likely to be much less)

implying that, taking the anti-logarithm to get back to the original question, the relative rounding errors on the first million Fibonacci numbers will each not be more than $10^{-13}$

so inspecting the $10$th, $11$th, and $12$th digits of the rounded Fibonacci number corresponding to the proposed solution for the Project Euler problem, to check they are not $\ldots 999\ldots$, will prove that no error has "bubbled up" enough to change that answer, and does so in this particular case

which means you do not need to check intermediate Fibonacci number calculations, so you could program your algorithm just to check its proposed final result, and if that fails then restart the calculation with more digits so eventually you will have enough, and in fact in this case you have enough in the first attempt

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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