Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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