# Last 10 digits of the billionth fibonacci number?

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?

• You can certainly look at your recursion mod(N) for whatever N you choose...but I'd rethink the choice! Most choices of modulus fail to preserve last digit (12 = 0 mod(3), for example). But there is a good choice of N available to you. – lulu Jul 7 '15 at 21:29
• If you just want the last $10$ digits, you should reduce mod $10^{10}$. – alex.jordan Jul 7 '15 at 21:32
• @DavidC.Ullrich I didn't implement it recursively, but with a loop and three variables. – Cubi73 Jul 7 '15 at 21:33
• @DavidC.Ullrich Noone forces you to use recursion here ^^ The iterative approach should work quite well for such few iterations depending on the computing power. The iterative algorithm will have linear time complexity. – AlexR Jul 7 '15 at 21:35
• @DavidC.Ullrich $O(10^9) = O(1)$, using this notation in such a way is just confusing. – dtldarek Jul 7 '15 at 21:40

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.

• This is great! This willl save some computation time, when the numbers are getting even bigger :) – Cubi73 Jul 7 '15 at 21:47
• I thought the period of $F_n \bmod 10^k$ is $15\cdot 10^{k-1}$ for $k\geq 3$? – dtldarek Jul 7 '15 at 21:51
• @dtldarek: Damn, you're right, I just remembered incorrectly. Wikipedia confirms. – Zev Chonoles Jul 7 '15 at 21:59
• @Cubinator73: Please unaccept, my answer is incorrect. – Zev Chonoles Jul 7 '15 at 22:00

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}$

• Also thank you for the tip with the modulus :) – Cubi73 Jul 7 '15 at 21:48

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.

Given the following Mathematica code, based on identities found here

Clear[f];
f := 0;
f := 1;
f := 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 results in

1560546875


in less than a 0.000887 seconds.

The only evaluations it does are

f = 0
f = 1
f = 1
f = 2
f = 13
f = 21
f = 28657
f = 46368
f = 9030460994
f = 2490709135
f = 3274930109
f = 9082304280
f = 3331634818
f = 5364519011
f = 6891052706
f = 7684747991
f = 9674730645
f = 6983060328
f = 3041238690
f = 6494990027
f = 9095828930
f = 1802444783
f = 8092298210
f = 439009787
f = 3467735873
f = 3439061376
f = 3463150271
f = 8878860737
f = 976213368
f = 2499441093
f = 9190666621
f = 4288166885
f = 2169005442
f = 1145757919
f = 7067038114
f = 440574219
f = 6434013378
f = 4572218287
f = 1560546875

• The same code gets the last million digits in less that four seconds. – Mariano Suárez-Álvarez Jul 8 '15 at 0:03
• Ok, so my 1560546875 for the last ten digits of $F_{10^9}$ was right, great. Of course $10^9$ is a little small. I get the last ten digits of $F_{10^{10000}}$ in three or four seconds. With homemade Python, code implementing the hints in my answer. – David C. Ullrich Jul 8 '15 at 0:23
• I cannot get past $F_{10^{100000}}$ because the recursion is killing me. One could precompute the values of f which are needed, and compute the function in the reverse order,thereby avoiding all recursion, and that should get one much further. Maybe someone with the energy can try? – Mariano Suárez-Álvarez Jul 8 '15 at 0:37
• Notice that David is using essentially identities for the duplication of the argument while mine are for triplication — as 3 is larger than 2, this is in the long run much faster :-) – Mariano Suárez-Álvarez Jul 8 '15 at 0:42
• Touche. New worlds to conquer - invent "ternary exponentiation". Then quartic, quintic, I think I'm going to like sextic... – David C. Ullrich Jul 8 '15 at 0:46