6
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – lulu Jul 7 '15 at 21:29
  • $\begingroup$ If you just want the last $10$ digits, you should reduce mod $10^{10}$. $\endgroup$ – alex.jordan Jul 7 '15 at 21:32
  • 1
    $\begingroup$ @DavidC.Ullrich I didn't implement it recursively, but with a loop and three variables. $\endgroup$ – Cubi73 Jul 7 '15 at 21:33
  • 2
    $\begingroup$ @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. $\endgroup$ – AlexR Jul 7 '15 at 21:35
  • 1
    $\begingroup$ @DavidC.Ullrich $O(10^9) = O(1)$, using this notation in such a way is just confusing. $\endgroup$ – dtldarek Jul 7 '15 at 21:40
3
$\begingroup$

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.

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

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

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

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.

$\endgroup$
2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ The same code gets the last million digits in less that four seconds. $\endgroup$ – Mariano Suárez-Álvarez Jul 8 '15 at 0:03
  • $\begingroup$ 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. $\endgroup$ – David C. Ullrich Jul 8 '15 at 0:23
  • $\begingroup$ 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? $\endgroup$ – Mariano Suárez-Álvarez Jul 8 '15 at 0:37
  • $\begingroup$ 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 :-) $\endgroup$ – Mariano Suárez-Álvarez Jul 8 '15 at 0:42
  • $\begingroup$ Touche. New worlds to conquer - invent "ternary exponentiation". Then quartic, quintic, I think I'm going to like sextic... $\endgroup$ – David C. Ullrich Jul 8 '15 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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