二进制快速幂

2023-08-06

二进制快速幂

二进制快速幂（简称BE）是一种可以加速幂运算计算的技术。对于朴素的幂运算 ，时间复杂度是 ，而使用二进制快速幂，时间复杂度降为 。
让我们从一个例子开始，

假设 是一个32位整数，这意味着最多我们只需要计算32次，并检查 是否包含在内。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int fastPower(int a, int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return a;
    }
    int base = a;
    int result = 1;
    while(exp > 0) {
        if ((exp & 1) == 1) {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return result;
}

矩阵快速幂

1
2
3
4
5
6
7
8
9
10
11
public Matrix matrixFastPower(Matrix A, int n) {
	Matrix ans = I;
	while(n)
	{
	    if(n & 1)
	        ans = ans * A;
	    A = A * A;
	    n >>= 1;
	}
	return ans;
}

矩阵快速幂主要用于线性递归计数问题，以及一些状态转移方程是线性递归关系的动态规划问题。有些计数问题可以通过手动推导小规模的n来观察模式，并猜测递归关系。如果这个递归关系是线性的，那么它可以转化为矩阵幂问题，并使用矩阵快速幂加速计算。