快速幂及矩阵快速幂

快速幂

场景：计算 $x^{14}$，如果直接算需要做14次乘法，使用快速幂算法，将 $x^{14}$ 拆分为 $x^{14}=x^{(1110{)}_2}=x^8\cdot x^4\cdot x^1$，只需做4+3=7次乘法。在实现时，循环计算$x^1,x^2,x^4,x^8$，当遇到1、4、8时就将结果累乘，判断方法是循环时对幂数 $n$ 右移，判断最后一位是否为1，为1则累乘结果。

矩阵快速幂

该算法同样可以用于矩阵的幂乘中，$A^{14}=A^8\times A^4\times A^1$，同理循环计算$A^1,A^2,A^4,A^8$，遇到1、4、8则将结果累乘。java实现代码如下。

public static void main(String[] args) {
    // 计算 M^n次幂
    int[][] M = new int[][]{{1, 1}, {0, 1}};
    int[][] res = new int[][]{{1, 0}, {0, 1}}; // 结果矩阵，初始为单位矩阵
    int n = 10; //幂数
    while (n != 0) {
        if ((n & 1) == 1)
            res = multi(M, res);
        M = multi(M, M);
        n >>= 1;
    }
}

public static int[][] multi(int[][] a, int[][] b) {
    int[][] r = new int[a.length][b[0].length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < b[0].length; j++) {
            int res = 0;
            for (int k = 0; k < a[0].length; k++)
                res += a[i][k] * b[k][j];
            r[i][j] = res;
        }
    }
    return r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25