快速幂算法
计算 。
可以看到，原本需要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)。
关于快速幂和快速幂时间复杂度的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。