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 HTML
    1. private static long getFibb(int n) {
    2.     long a11 = 1, a12 = 1, a21 = 1, a22 =  0; //матрица оператора
    3.     long r11 = 1, r12 =  0; //вектор-столбец результа
    4.     long q11 =  0, q12 =  0, q21 =  0, q22 =  0; //вспомогательная матрица при перемножении
    5.     while (n >  0) {
    6.         if ((n&1)==1) {
    7.             q11 = (r11 * a11 + r12 * a21) % MOD;
    8.             q12 = (r11 * a12 + r12 * a22) % MOD;
    9.             r11 = q11;
    10.             r12 = q12;
    11.         }
    12.         q11 = (a11 * a11 + a12 * a21) % MOD;
    13.         q12 = (a11 * a12 + a12 * a22) % MOD;
    14.         q21 = (a21 * a11 + a22 * a21) % MOD;
    15.         q22 = (a21 * a12 + a22 * a22) % MOD;
    16.         a11 = q11;
    17.         a12 = q12;
    18.         a21 = q21;
    19.         a22 = q22;
    20.  
    21.         n >>= 1;
    22.     }
    23.     return r12; //возвращаем Fn
    24. }

    It remains only to give our answer:
    Copy Source | Copy HTML
    1. out.println(getFibb(N));

    Thanks for attention.

    Also popular now: