Finding Fibonacci numbers
Good day!
Today I would like to talk about the method of resolving some recurrences and analyze a classic example on this topic.
Let's start by defining a recurrence formula:
Consider a problem that is formulated very simply: we need to find the Nth Fibonacci number modulo P, where N <= 10 ^ 15, P <= 10 ^ 9. As can be seen from the restrictions, adding the numbers by the trivial method in O (n) does not work, you need to come up with a faster algorithm, in this article we will focus on the operator method with the asymptotic behavior of O (log N). Suppose we have a column vector , is the nth Fibonacci number, we will try to choose an operator such that equality holds . For Fibonacci numbers, it is easy to find the matrix of this operator, if we recall the recurrence formula , the matrix is , indeed . And given that our operator is suitable not only for the first Fibonacci numbers, but also for everyone, that is , we have. So we can calculate the answer by raising the matrix of our operator to the Nth power, for this we use the algorithm of logarithmic raising to a power. Here is the code written in java:
It remains only to give our answer:
Thanks for attention.
Today I would like to talk about the method of resolving some recurrences and analyze a classic example on this topic.
Let's start by defining a recurrence formula:
A recurrence formula is a species formula expressing each member of a sequence through previous members. 
Consider a problem that is formulated very simply: we need to find the Nth Fibonacci number modulo P, where N <= 10 ^ 15, P <= 10 ^ 9. As can be seen from the restrictions, adding the numbers by the trivial method in O (n) does not work, you need to come up with a faster algorithm, in this article we will focus on the operator method with the asymptotic behavior of O (log N). Suppose we have a column vector , is the nth Fibonacci number, we will try to choose an operator such that equality holds . For Fibonacci numbers, it is easy to find the matrix of this operator, if we recall the recurrence formula , the matrix is , indeed . And given that our operator is suitable not only for the first Fibonacci numbers, but also for everyone, that is , we have. So we can calculate the answer by raising the matrix of our operator to the Nth power, for this we use the algorithm of logarithmic raising to a power. Here is the code written in java:
Copy Source  Copy HTML private static long getFibb(int n) {
 long a11 = 1, a12 = 1, a21 = 1, a22 = 0; //матрица оператора
 long r11 = 1, r12 = 0; //векторстолбец результа
 long q11 = 0, q12 = 0, q21 = 0, q22 = 0; //вспомогательная матрица при перемножении
 while (n > 0) {
 if ((n&1)==1) {
 q11 = (r11 * a11 + r12 * a21) % MOD;
 q12 = (r11 * a12 + r12 * a22) % MOD;
 r11 = q11;
 r12 = q12;
 }
 q11 = (a11 * a11 + a12 * a21) % MOD;
 q12 = (a11 * a12 + a12 * a22) % MOD;
 q21 = (a21 * a11 + a22 * a21) % MOD;
 q22 = (a21 * a12 + a22 * a22) % MOD;
 a11 = q11;
 a12 = q12;
 a21 = q21;
 a22 = q22;

 n >>= 1;
 }
 return r12; //возвращаем Fn
 }
It remains only to give our answer:
Copy Source  Copy HTML out.println(getFibb(N));
Thanks for attention.