Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
You can take the remainder after every step. –  Daniel Fischer Apr 4 at 15:00
    
@Daniel Fischer, I'm sorry, I understand correct, that you offer to calculate the Pisano period, and then I should use this period? –  Denis Apr 4 at 15:05
1  
No. If we denote the remainder of $F_n$ modulo $k$ by $R_n$, then we have the recurrence $$R_{n+2} \equiv F_{n+2} = F_{n+1}+F_n \equiv R_{n+1} + R_n \pmod{k}.$$ So you can compute $R_{n+2} = (R_{n+1}+R_n) \bmod k$. Of course, for large $n$ that's not so efficient. See that (and why) the same principle works for the matrix method. –  Daniel Fischer Apr 4 at 15:09
    
@Daniel Fischer, thank you for the information. –  Denis Apr 4 at 15:12
2  
Compute the matrix by repeated squaring, using arithmetic mod n. This will be very fast. –  Bill Dubuque Apr 4 at 15:18

1 Answer 1

up vote 2 down vote accepted

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$.
share|improve this answer
    
Also, if you are trying to find EVERY combination of $n$ and $k$, $n$ being $F_n$ and $k$ being $\mod k$, it would actually just be faster to set $k$ to a value, and start a Fibonacci sequence, then if the Fibonacci sequence is ever larger or equal to $k$, just subtract $k$. Then just restart the sequence for the next value of k. –  Dane Bouchie Jun 21 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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