🚀 快速幂算法

SimpleWord / 2023-07-13 / 原文

📖 1.算法原理

将指数n表示为二进制形式,例如n的二进制表示为\(b_k b_{k-1} ... b_2 b_1 b_0\),那么\(x^n\)可以表示为:

\[x^n = x^{(b_k \cdot 2^k)} \cdot x^{(b_{k-1} \cdot 2^{k-1})} \cdot \cdots \cdot x^{(b_2 \cdot 2^2)} \cdot x^{(b_1 \cdot 2^1)} \cdot x^{(b_0 \cdot 2^0)} \]

* \(b_m\)为0的项相当于\(\cdot1\),直接忽略即可。

算法的核心思想是将大的幂运算分解为多个幂运算,并且它们的值的依赖于前面的幂运算,不需要从头开始计算。

📝 2.手动计算案例

计算\(2^{13}\):

将指数13转换为二进制:\(13 = (1101)_2\)。
应用快速幂公式:\(2^{13} = 2^{(1 \cdot 2^3)} \cdot 2^{(1 \cdot 2^2)} \cdot 2^{(1 \cdot 2^0)} = 2^8 \cdot 2^4\cdot 2^1= 8192\)。

计算\(3^{5}\):

将指数5转换为二进制:\(5 = (101)_2\)。
应用快速幂公式:\(3^{5} = 3^{(1 \cdot 2^2)} \cdot 3^{(1 \cdot 2^0)} = 3^4 \cdot 3^1= 243\)。

💻 3.Java实现

result初始为1

可以采用\((power\ \&\ 1)\)每次获取指数二进制的最后一位

是1则之前的结果\(result\cdot\ base\)

power每次右移一位

删除和刷新当前最低位

为0时说明处理结束

每次通过base的平方计算下一次循环中更高位的幂次方。

👀 点击查看代码

import java.math.BigInteger;

public class Main {
    // 可适应大多数场景
    public static long fastPower(long base, long power) {
        long result = 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                result *= base;
            }
            base *= base;
            power >>= 1;
        }
        return result;
    }

    // 对于更大的数
    public static BigInteger fastPower(BigInteger base, BigInteger power) {
        BigInteger result = BigInteger.ONE;
        while (!power.equals(BigInteger.ZERO)) {
            if (power.and(BigInteger.ONE).equals(BigInteger.ONE)) {
                result = result.multiply(base);
            }
            base = base.multiply(base);
            power = power.shiftRight(1);
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试用例1
        long base1 = 3;
        long power1 = 3;
        long result1 = fastPower(base1, power1);
        System.out.println("Long fastPower(" + base1 + ", " + power1 + ") = " + result1);

        // 测试用例2
        BigInteger base2 = new BigInteger("3");
        BigInteger power2 = new BigInteger("100");
        BigInteger result2 = fastPower(base2, power2);
        System.out.println("BigInteger fastPower(" + base2 + ", " + power2 + ") = " + result2);
    }
}