整数快速幂与矩阵快速幂算法
时间:2021-10-9
参考文章:
矩阵快速幂基础讲解 - 林夕-梦 - 博客园 (cnblogs.com)
模板 | 整数快速幂 & 快速幂取模 - 简书 (jianshu.com)
整数快速幂（取模）、矩阵快速幂及其应用 - Reqaw - 博客园 (cnblogs.com)
首先,我们在这里假设读者已经有了基本的关于矩阵的相关知识,因为这样可以更好地去理解矩阵快速幂的思想.
1.整数快速幂
请注意,目前而言我们不去考虑幂指数为负数的情况
(1)我们先来看整数快速幂:
比如,我们要去计算X^8,一种初始的思路应该是这样的
int func(int x)
{
int sum=x;
for(int i=1;i<8;i++)
{
sum*=x;
}
}
在这里我们进行了七次乘法运算,那么有没有什么方法来简化运算呢?
试想一下,如果我们首先计算出X ^ 2,那么实际上x ^ 4=(x ^ 2)×(x ^ 2),再进而X ^ 8=(X ^ 4)×(X ^ 4),这样的话实际上我们只需要进行三次乘法运算就可以将对应的x^8结果计算出来了,可以在一定程度上降低算法的复杂度.
因此,整数快速幂的基本思想就是将幂指数进行一定程度的划分,用来简化运算.我们可以再拿x^11次方举例子,可以看到:
所以,当我们在计算a^b的时候.
上述公式有一些问题,应该是:
该算法模板如下:
int pow(int a,int b)//计算a^b
{
int res=1;
int base=a;//这个base指的是底数
while(b)
{
if(b&1)//如果当前检查的这一位为1
{
res*=base;
}
base*=base;//这个对应上述的那个修正之后的公式
b>>=1;//b右移一位
}
return res;
}
(2)快速幂取模算法
前置知识点:刚才所叙述的整数快速幂算法
这里我们考虑计算形如(a^b)mod c的情况,很显然如果我们直接去进行计算的很容易出现整型溢出的现象,这个时候我们就需要了解一下取模运算律:
请注意第四个公式,这是我们所需要重点关注的
也就是说,我们只要先计算出a%p的值,再进行幂运算,最后对结果取余即可,而幂运算是我们所熟悉的刚才所描述的整数快速幂
此时我们就可以写出如下的模板算法:
int mymod(int a,int b,int c) //这个函数用来计算a^b对c取模运算的结果,暂时不多考虑越界的问题
{
int tmp=a%c; //保存上述公式中的a%p的值,方便进行接下来的快速幂运算
int base=tmp;
int res=1;
while(b)//b是base的指数,这里面已经考虑了指数为0的情况
{
if(b&1)
{
res=(res*base)%c;//及时使用取模运算律,有效避免整型越界问题
}
base=(base*base)%c;//及时使用取模运算律,有效避免整型越界问题
b>>=1;
}
return res;
}
因为我们将2,4,8指数次进行了合并处理,所以直观理解这种整数快速幂算法的复杂度是O(logn),这里不进行严格的数学证明
2.矩阵快速幂
矩阵快速幂的思想与前面的整数快速幂基本一致,也是通过简化中间的运算过程来降低复杂度.
我们通过引入一道非常经典的求解斐波那契数的题目来展开叙述矩阵快速幂的方法:
509. 斐波那契数 - 力扣（LeetCode） (leetcode-cn.com)
所以,我们可以写出如下所示的代码:
class Solution {
public:
int fib(int n) {
if(n<2) return n;//进行边界判定
vector<vector<int> > m{{1,1},{1,0}};
vector<vector<int> > res=matrix_pow(m,n-1);//n-1是因为计算的时候已经有一个m作为最终结果了,也就是res初始值=m
return res[0][0];//从公式可以看出,最终的结果是M^n乘一个[1,0]T矩阵,因此实际上只要取(0,0)位置就可以了
}
vector<vector<int> > matrix_pow(vector<vector<int> >& m,int n)//这个函数用来对矩阵进行快速幂运算
{
vector<vector<int> > res{{1,0},{0,1}};//初始的时候就是上面式子中的M
while(n)
{
//核心部分,参考整数快速幂
if(n&1)
{
res=matrix_multiply(res,m);
}
m=matrix_multiply(m,m);//这个就相当于之前算法所写的base
n>>=1;
}
return res;
}
vector<vector<int> >matrix_multiply(vector<vector<int> >&a,vector<vector<int> >&b)//这个函数用来计算两个矩阵的乘积
{
vector<vector<int> > res{{0,0},{0,0}};
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
res[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
}
}
return res;
}
};
对于矩阵,我们用vector<vector<int>>来实现,本质其实类似于刚才的整数快速幂.
