How can I program the last digits of Fibonacci numbers?

Question

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.

Answer 1

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].

Answer 2

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

Answer 3

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}