11
$\begingroup$

Is there a way to compute the last digits of an arbitrarily large Fibonacci number?

For the $10^n$th Fibonacci number, we can just find the $2^n$-th Fibonacci number (if that isn't too large) $\bmod n$, and then use the Chinese remainder theorem, since we know it is a multiple of $5^n$ (the Pisano period is $4\cdot5^n$ which divides $10^n$) to find the last $n$ digits.

However, is there a way to find the last digits of the $n$-th Fibonacci number efficiently if $n$ is not a power of $10$?

A way to program this would probably require a way to reference the last two intermediate values and add them together, and then taking the result $\bmod 10^d$. Taking the value $\bmod 3\times10^d$ would be preferred because this allows the calculation to be iterated.

$\endgroup$
17
$\begingroup$

This can be computed almost instantaneously due to one curious property of the Fibonacci numbers: Their sequence is periodic modulo any modulus $m$. These periods are known as Pisano periods $\pi(m)$. For 10 the period is 60. Therefore we have

FibLastDigit[n_] := Mod[Fibonacci[Mod[n, 60]], 10]

This is presumably faster than any other method. Even faster would be to precompute the sequence from 1 to 60. In this case the problem is to merely compute Mod[n,60].

$\endgroup$
5
  • 3
    $\begingroup$ I'm not sure if it's a curious property — the sequence is described by a recurrence relation on the previous two terms, and there are only a finite number of pairs of residues mod any given base, so you can't avoid repeating a pair eventually :) $\endgroup$
    – hobbs
    Aug 14 '20 at 7:40
  • $\begingroup$ @hobbs: Right, the period can't be any greater than $m^2$ by that argument ($m^2 - 1$, really, since the residue pair $(0,0)$ always maps to itself in any base.) $\endgroup$ Aug 14 '20 at 17:25
  • $\begingroup$ Thanks for the link to Pisano periods above! I "discovered" this property of Fibonacci numbers during a boring meeting once, and it's nice to know that it's already been named & explored. $\endgroup$ Aug 14 '20 at 17:27
  • $\begingroup$ Since this became popular, here are some notes: 1. Pisano periods were discussed earlier here. 2 The current solution as implemented only does the last digit, and is less general than the other answers.3. If you look at OEIS, to extend the Pisano period approach to the general "last $n$ digits" problem, you will find that e.g. for $n=8$, you need to $\bmod 150,000,000$ your original number before feeding to Fibonacci[], which of course you can skip if the original input is less than that. ;) $\endgroup$ Aug 14 '20 at 23:07
  • $\begingroup$ @MichaelSeifert why is it nice to know that? Because you wouldn't want to have to deal with the fame and fortune of being the first to discover it? $\endgroup$
    – phoog
    Aug 15 '20 at 23:15
11
$\begingroup$

Using an undocumented function (see this as well) to implement the matrix form of the Fibonacci recurrence (see this as well):

With[{n = 1003, m = 8}, 
     Algebra`MatrixPowerMod[{{1, 1}, {1, 0}}, n - 1, 10^m][[1, 1]]]
   96035877

Mod[Fibonacci[1003], 1*^8]
   96035877
$\endgroup$
8
$\begingroup$

I combined MatrixPowerMod from Bressoud & Wagon's book, A Course in Computational Number Theory, with a Fold formulation from @J.M.'s, to give FibonacciMod as follows. This code is what is essentially contained in the undocumented Algebra`MatrixPowerMod function found by @J.M.'s (+1).

FibonacciMod[0, m_] = 0;

FibonacciMod[n_, m_] :=
   Fold[
      If[#2 == 1, Mod[#1.#1.{{0, 1}, {1, 1}}, m], Mod[#1.#1, m]] &, {{0, 1}, {1, 1}},
      Rest[IntegerDigits[n, 2]]][[1, 2]]

FibonacciMod[n,m] is slower than Mod[Fibonacci[n],m] for small n, but much faster for large n. To echo J.M.'s example,

FibonacciMod[1003],10^8]

96035877

Also,

AbsoluteTiming[FibonacciMod[10^20-1, 10^10]]

{0.00323, 2900390626}

$\endgroup$

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.