I am participating in a challenge where I have to calculate the first four and last four digits of the Fibonacci sequence. My first try was just using $x_n = x_{n-1} + x_{n-2}$ but that takes to long for $n = 50\times 10^6$, so I looked it up on Google and found that
$$
x_n = \frac{\varphi^n – (1-\varphi)^n}{\sqrt{5}}.
$$
This approach is definitely much faster, but the programming language python can't handle numbers that large, so I thought that I can change the value of numbers to make it possible for the programming language to calculate the $50\times 10^6$-th number of the Fibonacci sequence. I just said that the number 1 has a value of $10^6$. Then I multiplied every number in the formula by $10^{-6}$ hoping this technique would work but it didn't.
Can anyone explain to me why this method doesn't work? If you also know a solution to my Fibonacci problem then please share. Thanks
Best Answer
The first 4 digits can be computed using Binet's formula as you have, which essentially boils down to computing $\varphi^n/\sqrt5$ to 4 significant figures since $(1-\varphi)^n$ decays exponentially. To do this, rewrite it as
$$\varphi^n=10^{n\log_{10}(\varphi)}$$
For $n=50\times10^6$ this becomes:
$$\varphi^n\simeq10^{10449382.0124989}=10^{0.0124989}\times10^{10449382}\simeq1.0291979\times10^{10449382}$$
Dividing $1.0291979$ by $\sqrt5$ gives us $0.4602713$, so the first 4 digits are $4602$.
One can compute the last 4 digits by simply keeping the last 4 digits in the Fibonacci recurrence each iteration, since the last 4 digits of $x_n$ is given by the sum of the last 4 digits of $x_{n-1}$ and $x_{n-2}$.
Eventually you will hit $0000$ and $0001$ as the last 4 digits again, and it simply loops from there.
This can be easily done with a program, which reveals it repeats every $15000$ iterations, and hence the last 4 digits of the $50\times10^6$th Fibonacci number is equivalent to the last 4 digits of the $5000$th Fibonacci number, which are given by $3125$ by a modification of the above code.
As pointed out by rtybase, there are recursive formulas that allow the $n$th Fibonacci number to be computed in $\mathcal O(\log n)$ iterations. By using such methods, we would need only $6\log_2(10)+\log_2(5)<23$ iterations to find the last 4 digits, by again modifying the formula to take only the last 4 digits each step.
This method of more direct computation is faster than the one laid out above if the exponent is not too large or if the length of the cycle is large (in this case it was).