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

4 Answers 4

Reset to default
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$
4
  • $\begingroup$ This is great! This willl save some computation time, when the numbers are getting even bigger :) $\endgroup$ Commented Jul 7, 2015 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$ Commented Jul 7, 2015 at 21:51
  • $\begingroup$ @dtldarek: Damn, you're right, I just remembered incorrectly. Wikipedia confirms. $\endgroup$ Commented Jul 7, 2015 at 21:59
  • 4
    $\begingroup$ @Cubinator73: Please unaccept, my answer is incorrect. $\endgroup$ Commented Jul 7, 2015 at 22:00
3
$\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$

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$
1
  • $\begingroup$ Also thank you for the tip with the modulus :) $\endgroup$ Commented Jul 7, 2015 at 21:48
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$
6
  • $\begingroup$ The same code gets the last million digits in less that four seconds. $\endgroup$ Commented Jul 8, 2015 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$ Commented Jul 8, 2015 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$ Commented Jul 8, 2015 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$ Commented Jul 8, 2015 at 0:42
  • $\begingroup$ Touche. New worlds to conquer - invent "ternary exponentiation". Then quartic, quintic, I think I'm going to like sextic... $\endgroup$ Commented Jul 8, 2015 at 0:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.