[Math] Computing first digits of Fibonacci numbers

elementary-number-theoryfibonacci-numbersnumerical methods

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.

Best Answer

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.