# 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:
 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 N-th power, for this we use the algorithm of logarithmic raising to a power. Here is the code written in java:
`Copy Source | Copy HTMLprivate 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 HTMLout.println(getFibb(N)); `

Thanks for attention.