Last 10 digits of the billionth fibonacci number?

Question

I want to compute the last ten digits of the billionth fibonacci number, but my notebook doesn't even have the power to calculate such big numbers, so I though of a very simple trick: The carry of addition is always going from a less significant digit to a more significant digit, so I could add up the fibonacci numbers within a boundary of 8 bytes ($0$ to $18\cdot10^{18}$) and neglect the more significant digits, because they won't change the less significant digits anymore.

So, instead of using $$F_{n+1}=F_n+F_{n-1}$$ to compute the whole number, I would use $$F_{n+1}=(F_n+F_{n-1})\operatorname{mod}18\cdot10^{18}$$ to be able to keep track of the last 10 digits.

Here my question: Can I do this?

Answer 1

EDIT: The period of repetition I claimed was incorrect. Thanks to @dtldarek for pointing out my mistake. The relevant, correct statement would be

For $n\geq 3$, the last $n$ digits of the Fibonacci sequence repeat every $15\cdot 10^{n-1}$ terms.

So for the particular purpose of getting the last $10$ digits of $F_{1{,}000{,}000{,}000}$, this fact doesn't help.

---

For $n\geq 1$, the last $n$ digits of the Fibonacci sequence repeat every $60\cdot 5^{n-1}$ terms. Thus, the last $10$ digits of $F_{1{,}000{,}000{,}000}$ are the same as the last $10$ digits of $F_{62{,}500{,}000}$ because $$1{,}000{,}000{,}000\equiv 62{,}500{,}000\bmod \underbrace{117{,}187{,}500}_{60\cdot 5^9}$$ This will help make the problem computationally tractable.

Answer 2

You idea is very good, but the digits are only preserved in every iteration iff the modulus is a multiple of $10^{10}$. In other words, look at $$\tilde{F}_{n+1} = (\tilde{F}_n + \tilde{F}_{n-1}) \bmod 10^{10}$$ instead. $\tilde{F}_{1000000000}$ will then consist exactly of the last $10$ digits of $F_{1000000000}$

Answer 3

A hint regarding some of the comments: Say $$X_n=\left[\begin{array}{}F_n\\F_{n+1}\end{array}\right].$$ Then $$X_{n+1}=AX_n$$for a certain $2\times 2$ matrix $A$. So you just have to calculate $A^n$.

Why would you go to the trouble of implementing $2\times 2$ matrix multiplication? Because then you can use "fast exponentiation", giving the result in time $\log(n)$. An example giving the idea of that: You'd calculate $A^{11}$ as $$A^{11}=AA^2A^8,$$after finding $A^{2^k}$ for $1\le k \le 3$. Which you do very quickly using $$A^{2^{k+1}}=\left(A^{2^k}\right)^2$$in a loop. A very short loop...

Oh. Didn't realize that's what the link "indeed" went to. Anyway there it is.

Answer 4

Given the following Mathematica code, based on identities found here

Clear[f];
f[0] := 0;
f[1] := 1;
f[2] := 1;
f[n_ /; Mod[n, 3] == 0] := f[n] = With[{m = n/3}, 
    Mod[5 f[m]^3 + 3 (-1)^m f[m], 10^10]];
f[n_ /; Mod[n, 3] == 1] := f[n] = With[{m = (n - 1)/3}, 
    Mod[f[m + 1]^3 + 3 f[m + 1] f[m]^2 - f[m]^3, 10^10]];
f[n_ /; Mod[n, 3] == 2] := f[n] = With[{m = (n - 2)/3}, 
    Mod[f[m + 1]^3 + 3 f[m + 1]^2 f[m] + f[m]^3, 10^10]];

evaluating f[1000000000] results in

1560546875

in less than a 0.000887 seconds.

The only evaluations it does are

f[0] = 0
f[1] = 1
f[2] = 1
f[3] = 2
f[7] = 13
f[8] = 21
f[23] = 28657
f[24] = 46368
f[69] = 9030460994
f[70] = 2490709135
f[209] = 3274930109
f[210] = 9082304280
f[627] = 3331634818
f[628] = 5364519011
f[1881] = 6891052706
f[1882] = 7684747991
f[5645] = 9674730645
f[5646] = 6983060328
f[16935] = 3041238690
f[16936] = 6494990027
f[50805] = 9095828930
f[50806] = 1802444783
f[152415] = 8092298210
f[152416] = 439009787
f[457247] = 3467735873
f[457248] = 3439061376
f[1371742] = 3463150271
f[1371743] = 8878860737
f[4115226] = 976213368
f[4115227] = 2499441093
f[12345679] = 9190666621
f[12345680] = 4288166885
f[37037037] = 2169005442
f[37037038] = 1145757919
f[111111111] = 7067038114
f[111111112] = 440574219
f[333333333] = 6434013378
f[333333334] = 4572218287
f[1000000000] = 1560546875