快速幂算法
计算 。
可以看到,原本需要12次乘法的计算,现在只需要5次乘法了。
将 的上标全写为二进制
可以看到,完全展开之后, 的上标组成的二进制串正是 的二进制串。真正进行计算时, 可以省略。因此,用快速幂算法计算 时,需要进行 次平方运算和 次乘法运算,其中 是 的二进制位数, 是 的二进制中的 的个数。平方运算其实就是乘法运算,因此,需要进行的乘法运算次数总计为 ,介于 倍 之间。因此,快速幂算法的时间复杂度为
快速幂算法还可以像下面这样表述,时间复杂度与上面的一致。不过测试表明,比上面的要慢。
可以看到,尽管大数乘法并非 ,快速幂算法依然要比普通算法快得多。
计算机快速计算2^N是如何实现的?
计算乘方是有快速算法的,并不是一个一个蛮力乘上去的。比如想算2^10000,计算机先算2^5000,再算一次平方,即两个数的乘法。而为了计算2^5000,计算机会先算2^2500再算一次平方。这个算法叫快速幂算法,对于2^N的计算,如果认为每次乘法的时间复杂度是O(1)的话,那整体的时间复杂度只有O(logN)级别。
一般来说,为了实现快速幂算法,首先把指数做二进制表示,比如你要算A的23次方,可以把23分解为16+4+2+1。然后计算B=A^2,C=B^2=A^4,D=(C^2)^2=A^16。最终结果为ABCD相乘。
但这里乘法的复杂度并不是O(1),因为它是无限精度的,也就是所谓的大数乘法。大数乘法也有很多算法,最朴素的,类似手算的方法,复杂度是O(N^2),其他一些方法有分治法,复杂度O(N^1.58),FFT方法,复杂度O(N logN loglogN)等。快速幂的O(logN)次大数乘法中,最复杂的只有最后一次,也就是2^5000的那次,前面的复杂度几何级数衰减,所以整体复杂度也就是最后一次计算的复杂度。如果你用FFT方法的话,复杂度也就是比线性多了一点点,一般计算机上随便算算就出来了。
CPU没有全速运行是因为这个程序只用了1个核心在做计算,而你显示的是总的使用率,所以大概会保持在四分之一的水平。
是否用到了移位操作涉及Python大数运算的具体设计,我不是很懂就不多讲了。但原理上讲也是很有可能的,如果用比特串存储大数的话,那么计算2^N只需要在数组的第N位设置一个1,其余设置为0即可,那么转换到十进制是这段代码中最消耗计算量的部分。
快速幂算法原理
快速幂
顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log2N), 与朴素的O(N)相比效率有了极大的提高。
中文名
快速幂
外文名
Fast Power
时间复杂度
log(n)
性质
快速算底数的n次幂
快速
导航
实现
代码比较
原理
快速幂算法的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。
让我们先来看一个简单的例子:
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
9^5=(9^4)*(9^1)
9^5=(9^4)*(9^1)
9^5=(6561^1)*(9^1)
以下以求a的b次方来介绍[1]
把b转换成二进制数。
该二进制数第i位的权为
例如

11的二进制是1011

因此,我们将a11转化为算
实现
快速幂可以用位运算来实现
b and 1{也就是取b的二进制***位(即第0位) 判断b是否为奇数,是则为1}
b shr 1{就是去掉b的二进制***位(即第0位)}
C++实现为
b 1//取b二进制的***位,判断和1是否相同,相同返回1,否则返回0,可用于判断奇偶
b1//把b的二进制右移一位,即去掉其二进制位的***位
以下为pascal的实现:
var a,b,n:int64;
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1; y:=a;
while b0 do begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;{这里用了一个技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理
a^(2^(i-1))*a^(2^(i-1))=a^(2^i)
而且一般情况下a*b mod c =(a mod c)*(b mod c) mod c}
b:=b shr 1;{去掉已经处理过的一位}
end;
exit(t);
end;
begin
read(a,b,n);{n是模}
writeln(f(a,b,n));
end.
[1]
以下为C的实现,为了方便与pascal的对照,变量全部与上面相同.可以对照查看。
递归版:[2]
ll pow(ll a,ll i){
if (i==0) return 1;
int temp=pow(a,i1);
temp=temp*temp%MOD;
if (i1) temp=(ll)temp*a%MOD;
return temp%MOD;
}
非递归版:
ll f(ll a,ll b,ll n){
int t,y;
t=1; y=a;
while (b!=0){
if (b1==1) t=t*y%n;
y=y*y%n; b=b1;
}
return t;
}
如何计算快速幂,比如 x^100000000次方,直接循环很慢。。谢谢了
因为 x^n = (x^(n/2))^2
根据这个公式,可以在 log2N时间内算出乘法幂
递归算法:
int pow(int x,int n)
{
if(n==1) return x;
else if(n1) //n is odd
{
return x*pow(x,n/2);
}
else
{
return pow(x,n/2);
}
}
非递归算法:
int pow(int x,int n)
{
int temp(x),res(1);
while(n)
{
if(n1)
{
res *= temp;
}
temp *= temp;
n=1;
}
return res;
}
快速幂是什么?
解释一下a^b mod c:
a^b mod c=a^(f[0]*2^0+f[1]*2^1+f[2]*2^2...f[t]*2^t)
因为 a*b mod c= ((a mod c) *b) mod c
所以
a^b mod c=(((f[0]*2^0 mod c)*f[1]*2^1 mod c)......*f[t]*2^t mod c)
用这种方法解决a^b mod c 时间复杂度
2^t=b2^(t+1)
t=log(2)bt+1
因为 b是个整数 所以
t=log(2)b
时间复杂度比直接循环求a^b大大的降低了
模取幂运算
事实上,m^e mod n可以直接计算,没有必要先算m^e。
m^e mod n叫做模取幂运算,根据简单的数论知识,很容易设计一个分治算法。具体如下:
设b[k], b[k-1],...,b[1],b[0]是整数b的二进制表示(即b的二进制有k+1位,b[k]是最
高位),下列过程随着c的值从0到b成倍增加,最终计算出a^c mod n
Modular-Exponentiation(a, b, n)
1. c ← 0
2. d ← 1
3. 设b[k],b[k-1],..b[0]是b的二进制表示
4. for i←k downto 0
5. do c ← 2c
6. d ← (d*d) mod n
7. if b[i] = 1
8. then c ← c + 1
9. d ← (d*a) mod n
10. return d
首先说明一下,上述伪代码中用缩紧表示语句之间的层次关系,例如第5~9行都是for循环体
内的语句,第8~9行都是then里面的语句。这是我比较喜欢的一种表示方法 ;)
上述伪代码依次计算出的每个幂或者是前一个幂的两倍,或者比前一个幂大1。过程依次从
右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的
两个恒等式中的一个:
a^(2c) mod n = (a^c mod n)^2
a^(2c+1) mod n = a * (a^c mod n)^2
用哪一个恒等式取决于b[i]=0还是1。由于平方在每次迭代中起着关键作用,所以这种方法
叫做“反复平方法(repeated squaring)”。在读入b[i]位并进行相应处理后,c的值与b的
二进制表示b[k],b[k-1],..b[0]的前缀的值相同。事实上,算法中并不真正需要变量c,
只是为了说明算法才设置了变量c:当c成倍增加时,算法保持条件d = a^c mod n 不变,直
至c=b。
如果输入a,b,n是k位的数,则算法总共需要执行的算术运算次数为O(k),总共需要执行的位
操作次数为O(k^3)。
关于快速幂和快速幂时间复杂度的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。