乘法快速幂相关总结

Question

递归计算 (a <sup>n</sup>) % mod

递归计算其实是更容易理解的:

• 为了求 aⁿ，我们先递归去求出 a^n/2，得到结果记录为 halfRes ；
• 然后如果 n 为偶数，很好办，再乘以一个 halfRes 就可以了（再取模一下)，也就是可以返回 halfRes*halfRes ；
• 但是如果 n 为奇数的话，就需要再乘以一个 a ，然后再返回；

代码：

    static long pow_mod(long a, long n, long mod) {
        if (n == 0)      // a^0 = 1
            return 1;
        // 先求一半的 --> 你先给我求出 a ^ (n/2) 的结果给我
        long halfRes = pow_mod(a, n >> 1, mod); // n >> 1 --> n/2

        long res = halfRes * halfRes % mod;

        if ((n & 1) != 0)       // odd num
            res = res * a % mod;
        return res;
    }

---

非递归计算 (a <sup>n</sup>) % mod

假设一个整数是 10 ，如何最快的求解 10 的 75 次方。

• ① 75 的二进制形式为 1001011 ；
• ② 10 的 75 次方 = 10⁶⁴ × 10⁸ × 10² × 10¹；
• 在这个过程中，我们先求出10¹，然后根据10¹求出10²，再根据10²求出10⁴。。。。，最后根据10³²求出10⁶⁴，即 75 的二进制数形式总共有多少位，我们就使用了多少次乘法；
• ③ 在步骤②进行的过程中，把应该累乘的值相乘即可，比如10⁶⁴、10⁸、10²、10¹应该累乘，因为 64、8、2、1 对应到 75 的二进制数中，相应位上是 1 ；而10³²、10¹⁶、10⁴不应该累乘，因为 32、16、 4 对应到 75 的二进制数中，相应位是 0 ；

    static long pow_mod2(long a, long n, long mod) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) != 0) // 二进制最低位 是 1 --> (n&1) != 0  -->  乘上 x ^ (2^i)   (i 从 0 开始)
                res = res * a % mod;
            a = a * a % mod;  // a = a^2
            n >>= 1;          // n -> n/2      往右边移一位
        }
        return res;
    }

使用 a ^ 11 来模拟一下计算过程：

计算 ( a * b ) % mod

	// 计算 (a * b) % mod
    static long mul_mod(long a, long b, long mod){
        long res = 0;

        while(b > 0){
            if( (b&1) != 0)  // 二进制最低位是 1 --> 加上 a 的 2^i 倍, 快速幂是乘上 a 的 2^i ）
                res  = ( res + a) % mod;
            a = (a << 1) % mod;    // a = a * 2    a 随着 b 中二进制位数而扩大 每次 扩大两倍。
            b >>= 1;               // b -> b/2     右移  去掉最后一位 因为当前最后一位我们用完了，
        }

        return res;
    }

---

配合 ( a * b ) % mod 和乘法快速幂

可以使用非递归的乘法快速幂和上面的 (a*b) % mod 来计算快速幂，差别不大：

    // 计算 (a * b) % mod
    static long mul_mod(long a,long b,long mod){
        long res = 0;
        while(b > 0){
            if( (b&1) != 0)  // 二进制最低位是 1 --> 加上 a 的 2^i 倍, 快速幂是乘上 a 的 2^i ）
                res  = ( res + a) % mod;
            a = (a << 1) % mod;    // a = a * 2    a 随着 b 中二进制位数而扩大 每次 扩大两倍。
            b >>= 1;               // b -> b/2     右移  去掉最后一位 因为当前最后一位我们用完了，
        }
        return res;
    }

    //非递归 计算 (a^n) % mod   配合 mul
    static long pow_mod3(long a,long n,long mod){
        long res = 1;
        while(n > 0) {
            if( (n&1) != 0 ) // 二进制最低位 是 1 --> (n&1) != 0  -->  乘上 x ^ (2^i)   (i 从 0 开始)
                res = mul_mod(res,a,mod) % mod;
            a = mul_mod(a,a,mod) % mod;  // a = a^2
            n >>= 1;          // n -> n/2      往右边移一位
        }
        return res;
    }