快速幂【c++】

作者: 執迷_4869 | 来源:发表于2020-01-20 00:56 被阅读0次

2018-07-09-快速幂
快速幂【c++】
(矩阵)快速幂
快速幂
快速幂,矩阵快速幂
模板 | 整数快速幂 & 快速幂取模
常用算法
快速幂
快速幂
快速幂

幂是指乘方运算的结果。
在编写程序来实现乘方运算时，例如要求 $a^b$ ，很容易想到将b个a依次相乘。这样做需要n-1次乘法运算，这就是朴素版本的求幂算法。

朴素版本

// 朴素算法
int exponentiation(int a, int b) {
    int res = 1;
    for (; b > 0; b--) 
        res *= a;
    return res;
}

递归版本

设 $n=2k$ ，且k是大于1的整数。显然运用朴素版本的算法来计算 $2^n$ 需要 $n-1=2k-1$ 次乘法。但若想到 $2^n = 2^k\times 2^k$ 的话，若计算 $2^k$ 用了 $k-1$ 次乘法的话，那计算 $2^n$ 需要的乘法次数 $=k < 2k-1$ . 当然，如果将这个策略再次运用到 $2^k$ 的计算上，那么乘法次数又可以减少了。
再比如， $2^{10} = (2^5)^2 = ((2^2)^2\times 2)^2$ ，只需要四次乘法就能完成运算。
减少乘法次数的要诀在于，重复利用低幂次的值来计算高次幂。基于这种思想，很容易设计出基于递归的求幂算法。

// 递归算法
int fastExponetiation1(int a, int b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    int a2 = fastExponetiation1(a, b / 2);
    return a2 * a2 * fastExponetiation1(a, b % 2);
}

简单来说，每次递归，指数减半（并向下取整）。指数为0或1时，不再往下递归。显然，此算法的时间复杂度为 $O(\log_2 b)$ ，相比之下，朴素算法的时间复杂度为 $O(b)$ . 新算法优秀多了。

这还没完。实际上，该递归算法还存在非递归形式。

非递归版本

再看 $2^{10}$ 的例子。 $2^{10}=2^8\times 2^2=2^{8\times1}\times 2^{4\times0} \times 2^{2 \times 1}\times 2^{1\times 0}$ . 细心的读者已经发现，式子中依次出现了1、0、1、0四个数，而1010正是10的二进制表示。
令n = 0, 1, 2, 3···，依次遍历b的二进制表示的第n位，根据该位是0还是1来判断是否将 $a^{2^n}$ 纳入连乘之中，最终就能得到 $a^b$ 的值。同样的，还是利用低幂次的值来计算高幂次的值。代码如下：

// 非递归算法
int fastExponetiation2(int a, int b) {
    int res = 1;
    for (; b; res = (b & 1 ? res * a : res), a = a * a, b = b >> 1);
    return res;
}

在第i轮循环（i = 1, 2, 3······）中，变量a的值为（a的初始值）的 $2^{i-1}$ 次幂。
注意代码b = b >> 1等同于b = b / 2，而代码b & 1等同于b % 2. 这就和前面的递归版本的代码联系起来。

总结

递归版本和非递归版本的算法，本质上都是一样的，都是基于指数的拆分，即 $a^b = a^{x+y}=a^x a^y$ 。递归版本应该更好理解。然而，众所周知，函数的递归深度是有限的，而且递归操作还会产生其它额外的开销。将递归的算法展开为非递归的形式，有助于提高程序的性能。因此，非递归版本的算法在效率上更胜一筹。