快速幂算法超详细教程

2024-07-12 03:03| 来源: 网络整理| 查看: 265

快速幂求幂运算快速幂引入快速幂二进制快速幂指数折半快速幂的应用

求幂运算

求幂运算大家都不陌生，幂是指数运算的结果，当m是正整数时nᵐ的意义为m个n相乘，n的m次幂也就是n的m次方。用代码实现求幂运算可以这样写：

long long int mypower(int base, int power) { long long int result = 1; for (int i = 1; i 0) //指数大于0说明指数的二进制位并没有被左移舍弃完毕 { if (power & 1) //指数的当前计算二进制位也就是最末尾的位是非零位也就是1的时候 //例如1001的当前计算位就是1， 100*1* 星号中的1就是当前计算使用的位 result *= base; //累乘当前项并存储 base *= base; //计算下一个项，例如当前是n^2的话计算下一项n^2的值 //n^4 = n^2 * n^2; power >>= 1; //指数位右移，为下一次运算做准备 //一次的右移将舍弃一个位例如1011(2)一次左移后变成101(2) } return result; //返回最终结果 }

为了便于理解我们分析一个实例计算 345 首先把指数45转换为二进制 45 ( 10 ) = 101101 ( 2 ) 45(10) = 101101(2) 45(10)=101101(2) 接下来我们可以得到下面的等式 3 45 ( 10 ) = 3 101101 ( 2 ) = 3 2 5 ∗ 1 + 2 4 ∗ 0 + 2 3 ∗ 1 + 2 2 ∗ 1 + 2 1 ∗ 0 + 2 0 ∗ 1 = 3 2 5 ∗ 1 ∗ 3 2 4 ∗ 0 ∗ 3 2 3 ∗ 1 ∗ 3 2 2 ∗ 1 ∗ 3 2 1 ∗ 0 ∗ 3 2 0 ∗ 1 3^{45(10)} = 3^{101101(2)}=3^{2^5*1 + 2^4*0+2^3*1+2^2*1+2^1*0+2^0*1}=3^{2^5*1}*3^{2^4*0}*3^{2^3*1}*3^{2^2*1}*3^{2^1*0}*3^{2^0*1} 345(10)=3101101(2)=325∗1+24∗0+23∗1+22∗1+21∗0+20∗1=325∗1∗324∗0∗323∗1∗322∗1∗321∗0∗320∗1因为 3 2 4 ∗ 0 = 3 2 1 ∗ 0 = 3 0 = 1 3^{2^4 * 0}=3^{2^1 * 0}=3^0 = 1 324∗0=321∗0=30=1所以我们只需要计算 3 2 5 ∗ 1 ∗ 1 ∗ 3 2 3 ∗ 1 ∗ 3 2 2 ∗ 1 ∗ 1 ∗ 3 2 0 ∗ 1 3^{2^5*1}*1*3^{2^3*1}*3^{2^2*1}*1*3^{2^0*1} 325∗1∗1∗323∗1∗322∗1∗1∗320∗1根据指数运算性质可以得到 n 2 m − 1 ∗ n 2 m − 1 = n 2 m n^{2^{m-1}}* n^{2^{m-1}}= n^{2^m} n2m−1∗n2m−1=n2m所以根据上述公式递推计算即可得以下项的值 3 2 5 ， 3 2 4 ， 3 2 3 ， 3 2 2 ， 3 2 1 ， 3 2 0 3^{2^5}，3^{2^4}，3^{2^3}，3^{2^2}，3^{2^1}，3^{2^0} 325，324，323，322，321，320 最后累乘即可得到结果。

快速幂指数折半

核心思想：每一次运算都把指数折半，底数变其平方每次的指数都折半可以把很大的指数不断减小，这样减少循环次数，但还能保持最终结果不变达到快速求幂次方的效果。因为是每一轮指数都折半所以这相当于用二的m次方（m是折半次数）去除于指数，因为指数的”大爆炸“特性所以不管多大的指都能被快速缩小。例如：410第一次折半是45,第二次折半是42,第三次折半是41,第四次折半是40。也就是说若nm的m被除以2k次方k为折半次数。在2k(k=1,2,3,4……)形成指数"大爆炸"。接下来我们具体看例子。计算412: 4 12 = 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 ∗ 4 4^{12}= 4*4*4*4*4*4*4*4*4*4*4*4 412=4∗4∗4∗4∗4∗4∗4∗4∗4∗4∗4∗4我们跟据指数折半底数变其平方来操作 ( 4 ∗ 4 ) 12 / 2 = 1 6 6 = ( 4 ∗ 4 ) ∗ ( 4 ∗ 4 ) ∗ ( 4 ∗ 4 ) ∗ ( 4 ∗ 4 ) ∗ ( 4 ∗ 4 ) ∗ ( 4 ∗ 4 ) = 16 ∗ 16 ∗ 16 ∗ 16 ∗ 16 ∗ 16 (4*4)^{12/2}=16^{6}= (4*4)*(4*4)*(4*4)*(4*4)*(4*4)*(4*4) = 16 * 16 * 16 *16*16*16 (4∗4)12/2=166=(4∗4)∗(4∗4)∗(4∗4)∗(4∗4)∗(4∗4)∗(4∗4)=16∗16∗16∗16∗16∗16我们发现412变成了166，循环次数从12变成了6，我们继续操作 ( 16 ∗ 16 ) 6 / 2 = 25 6 3 = ( 16 ∗ 16 ) ∗ ( 16 ∗ 16 ) ∗ ( 16 ∗ 16 ) = 256 ∗ 256 ∗ 256 (16*16)^{6/2} = 256^3 = (16*16)*(16*16)*(16*16) = 256*256*256 (16∗16)6/2=2563=(16∗16)∗(16∗16)∗(16∗16)=256∗256∗256现在166次方变成了2563，循环次数从6变成了3，我们继续操作，但是会发现现在的指数是3，不能被二整除，那怎么办呢？若指数是奇数那么指数减一再折半。让3变成2再折半。 256 ∗ ( 256 ∗ 256 ) ( 3 − 1 ) / 2 = 256 ∗ 6553 6 1 = 256 ∗ ( 256 ∗ 256 ) = 256 ∗ 65536 256*(256 * 256)^{(3-1)/2}=256*65536^1= 256*(256*256)=256*65536 256∗(256∗256)(3−1)/2=256∗655361=256∗(256∗256)=256∗65536现在2563变成了256 * 655361 因为现在的指数是1指数是奇数所以我们还是继续指数减一再折半的操作 256 ∗ 65536 ∗ 6553 6 0 / 2 = 256 ∗ 65536 256*65536*65536^{0/2} = 256*65536 256∗65536∗655360/2=256∗65536现在指数已经被除以没了，指数为0了，我们不能再做指数折半底数变其平方的操作了。最后我们得到412=256*65536。原本需要循环12次的如今四次循环完成了。这种折半效率在大指数的时候效果显著。例如410000需要循环10000次但是折半计算后只需要14次循环就能解决因为214=16384这已经超过10000了。回忆一下412=256 * 65536的256和65536是从哪里来的呢。2563与655361指数是奇数的时候被指数减一而分离出来的项。现在我们尝试用代码去实现上面的指数折半，底数变其平方的操作。

long long int quik_power(int base, int power) { long long int result = 1; while (power > 0) //指数大于0进行指数折半，底数变其平方的操作 { if (power % 2 == 1) //指数为奇数 { power -= 1; //指数减一 power /= 2; //指数折半 result *= base; //分离出当前项并累乘后保存 base *= base; //底数变其平方 } else //指数为偶数 { power /= 2; //指数折半 base *= base; //底数变其平方 } } return result; //返回最终结果 }

我们不难发现代码中有重复的语句所以我们可以稍加优化整理。

power /= 2; //指数折半 base *= base; //底数变其平方

不管指数是否为奇数偶数，指数折半和底数变其平方是都需要进行的必要操作我们可以直接写在判断语句外面

long long int quik_power(int base, int power) { long long int result = 1; while (power > 0) //指数大于0进行指数折半，底数变其平方的操作 { if (power % 2 == 1) //指数为奇数 { power -= 1; //指数减一 result *= base; //分离出当前项并累乘后保存 } power /= 2; //指数折半 base *= base; //底数变其平方 } return result; //返回最终结果 }

还有一些多余代码我们也能删除。

power -= 1; //指数减一

如果指数是奇数的话有个减一操作，但在代码中我们可以省略这个，因为代码中指数是整数int类型，当power是奇数时小数点会被舍弃，这相当于power减一后再除二的操作。例如：power= 3的时候power / 2 = 相当于power-1后power=2后power / 2 = 1。所以代码可以写成这样。

long long int quik_power(int base, int power) { long long int result = 1; while (power > 0) //指数大于0进行指数折半，底数变其平方的操作 { if (power % 2 == 1) //指数为奇数 result *= base; //分离出当前项并累乘后保存 power /= 2; //指数折半 base *= base; //底数变其平方 } return result; //返回最终结果 }

判断一个数的奇数偶数时，除了判断能否被二整除以外我们还有一个方法就是看那个数的二进制。 15 ( 10 ) = 1111 ( 2 ) 15(10)=1111(2) 15(10)=1111(2) 26 ( 10 ) = 11010 ( 2 ) 26(10)=11010(2) 26(10)=11010(2) 17 ( 10 ) = 10001 ( 2 ) 17(10)=10001(2) 17(10)=10001(2) 36 ( 10 ) = 100100 ( 2 ) 36(10)=100100(2) 36(10)=100100(2)我们可以发现一个规律，奇数的二进制位末尾是1，偶数的二进制位是0.位运算要比取余运算要快所以我们可以把代码写成这样。

long long int quik_power(int base, int power) { long long int result = 1; while (power > 0) //指数大于0进行指数折半，底数变其平方的操作 { if (power & 1) //指数为奇数，power & 1这相当于power % 2 == 1 result *= base; //分离出当前项并累乘后保存 power /= 2; //指数折半 base *= base; //底数变其平方 } return result; //返回最终结果 }

我们还可以替换一些代码使程序运算效率更高。

power /= 2; //指数折半

这里的指数折半操作我们也可以使用位运算的左移运算来完成。位运算比除于运算要快。所以我们可以这样写代码。

long long int quik_power(int base, int power) { long long int result = 1; while (power > 0) //指数大于0进行指数折半，底数变其平方的操作 { if (power & 1) //指数为奇数，power & 1这相当于power % 2 == 1 result *= base; //分离出当前项并累乘后保存 power >>= 1; //指数折半,power >>= 1这相当于power /= 2; base *= base; //底数变其平方 } return result; //返回最终结果 }

这就是我们最终的快速幂代码了。大家可能发现了，在快速幂算法中二进制角度还是指数折半角度最终写出的代码其实是一样的只是理解角度略有不同罢了。

快速幂的应用

快速幂一般不会独立使用，常常配合取余运算法则来使用。看下面这两个题： HDOJ 2035 人见人爱A^B HDOJ 1061 Rightmost Digit 做这两个题前首先我们需要了解一下关于取余的公式 (a + b) % p = (a % p + b % p) % p (a - b) % p = (a % p - b % p ) % p (a * b) % p = (a % p * b % p) % p 我们可以把公式三加入我们的快速幂代码中

long long int quik_power(int base, int power, int p) { long long int result = 1; while (power > 0) { if (power & 1) result = result * base % p; //根据公式每个项都取余数后在再做累乘 base = base * base % p ; //根据公式每个项都取余数后在再做平方操作 power >>= 1; } //根据公式在最后的的结果上再来一次取余数 return result % p; }

那两个题的题解我就不在这写了。特别出两个博客了。感兴趣的朋友可以去看看。 HDOJ 1061 Rightmost Digit 题解 HDOJ 2035 人见人爱A^B 题解

【本文地址】

快速幂算法超详细教程

快速幂算法超详细教程

今日新闻

推荐新闻

快速幂算法 超详细教程

快速幂算法 超详细教程

今日新闻

推荐新闻

快速幂算法超详细教程

快速幂算法超详细教程