Geekly Articles each Day
📜 ⬆️ ⬇️

Finding Fibonacci numbers

Good day!
Today I would like to talk about the method of resolving some recurrences and analyze the classic example on this topic.
Let's start with the definition of a recurrent formula:
Recurrent Formula - Formula expressing each term in the sequence through previous members.

Consider a problem that is formulated very simply: we need to find the N-th Fibonacci number modulo P, where N <= 10 ^ 15, P <= 10 ^ 9. As can be seen from the limitations, adding numbers by the trivial method behind O (n) will not work, you need to come up with a faster algorithm, in this article we will discuss the operator method with the asymptotics O (log N). Suppose we have a column vector , - n-th Fibonacci number, we will try to pick up the operator such that equality will be performed . For Fibonacci numbers it is easy to find the matrix of this operator, if we recall the recurrent formula the matrix is ​​equal to really . And given that our operator is suitable not only for the first Fibonacci numbers, but 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 logarithmic exponentiation algorithm. 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 }
  1. 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 }
  2. 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 }
  3. 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 }
  4. 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 }
  5. 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 }
  6. 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 }
  7. 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 }
  8. 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 }
  9. 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 }
  10. 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 }
  11. 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 }
  12. 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 }
  13. 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 }
  14. 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 }
  15. 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 }
  16. 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 }
  17. 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 }
  18. 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 }
  19. 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 }
  21. 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 }
  22. 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 }
  23. 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 }
  24. 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
  1. out .println (getFibb (N));

Thanks for attention.

')

Source: https://habr.com/ru/post/91296/

More articles:


All Articles