# Computing first digits of Fibonacci numbers

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.

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. –  Brian M. Scott Apr 9 '13 at 4:17
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.
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.