快速幂算法浅谈

简介

快速幂是一种简单有效的高次幂算法，可以在$O(log\ n)$的时间里快速计算高次幂

它是一种常见而且应用广泛的算法，在多种境地都能见到它的身影

引入

我们知道，C语言中，要计算某个数的高次幂，比如x的n次幂，有两种相当简单的方法

其一，就是利用循环，暴力循环n次，每次对结果乘上x，复杂度$O(n)$

其二，则是引用math.h头文件，利用自带的pow函数进行计算

但是我们也知道，这两种算法都较慢，在n相当大时，很容易超时

由此我们就需要一个更优的算法，也即本文所述的快速幂算法

原理

以13的59次幂为例，对于指数59，有如下等式

$$59=2^5+2^4+2^3+2^1+2^0$$

也即

$$(59)_{10}=(111011)_2$$

因此

$$13^{59}=(((((13)^2*13)^2*13)^2)^2*13)^2*13$$

也可写作

$$13^{59}=13*(13)^2*(13)^8*(13)^{16}*(13)^{32}$$

快速幂的思路，就是将较大的指数二分为多个较小的指数之和，进而计算出完整的高次幂

实现

递归

由等式

$$13^{59}=(((((13)^2*13)^2*13)^2)^2*13)^2*13$$

很容易想到递归方程如下

$$
x^n=\begin{cases}
x^{n-1}*a, & \text{if n % 2 != 0}
\\
(x^{n/2})^2, & \text{if n % 2 == 0 && n != 0}
\\
1, & \text{if n == 0}
\end{cases}
$$

而其代码实现也非常简单，只需按照递归方程写即可，如下

int quick_pow(int x, int n)
{
    if (n == 0) return 1;                           // 递归出口
    if (n % 2 != 0) return quick_pow(x, n - 1) * x; // n为奇数
    int tmp = quick_pow(x, n / 2);
    return tmp * tmp;                               // n为偶数
}

这其中，tmp变量不可省略，否则在最后一个return处会因调用两次quick_pow从而把复杂度退化回$O(n)$

循环

由等式

$$13^{59}=13*(13)^2*(13)^8*(13)^{16}*(13)^{32}$$

可以得到平方底数得到新底数计算快速幂的方法

代码实现如下

int quick_pow(int x, int n)
{
    int res = 1;
    while (n)
    {
        if (n & 1) res *= x;    // n在二进制下末位为1
        x *= x;                 // 底数平方
        n >>= 1;                // n 右移一位
    }
    return res;
}

总结

快速幂算法是一种简单而高效的算法，本文简单陈述了其原理及实现，而快速幂仅仅只是众多令人着迷的算法中的一个，还希望与阅读本文的诸君共勉，一同去探索无尽的算法世界。

P.S. 笔者如有陈述不周之处还望斧正