Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.