Matrix fast power notes

Matrix fast power

Conventional exponentiation

seek $a^n$ Value , If you use pure for loop , To cycle n Second ride a.
Time complexity ：O(n)
Spatial complexity ：S(1)

recursive

Similar to dichotomy .
example ：
$$a^{57}=\{\begin{array}{cc}{a}^{28}& \{\begin{array}{cc}{a}^{14}& \{\begin{array}{cc}{a}^7& \{\begin{array}{cc}{a}^3& \{\begin{array}{c}a\\ a\\ a\end{array}\\ a^3& \\ a& \end{array}\\ a^7& \end{array}\\ a^{14}& \end{array}\\ a^{28}& \\ a& \end{array}$$
Just divide the power by two , Take the square （ cube a） that will do .
$$\begin{gathered} a^{2k}=\{\begin{array}{l}{a}^k\\ a^k\end{array} \\ {a}^{2k+1}=\{\begin{array}{l}{a}^k\\ a^k\\ a\end{array} \end{gathered}$$
Time complexity ：O(logn)
Spatial complexity ：O(logn)

Fast power

Yes n Binary decomposition .
example ： solve $a^{57}$

1. take 57 Change to binary 111001, For binary is 1 Bit value of , namely
   $a^{57}=a^1\ast a^8\ast a^{16}\ast a^{32}$
2. Find the value of each binary ：
   1. initialization a = 1
   2. From the bottom , Each binary value is a *= a
3. Convert binary to 1 Multiply the bit values of .

public int MOD = 1000000007;

public static int qp(int a, int n) {
    
    int ans = 1;
    while (n > 0) {
    
        if ((n&1) == 1) {
    
            ans = (int) (((long)ans * a) % MOD);
        }
        a = (int) (((long)a * a) % MOD);
        n >>= 1;
    }
    return ans;
}

Matrix fast power

Matrix multiplication to solve recursive state transition

Take the Fibonacci sequence as an example

$$f(n)=\{\begin{array}{ll}f(n-1)+f(n-2)& n>1\\ 1& 0<=n<=1\end{array}$$

Using matrix multiplication
$$\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]\left[\begin{array}{c}f(n-2)\\ f(n-1)\end{array}\right]=\left[\begin{array}{c}f(n-1)\\ f(n)\end{array}\right]$$

Set the matrix to A
$$A=\left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]$$
Then the final matrix can be decomposed into
$$\left[\begin{array}{c}f(n)\\ f(n+1)\end{array}\right]=A^n\left[\begin{array}{c}f(0)\\ f(1)\end{array}\right]$$

Determine the matrix A

Any state transition equation can determine the matrix A, example ：
$$\begin{gathered} f(n)=3f(n-1)+6f(n-2)-7f(n-3) \\ \left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ -7& 6& 3\end{array}\right]\left[\begin{array}{c}f(0)\\ f(1)\\ f(2)\end{array}\right]=\left[\begin{array}{c}f(1)\\ f(2)\\ f(3)\end{array}\right] \\ A=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ -7& 6& 3\end{array}\right] \end{gathered}$$

java Code implementation

public static int[][] matrix_qp(int n) {
    
    // Take the Fibonacci series for example 
    // matrix A
    //0 1
    //1 1
    int[][] A = new int[2][2];
    A[0][0] = 0;
    A[0][1] = A[1][0] = A[1][1] = 1;

    // Fibonacci sequence 0 1 matrix 
    //1 0
    //1 0
    int[][] F = new int[2][2];
    F[0][0] = F[1][0] = 1;
    F[0][1] = F[1][1] = 0;

    return matrix_multi(matrix_mi(A, n), F);
}

public static int[][] matrix_multi(int[][] a, int[][] b) {
    
    int[][] ans = new int[2][2];
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                ans[i][j] += a[i][k] * b[k][j];
    return ans;
}

public static int[][] matrix_mi(int[][] a, int n) {
    
    int[][] ans = new int[2][2];
    ans[0][0] = ans[1][1] = 1;
    while(n > 0) {
    
        if ((n&1) == 1)
            ans = matrix_multi(ans, a);
        a = matrix_multi(a, a);
        n >>= 1;
    }
    return ans;
}

public static void show_matrix(int[][] a) {
    
    System.out.println("Matrix");
    for (int i = 0; i < a.length; ++i) {
    
        for (int j = 0; j < a[i].length; ++j)
            System.out.print(a[i][j] + " ");
        System.out.println();
    }
}

The above code does not perform modulo operation .

When doing modular operation, you should pay attention to ：

When the matrix contains negative numbers , To ensure that the modulus is large and 0

(a%c - b%c + c)%c

Reference material

Matrix fast power - b standing