6
$\begingroup$

How would you compute the first $k$ digits of the first $n$th Fibonacci numbers (say, calculate the first 10 digits of the first 10000 Fibonacci numbers) without computing (storing) the whole numbers ?

A trivial approach would be to store the exact value of all the numbers (with approximately $0.2n$ digits for the $n$th number) but this requires performing additions over numbers with many digits (and also a lot of storage), even if $k$ is small. Perhaps there's a way to accomplish this using only smart approximations that lead to precise results for the first $k$ digits.

Thanks in advance.

$\endgroup$
  • $\begingroup$ You might be able to use the fact that $F_n$ is the integer nearest $\frac{\varphi^n}{\sqrt5}$, where $\varphi=\frac12(1+\sqrt5)$, if you can determine how precisely you have to take the logs. $\endgroup$ – Brian M. Scott Apr 9 '13 at 4:17
5
$\begingroup$

We have $$F_n = \dfrac{\left(\dfrac{1+\sqrt5}2\right)^n - \left(\dfrac{1-\sqrt5}2\right)^n}{\sqrt{5}}$$ Hence, $$F_n = \begin{cases} \left\lceil{\dfrac{\left(\dfrac{1+\sqrt5}2\right)^n}{\sqrt{5}}} \right\rceil & \text{if $n$ is odd}\\ \left\lfloor{\dfrac{\left(\dfrac{1+\sqrt5}2\right)^n}{\sqrt{5}}} \right\rfloor & \text{if $n$ is even}\end{cases}$$ Now compute the $n\log(\phi)$ and use it to compute the first desired number of digits of $F_n$ from above.

$\endgroup$
4
$\begingroup$

How about Binet's formula? If you want the first $k$ digits, you need to calculate $\sqrt 5$ to not many more than $k$ digits (use the continued fraction, for example) and you are there. The subtraction doesn't cancel, and if $n$ is large you can ignore the second term in the numerator-it is tiny.

$\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.