快速幂

快速幂算法用于处理大数问题，由于一般Number类型的精度无法处理过大的数字，所以对幂乘操作进行优化，用时间换精度的解决方案
快速幂算法复杂度：

  • 时间复杂度：O(log n)

快速幂算法使用场景：
用于对某个数做大数幂乘，幂乘过大导致超过精度范围，一般包括两个参数(base,exp)

快速幂问题解题思路：

  1. 将指数部分拆解为多个幂次的和
    比如 $3^{13}$ ,我们可以将其拆解为 $3^1*3^4*3^8$，为什么这么拆？从二进制角度考虑13 = 1101
  2. 基数和幂次的转化
    通过基数base和幂次exp之间的转化逐步累积结果，即根据幂次的特性，每次exp/2可以等价互换base*base
  3. 通过前两步累积有贡献的位次
    我们设定res初始值为1，那么通过每次循环exp = Math.floor(exp / 2)，检查最低位为1，并计入结果res = (res*base) % MOD，同时更新base的值为base = (base * base) % MOD
    以$3^{13}$为例，快速幂乘从低位到高位逐步处理：
    • $3^1$对应最低位1，base对应$2^0$部分 => 有贡献,res*=base
    • $3^2$对应次低位0，base对应$2^1$部分 => 无贡献
    • $3^4$对应次低位1，base对应$2^2$部分 => 有贡献,res*=base
    • $3^8$对应次低位1，base对应$2^3$部分 => 有贡献,res*=base
    • 结果即$3^{13} = 3^1*3^4*3^8$

javascript下的具体样例：

点击查看具体代码 
1
2
3
4
5
6
7
8
9
10
11
12
function fastPower(base, exp) {
    let res = BigInt(1);
    base = BigInt(base);
    while (exp > 0) {
        if (exp % 2 === 1) {            // 如果指数是奇数，累积乘法
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;     // 基数平方并取模
        exp = Math.floor(exp / 2);      // 指数减半
    }
    return res;                         // 返回结果
}