快速幂算法

doMore 252 2024-04-19

简介

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以 O(log n)的时间复杂度计算乘方。

思考

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

方法1： 最朴素的想法，7 \* 7=49，49 \* 7=343，... 一步一步算，共进行了9次乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。

方法2： 先算7的5次方，即7\*7\*7\*7\*7，再算它的平方，共进行了5次乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

方法3： 先算7 \* 7得 49，则7的5次方为49 \* 49 \* 7，再算它的平方，共进行了4次乘法。

方法

递归快速幂

di_gui_kuai_su_mi_tu_pian

计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

    public static int recursionPow(int x, int p) {
        if (p == 0) {
            return 1;
        } else if (p % 2 == 1) {
            return recursionPow(x, p - 1) * x;
        } else {
            // 必要的临时变量，否则会计算两次，算法会退化
            int t = recursionPow(x, p / 2);
            return t * t;
        }
    }

非递归快速幂

    public static int noRecursionPow(int x, int p) {
        int res = 1;
        while (p > 0) {
            // 当前 p 的末位 为 1
            if ((p & 1) == 1) {
                // 当前的 res 乘以 a
                res *= x;
            }
            // x 自乘
            x *= x;
            // p 往右移动一位
            p >>= 1;
        }
        return res;
    }

场景

在实际问题中，常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模。先看一下取模的运算规则 （具体的证明感兴趣的同学可以问度娘）：

  1. (a + b) % p = (a % p + b % p) % p （1）

  2. (a - b) % p = (a % p - b % p ) % p （2）

  3. (a * b) % p = (a % p * b % p) % p （3）

我们只要关注第3条即可：(a * b) % p = (a % p * b % p) % p ，我们仔细研究一下这个运算法则，会发现多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果。也就是说，我们如果要求：

(a*b*c)%d=(a%d*b%d*c%d)%d;

因此，我们可以借助这个法则，只需要在循环乘积的每一步都提前进行“取模”运算，而不是等到最后直接对结果“取模”，也能达到同样的效果。

    private static final int MOD = 1000000007;

    public static int recursionPowMod(int x, int p) {
        if (p == 0) {
            return 1;
        } else if (p % 2 == 1) {
            return recursionPow(x, p - 1) * x % MOD;
        } else {
            // 必要的临时变量，否则会计算两次，算法会退化
            int t = recursionPow(x, p / 2) % MOD;
            return t * t % MOD;
        }
    }
java