【Algorithm】矩阵快速幂

发表于 | 分类于 ， | | 阅读次数:

整数快速幂

为了引出矩阵的快速幂，以及说明快速幂算法的好处，我们可以先求整数的幂。

如果现在要算X^8：则 X*X*X*X*X*X*X*X 按照寻常思路，一个一个往上面乘，则乘法运算进行7次。

(X*X)*(X*X)*(X*X)*(X*X)

这种求法，先进行乘法得X^2,然后对X^2再执行三次乘法，这样去计算，则乘法运算执行4次。已经比七次要少。

所以为了快速算的整数幂，就会考虑这种结合的思想。

现在要考虑应该怎么分让计算比较快。接下来计算整数快速幂。例如：X^19次方。

19的二进制为：1 0 0 1 1 。

由(X^m)*(X^n) = X^(m+n)

则X^19 = (X^16)*(X^2)*(X^1)

1
2
3
4
5
6
7
8
9
10
11
12
int quickPow(int x, int n)
{
    int res = 1;
    while(n){
        if(n & 1){
            res *= x;
        }
        x = x * x;
        n = n >> 1;
    }
    return res;
}

矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
int c[N][N];
void multi(int a[][], int b[][], int n) // n*n
{
    memset(c, 0, sizeof(c))
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

矩阵快速幂

把整数乘法中的乘换成矩阵乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Matrix{
    int m[maxn][maxn];
};

Matrix quickPow(Maxtrix a, int n)
{
    Matrix res;
    //res应初始化为单位矩阵，及对角线为1其它为0
    while(n){
        if(n & 1){
            res = multi(res, a);
        }
        a = multi(a, a);
        n = n >> 1;
    }
}