快速幂算法

快速幂算法

一、简单介绍

​ 快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以$O(lo{g}_n)$的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

二、计算$7^{10}$

​ 让我们先来思考一个问题：7的10次方，怎样算比较快？

​ 最朴素的想法，77=49，497=343，… 一步一步算，共进行了9次乘法。这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

​ 我们换一个角度来引入快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是 1010。于是这个问题就变成了求7的二进制（1010）次幂。这样就只需要计算4次，相比于9次，大大提升了效率。

做法：计算$7^{10}$，也就是计算 $7^{1010}=7^{(1000{)}_2}\times 7^{(10{)}_2}=17^{(8{)}_{10}}\times \times 7^{(2{)}_{10}}$，那么只需要计算$7^{(8{)}_{10}}+7^{(2{)}_{10}}$。更一般化，只需要计算$7^{2^0},7^{2^1},7^{2^2},...,7^{2^n}$。

三、一般化

1、计算$a^n$的快速方法：

（1）将$n$ 转化成二进制形式，例如1011010

（2）转化后的形式为$a^{(x_k{x}_{k-1}...x_2{x}_1{x}_0{)}_2}=a^{x_k\mathrm{0...00}}\times a^{0x_{k-1}...00}\times a^{\mathrm{00...10}}\times a^{\mathrm{00...01}}$.

（3） 需要计算的数值为$a^1,a^2,a^4,a^8,....,a^{2^n}$.

2、时间复杂度分析：

一般求解 $a^n$ 时，需要计算n次。但是使用快速幂算法之后，将$n$ 表示成二进制只需要$O(lo{g}_n)$ 位数字，只需要计算$O(lo{g}_n)$次。

四、代码

public static Long quickPow(Long a,Long n,Long p){//结果Long res = 1L;while (n != 0) {//判断 n 的二进制的最后一位是否为0if((n&1)!=0){//当n的二进制最后一位为1时，乘以当前的权重res = (res*a)%p;}//更新n，每次n向右移一位n = n >> 1;//更新每一位的权重a = (a*a)%p;}return res;
}

五、参考资料

[1] 基础算法—快速幂详解

[2] 快速幂算法

幂算法](https://blog.csdn.net/HouGOD/article/details/123847315)