快速幂之Java实现

博主针对2021校招字节跳动的第五轮笔试第二，学习了快速幂算法

文章目录

一、简介

求A^B的最后三位数表示的整数。

说明：A^B的含义是“A的B次方”

当一个数的幂很大时，如果直接使用Math.pow()运算，会导致溢出，所以最简单的方法就是，累乘B次，每次对结果进行求模运算，我们以2的1000000000次方为例，Java代码如下：

public class Test {
    private static int mod = 1000;

    public static void main(String[] args) {
        int x = 2;
        int n = 1000000000;
        long startTime = System.currentTimeMillis();
        int result = fastPower(x,n);
        System.out.println("结果是："+result);
        long endTime = System.currentTimeMillis();
        System.out.println("运行时间为："+(endTime-startTime)+" ms. ");
    }

    private static int fastPower(int x, int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result %= mod;
            result *= x;
        }
        return result%mod;
    }
}

结果：

结果是：376
运行时间为：11127 ms.

可以看出，时间复杂度非常高，基本上所有的题目都没有办法AC，所以需要进一步优化时间复杂度。

二、性能优化

对于2的10次方来讲，可以对其进行拆分：

2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

快速幂算法的核心思想就是**每一步都把指数分成两半，而相应的底数做平方运算。**这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。

针对上面例子，继续优化：

(2 * 2) * (2 * 2) * (2 * 2) * (2 * 2) * (2 * 2)
==》4^5

此时指数变成了一半，多计算了一次底数平方，少计算5次指数运算。

按照这个思路，可以对所有指数为偶数的不断优化。但是如果指数为奇数呢，比如上面的4^5。

优化的思路就是，将指数减一，凑出偶数，即抽出了一个底数的一次方，如下所示：

4^5 = 4^4 * 4^1

这样继续对4^4优化为：

4^4 * 4^1 
==》 16^2 *  4^1 
==》 256^1 * 4^1
==》 1024

相比于10次的累乘运算，优化到了5次，优化后的Java代码如下。

public class Test {
    private static int mod = 1000;

    public static void main(String[] args) {
        int x = 2;
        int n = 1000000000;
        long startTime = System.currentTimeMillis();
        int result = fastPower(x, n);
        System.out.println("结果是：" + result);
        long endTime = System.currentTimeMillis();
        System.out.println("运行时间为：" + (endTime - startTime) + " ms. ");
    }

    private static int fastPower(int x, int n) {
        int result = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                n -= 1;
                result *= x;
                result %= mod;
            } else {
                n /= 2;
                x *= x;
                x %= mod;
            }
        }
        return result % mod;
    }
}

结果：

结果是：376
运行时间为：0 ms.

三、对性能进行压榨

上述代码结构依然有优化的空间：

n % 2 == 1可以使用&运算符优化，变成(n & 1) == 1
n /= 2可以使用位运算符优化，变成n = n >> 1

优化后的代码如下：

public class Test {
    private static int mod = 1000;

    public static void main(String[] args) {
        int x = 2;
        int n = 1000000000;
        long startTime = System.currentTimeMillis();
        int result = fastPower(x, n);
        System.out.println("结果是：" + result);
        long endTime = System.currentTimeMillis();
        System.out.println("运行时间为：" + (endTime - startTime) + " ms. ");
    }

    private static int fastPower(int x, int n) {
        int result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                n -= 1;
                result *= x;
                result %= mod;
            }
            n = n >> 1;
            x *= x;
            x %= mod;
        }
        return result % mod;
    }
}

结果：

结果是：376
运行时间为：0 ms.