Fork me on GitHub

快速幂算法的实现

发表于 | 分类于
字数统计: 697 字 | 阅读时长 ≈ 3 分钟

问题描述

首先我们来看一道题目:

有三个整数a,b,m，求a^b%m的值。
(注: a^b意为a的b次方)

这道题目一开始看上去很简单，只要写一个简单的循环就能够搞定。

1
2
3
4
5
6
7
long long f(long long a,long long b,long long m){
	long long res=1;
	for(long long i=1;i<=b;i++){
		res=res*a;
	}
	return res%m;
}

如果你这么写，那你就肯定没有考虑到数据范围，比如说f(2,200,3)，返回的结果会是0。
原因很简单，这样res变量会非常大，以至于超出了long long类型数据范围。
那么，我们应该如何解决这个问题呢？这里我们需要运用取模运算的性质：
$ (a + b) \mod p = (a \mod p + b \mod p) \mod p $
$ (a - b) \mod p = (a \mod p - b \mod p ) \mod p $
$ (a \times b) \mod p = (a \mod p \times b \mod p) \mod p $
将上面的代码稍作修改：

1
2
3
4
5
6
7
8
long long f(long long a,long long b,long long m){
	long long res=1;
	for(long long i=1;i<=b;i++){
		res=res*a;
		res=res%m; //加入一行
	}
	return res%m;
}

再次运行程序，f(2,200,3)返回的结果是1，这次是正确的。
但是，这个程序运行起来很慢，是不可取的。

快速幂算法

我们应该都知道，$ a^{m+n}=a^{m} \times a^{n} $ ,$ a^{m \times n}=(a^m)^n $。快速幂的思想就是，将幂的指数用二进制表示，分割成更小的任务。
例如，计算$2^{12}$，首先将指数12转为二进制数1100，然后按位乘以权值，分成8和4两个数。
$2^{12} = 2^{8} \times 2^{4} $
$2^1=2$
$2^2=(2^1)^2=4$
$2^4=(2^2)^2=16$
$2^8=(2^4)^2=256$
即$2^{12}=256 \times 16=4096$
观察上述算式，可以总结出：

  1. 当指数为偶数时，$a^b=(a^{b/2})^2$
  2. 当指数为奇数时，由于b/2余1，应当再乘以底数，即$a^b=(a^{b/2})^2 \times a$

我们用递归实现以上过程，加上每一步的取模：

1
2
3
4
5
6
long long ksm(long long a,long long b,long long m){
	if(b==0)return 1;
	long long res=ksm(a,b/2,m)%m;
	if(b%2==1)return ((res*res)%m*a%m)%m; //指数为奇数
	else return (res*res)%m; //指数为偶数
}

代码优化

非递归式通常会比递归要快一点，同时我们使用位运算，可以使速度大幅提升。
改进后的最终代码如下：

1
2
3
4
5
6
7
8
9
long long ksm(long long a,long long b,long long m){
	long long res=1;
	while(b>0){
		if(b&1)res=res*a%m;
		a=(a*a)%m;
		b>>=1;
	}
	return res%m;
}

具体程序运行速度可以自行对比，可以说，最终优化的快速幂可以极其快速地处理很大的数据。