Java快速幂算法：从递归与迭代到矩阵应用

原创

Yeats_Liao

发布于 2025-09-18 10:58:56

2900

文章被收录于专栏：后端知识开放麦后端知识开放麦

1 快速幂算法基础

快速幂算法用来计算 $a^n$，其中 $a$ 是底数，$n$ 是指数。这个算法的核心想法很简单：把指数 $n$ 转换成二进制，然后根据二进制的每一位来决定要不要把当前的底数乘到结果里。

通过这种方法，原来需要 $O(n)$ 时间的计算可以压缩到 $O(log n)$。

1.1 算法原理

举个例子，计算 $a^{13}$ 时，先把 13 转成二进制：$1101$。

根据二进制展开：$a^{13}=a^{8}\times a^{4}\times a^{1}$，因为 $13 = 2^3 + 2^2 + 2^0$。

计算过程中，我们不断让底数 $a$ 自乘（平方），同时检查 $n$ 的二进制位。如果当前位是 1，就把这个 $a$ 乘到最终结果里。

1.2 为什么要用快速幂

传统方法计算 $a^n$ 需要做 $n-1$ 次乘法，当 $n$ 很大时效率很低。快速幂能大幅减少乘法次数，特别是处理高次幂时效果明显。

1.3 应用场景

快速幂在多个领域都很有用：

密码学：RSA 加密需要计算大整数的幂取模，快速幂配合模运算能加快加密解密速度。

数论计算：求高次幂、模运算，解决离散对数等问题。

图形学：计算矩阵的高次幂，比如图形变换的多次迭代。

2 Java 实现方案

下面介绍几种在 Java 中实现快速幂的方法：

2.1 递归版本

public class FastPowerRecursive {
    public static long fastPower(long a, long n) {
        if (n == 0) {
            return 1;
        }
        long half = fastPower(a, n / 2);  // 递归计算 a 的 n/2 次幂
        if (n % 2 == 0) {
            return half * half;  // 如果 n 是偶数
        } else {
            return a * half * half;  // 如果 n 是奇数
        }
    }

    public static void main(String[] args) {
        long a = 2;
        long n = 10;
        System.out.println(fastPower(a, n));
    }
}

这个递归实现的思路是：

如果指数 n 为 0，直接返回 1
先递归计算 a 的 n/2 次幂
如果 n 是偶数，结果就是 half * half
如果 n 是奇数，结果是 a * half * half

2.2 迭代版本

public class FastPowerIterative {
    public static long fastPower(long a, long n) {
        long result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {  // 检查 n 的最低位是否为 1
                result = result * a;
            }
            a = a * a;  // 对 a 进行平方操作
            n >>= 1;  // 右移 n，相当于 n 除以 2
        }
        return result;
    }

    public static void main(String[] args) {
        long a = 2;
        long n = 10;
        System.out.println(fastPower(a, n));
    }
}

迭代版本更直观：

用位运算 (n & 1) 检查 n 的最低位
如果最低位是 1，就把当前的 a 乘到结果里
每次循环让 a 平方，n 右移一位

2.3 带模运算的快速幂

实际应用中经常需要对结果取模，防止数值溢出：

public class FastPowerMod {
    public static long fastPowerMod(long a, long n, long mod) {
        long result = 1;
        a %= mod;  // 对底数取模，防止溢出
        while (n > 0) {
            if ((n & 1) == 1) {
                result = (result * a) % mod;  // 累乘结果并取模
            }
            a = (a * a) % mod;  // 对底数平方并取模
            n >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        long a = 2;
        long n = 10;
        long mod = 1000000007;
        System.out.println(fastPowerMod(a, n, mod));
    }
}

这个版本在每次运算后都取模，确保中间结果不会溢出。

2.4 矩阵快速幂

矩阵快速幂是快速幂在矩阵运算中的扩展，常用于解决递推关系问题：

import java.util.Arrays;

class Matrix {
    long[][] data;
    int n;

    public Matrix(int n) {
        this.n = n;
        data = new long[n][n];
    }

    public Matrix multiply(Matrix other) {
        Matrix result = new Matrix(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result.data[i][j] += data[i][k] * other.data[k][j];
                }
            }
        }
        return result;
    }

    public Matrix fastPower(int k) {
        Matrix result = new Matrix(n);
        for (int i = 0; i < n; i++) {
            result.data[i][i] = 1;  // 初始化为单位矩阵
        }
        Matrix base = this.copy();
        while (k > 0) {
            if ((k & 1) == 1) {
                result = result.multiply(base);
            }
            base = base.multiply(base);
            k >>= 1;
        }
        return result;
    }

    public Matrix copy() {
        Matrix copy = new Matrix(n);
        for (int i = 0; i < n; i++) {
            copy.data[i] = Arrays.copyOf(data[i], n);
        }
        return copy;
    }
}

public class MatrixFastPowerExample {
    public static void main(String[] args) {
        Matrix m = new Matrix(2);
        m.data[0][0] = 1;
        m.data[0][1] = 1;
        m.data[1][0] = 1;
        m.data[1][1] = 0;
        int k = 5;
        Matrix result = m.fastPower(k);
        for (long[] row : result.data) {
            for (long num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

矩阵快速幂的实现思路和普通快速幂类似：

Matrix 类封装了矩阵的基本操作
multiply 方法实现矩阵乘法
fastPower 方法用快速幂思想计算矩阵的幂次
结果矩阵初始化为单位矩阵

3 总结

快速幂算法通过二进制拆分和分治思想，把幂运算的时间复杂度从 $O(n)$ 降到 $O(log n)$。Java 中可以用递归或迭代方式实现，还能结合取模运算避免溢出。

矩阵快速幂扩展了这个算法的应用范围，在解决线性递推、图论路径等问题时很有用。

选择哪种实现方式要看具体需求。处理大数时记得用 BigInteger 或 BigDecimal 来避免溢出问题。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S15#自选日志

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S15#自选日志

登录后参与评论

0 条评论

热度