Fibonacci series mod a number

Question

I'm trying to write a program with an input of numbers $n$ and $k$ (where $n<10^{20}$ and $k<10^9$), where I compute fib[n] % k. What is a good FAST way of computing this?

I have read many articles on this topic. At first I wanted to use a Pisano period. However, there is no formula to calculate the Pisano period.

Then I wanted to calculate Fibonacci number. However, it does not fit into any type of standard data type (Fibo(1000000000000000000) has about 208987640249978720 decimal).

I see this matrix formula: $$\begin{pmatrix} 1&1\\\ 1&0 \end{pmatrix}^n= \begin{pmatrix} F_{n+1}&F_n\\\ F_n&F_{n-1} \end{pmatrix} $$

However, according to the second issue, I can not save the result.

I feel that I am missing some theory. I'll be glad for any help.

Answer 1

The fastest way is somewhere around $O(\log^2 n)$. It is highly related to the matrix, but uses a little "recycling". This examples how to find $F_k$ I will explain the modding last.

Take note of these basic properties of Fibonacci numbers:

• $F_{2k+1} = 4F_k^2 - F_{k-1}^2 + 2(-1)^k$
• $F_{2k-1} = F_k^2 + F_{k-1}^2$
• $F_{2k} = F_{2k+1} - F_{2k-1}$

With these properties we can double the position of a Fibonacci number's index, instead of going one by one, which makes it so much faster.

Steps:

1. Convert the $n$ (as in $F_n$) to binary. Ex: The $11th$ Fibonacci number, so $11$ in binary is $1011_2$
2. Have $F_0 = 0$ and $F_1 = 1$, and let $k = 1$ to start. Lastly start from the $2nd$ binary digit place from the left. In this case it is the $0$.
3. Calculate $(F_{2k-1}, F_{2k},F_{2k+1})$ using the formulas listed above.
4. If the digit place is $0$ use $(F_{2k-1}, F_{2k})$, if it is odd use $(F_{2k},F_{2k+1})$ for the next values you substitute for $(F_{k-1},F_k)$. Now shift the digit place one to the right.
5. Repeat steps 3-4 until all the digits places are gone, and you will get your final Fibonacci number which will end up being whatever value you end up for your next $F_k$.

Example:

1. To find $F_{13}$, $n = 13$ in binary is $1101_2$
2. Starting from $(F_0,F_1) = (0,1)$, the next value sets are: $(1^2+0^2,F_{2k+1}-F_{2k-1},4(1)^2-0^2-2) = (1, 2-1, 2) = (1,1,2)$
3. Because the $2nd$ digit from the left is a $1$, we will use $(1,2)$ for our next values.
4. Next values: $(5,8,13)$. $3rd$ digit from the left is a $0$ so we use (5,8).
5. Next values: $(89,144,233)$. $4th$ digit form the left is a $1$ so we use $(144,233)$, but that was the last digit place, so our answer is $F_k$, which is $233$.

Optimizations:

• Calculate $F_k^2$ and $F_{k-1}^2$ first. Perform the mod after calculating them, then recycle them when calculating $F_{2k+1}$ and $F_{2k-1}$. This ensures that multiplication is at most $\log_2 m + 2$ digits long. Where $m$ is the modulus.
• Because $2(-1)^k$ is $-2$ when $k$ is odd, and $+2$ when $k$ is even, Whatever digit place read to determine what values to use for $(F_{k-1},F_k$), also predicts which $+2$ or $-2$ to use. So in our example because we read a $1$ in the $2nd$ place, we would use $-2$ for the next $2(-1)^k$. And because we read a $0$ in the $3rd$ place, we would use $+2$ for the $2(-1)^k$ after. So use a $+2$ if you read a $0$, and use $-2$ if you read a $1$.