Integer Fast Power (modular), Matrix Fast Power and Its Application

Summary:

In this paper, the integer fast power, matrix fast power and their applications are introduced, with the title as an example to show the use details.

 

We want to calculate the N-power of an integer x, x^n. The common method is continuous multiplication. Here we introduce an efficient algorithm for calculating power, the iterative square method.

Consider the method of accelerating the power operation first. If n=2^k, then x^n = ((x2)2)., that is, x^n can be obtained simply by squaring K times.Then we can think that if n is expressed as the sum of powers of 2, that is, x^n = 2k1 + 2k2 + 2k3..., then x^n = x2^k1 * x2^k2 * x2^k1..., you just need to calculate it while you are looking for x2^i.Finally, an algorithm for calculating the power of O(logn) is obtained.

For example, calculate x^22 = x^16 * x^4 * x^2, where 22's binary number is 10110, which means it needs to be squared three times over.The code is as follows:

 1 typedef long long ll;
 2 ll qpow(ll x, ll n) {
 3     ll res = 1;
 4     while(n) {
 5         if(n&1)
 6             res = res * x;    //If the lowest bit in binary is 1, multiply by x^(2^i) 
 7         x = x * x;            //take x square 
 8         n >>= 1;             //n/2
 9     }
10     return res;
11 }

In practical applications, it is sometimes necessary to solve x^n%mod.The code is as follows:

 1 typedef long long ll;
 2 ll qpow(ll x, ll n, ll mod) {
 3     ll res = 1;
 4     while(n) {
 5         if(n&1)
 6             res = res * x % mod;    //If the lowest bit in binary is 1, multiply by x^(2^i) 
 7         x = x * x % mod;            //take x square 
 8         n >>= 1;                    //n/2
 9     }
10     return res;
11 }

Take a look at an example: UVA 10006 Carmichael Numbers

To determine if it is a C-number, the following two conditions need to be met

1. Not a prime number.

2. For any 1<x<n, there are x^n and X congruent modules n.

The code is as follows:

 1 #include <cstdio>
 2 #include <cmath>
 3 typedef long long ll;
 4 
 5 ll qpow(ll x, ll n, ll mod) {
 6     ll res = 1;
 7     while(n) {
 8         if(n&1)
 9             res = res * x % mod;
10         x = x * x % mod;
11         n >>= 1; 
12     }
13     return res;
14 }
15 bool isprime(ll x) {
16     if(x == 0 || x == 1)
17         return 0;
18     ll k = (ll)sqrt(x);
19     for(ll i = 2; i < k; i++) {
20         if(x % i == 0)
21             return 0;
22     }    
23     return 1;
24 }
25 int main()
26 {
27     ll n;
28     while(scanf("%lld", &n) == 1 && n != 0) {
29         if(isprime(n)) {
30             printf("%lld is normal.\n", n);
31             continue;
32         }
33         ll i;
34         for(i = 2; i < n; i++) {
35             if(qpow(i, n, n) != i % n)
36                 break;
37         }
38         if(i == n) 
39             printf("The number %lld is a Carmichael number.\n", n);
40         else
41             printf("%lld is normal.\n", n);
42     }
43     return 0;
44 }

Now ask that the M-power of A^m, the power of A^m, of a matrix A^m, first multiply the two matrices, then know that the result of A^m must be a homogeneous matrix, and finally understand the integer fast power above.All that remains is to replace the integer with the matrix operation.The code is as follows:

 1 const int Matrix_size = 2
 2 struct Matrix {//Define Matrix 
 3     int x[Matrix_size][Matrix_size]; 
 4 }ans, res;
 5 /*
 6 Define the matrix multiplication, A * B, they are all square matrices of order n 
 7 */ 
 8 Matrix Mmul(Matrix A, Matrix B, int n) {
 9     Matrix tmp;
10     for(int i = 1; i <= n; i++) {
11         for(int j = 1; j <= n; j++) {
12             tmp.x[i][j] = 0;
13         }
14     } 
15     
16     for(int i = 1 ; i <= n; i++) {
17         for(int j = 1; j <= n; j++) {
18             for(int k = 1; k <= n; k++) {
19                 tmp.x[i][j] += A.[i][k] * B[k][j];
20             }
21         }
22     }
23     return tmp;
24 }
25 /*
26 Find the N-th power of res, n is the order of res 
27 */
28 void qmpow(int N, int n) {
29     for(int i = 1; i <= n; i++) {
30         for(int j = 1; j <= n; j++) {
31             res.x[i][j] = i == j ? 1 : 0;
32         }
33     }
34     
35     while(N) {
36         if(N&1)
37             ans = Mmul(ans, res);
38         res = Mmul(res, res);
39         N >>= 1;
40     }
41 }

Using the matrix fast power algorithm above, you can quickly solve the n-th power of a matrix. What is the use of finding the n-th power of a matrix?

1. Find the nth Fibonacci Number

According to the definition of Fibonacci number, F0 = 0 and F1 = 1;

                    Fn = Fn - 1 + Fn -2(n>=2).

Can be expressed as a matrix:

Further recursion to:

What you need here is the n-2 power of the right coefficient matrix, and then you can find f(n), the nth Fibonacci number, by substituting the first two terms.

Let's look at an example: HDU 6198 number number number

meaning of the title

Firstly, the definition of Fibonacci series is given.

 F0 = 0, F1 = 1;

 Fn = F n - 1 + F n - 2.

Give the definition of bad number again, give an integer k, if an integer n cannot consist of K arbitrary (repeatable) Fibonacci numbers, it will become a bad number.Now give k, ask what is the smallest bad number, answer 998244353 modeled.

Solving problems

Hard violence is not possible because the k given is very large.Look at the first few:

When k = 1, 4 = 5 - 1 = F(2 * 1 + 3) - 1;

When k = 2, 12 = 13 - 1 = F(2 * 2 + 3) - 1;

The problem becomes to solve the second * k + three Fibonacci numbers, and because K is so large, it needs to be solved with a matrix fast power.

By definition, the first two terms are 1 and 1, and the coefficient matrix is 1, 1, 1, 0. To find the nth term, we need to calculate the n-2 power of the coefficient matrix, and then multiply the first two terms to get F(n) and F(n-1).

The code is as follows:

 1 #include <cstdio>
 2 #include <cstring>
 3 typedef long long ll;
 4 const int mod = 998244353;
 5 struct Matrix {
 6     ll x[2][2];
 7 };
 8 Matrix Mmul(Matrix a, Matrix b) {
 9     Matrix tmp;
10     memset(tmp.x, 0, sizeof(tmp.x));
11     for(int i = 0; i < 2; i++) {
12         for(int j = 0; j < 2; j++) {
13             for(int k = 0; k < 2; k++) {
14                 tmp.x[i][j] = (tmp.x[i][j] + a.x[i][k] * b.x[k][j] % mod) % mod;
15             }
16         }
17     }
18     return tmp;
19 }
20 Matrix Mqpow(Matrix a, ll n) {
21     Matrix tmp;
22     for(int i = 0; i < 2; i++) {
23         for(int j = 0; j < 2; j++) {
24             tmp.x[i][j] = i == j ? 1 : 0;
25         }
26     }
27     
28     while(n) {
29         if(n&1)
30             tmp = Mmul(tmp, a);
31         a = Mmul(a, a);
32         n >>= 1;
33     }
34     return tmp;
35 }
36  int main()
37 {
38     ll k;
39     while(scanf("%lld", &k) != EOF) {
40         Matrix st;
41         st.x[0][0] = 1; st.x[0][1] = 1;
42         st.x[1][0] = 1; st.x[1][1] = 0;
43         
44         Matrix init;
45         init.x[0][0] = 1; init.x[0][1] = 0;
46         init.x[1][0] = 1; init.x[1][1] = 0;
47         
48         st = Mqpow(st, 2 * k + 1);
49         st = Mmul(st, init);
50         printf("%lld\n", (st.x[0][0] - 1 + mod) % mod);
51     }    
52     return 0;    
53 }

There are other important applications of the fast power of matrices, limited in time, to be supplemented later.

This is where the introduction and application of the fast power of matrices are exemplified. The knowledge of linear algebra is used. Appropriate recursive formulas should be found when solving the problem, and then fast power optimization of matrices is used.

Posted on Tue, 21 Apr 2020 13:03:28 -0700 by Floydian