带你走进快速幂，感叹算法的魅力-一一网

快速幂

快速幂是一种能够对m的n次幂快速进行计算的一种算法。能在log(n)的时间内求出结果。

传统算法

一般情况下我们会想到直接对m乘n次不就得到了m的n次幂了吗？也就是下面的这种算法，我们可以看到它的时间复杂度是O(n)。

private static double power1(int a,int b){
        double res = 1;
        for (int i = 0; i < b ; i++){
            res *= a;
        }
        return a == 0 ? 0 : res;
}
复制代码

递归快速幂

递归快速幂的思想大致如下：

2^15可以分解成求2^7 * 2^7 * 2，2^7分解为2^3 * 2^3 * 2

2^3分解为2^1 * 2^1 * 2，当幂次为1的时候就是递归的边界条件，我们直接return。我们可以看到2^15依赖2^7的计算，2^7依赖2^3，

所以我们可以用递归来实现它。

 private static double power2(int a,int b){
        if(b == 1){
            return a;
        }
        if((b & 1) == 1){
           return power2(a,b - 1) * a;
        }else {
            double temp =  power2(a,b / 2);
            return temp * temp;
        }
    }
复制代码

非递归快速幂

非递归快速幂的思想大致如下：

我们通过递归快速幂可以看到不断除以2，是不是跟右移动一位是一样的？所以我们换个角度，从n这个幂次的二进制出发，例如2^42，我们可以将42化成101010的二进制。

上述式子我们是很容易知晓的，指数相加。可以看到我们把101010拆成了100000和1010，这是因为我们在计算的过程中，会先计算m * m == m^2=m^10(2)，然后再计算(m * m) * (m * m) == m^4==m^100(2) ，m^8==m^1000(2)不就是对指数在移位吗？有多少位二进制就计算几次。

所以像计算2^100000(2)这种我们只需要移动100000(2)的长度6就行了，每次将上次的结果*结果得到新结果，幂次就会 * 2啦，我们知道* 2是会后面补0的，所以自然就慢慢得到100000，那么新结果这个时候就是我们2^100000(2)，首先2^1 * 2^1 变成了2^10(2)，然后2^2*2^2变成了2^100(2)，最后通过5次这样的计算我们就可以算到2^100000(2)。

回归正题，我们还有2^1010(2)没求呢？2^1010(2)分解成2^1000(2) * 2^10(2)，2^1000(2)和2^10(2)我们是不是在上述求2^100000(2)的过程中会有计算到2^1000(2)和2^10(2)的步骤呢？所以我们只需要在计算到这的时候，记录一下当前的值就行了。根据我们的拆分规则，以为1为分界点的，101010(2)即100000(2) + 1000(2) + 10(2)具体可以回归到上图观察下。每次我们遇到位数为1的时候就需要记录一下，以便于贡献给下次为1的时候计算。具体代码如下：

 private static double power3(int a,int b){
        double res = 1;
        double base = a;
        while(b > 0) {
            if ((b & 1) == 1) {
                res *= base;
            }
            base *= base;
            b >>= 1;
        }
        return res;
    }

复制代码

三种算法时间对比

public class Main {

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        System.out.println(power1(2,100000));
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        System.out.println(power2(2,100000));
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        System.out.println(power3(2,100000));
        System.out.println(System.currentTimeMillis() - startTime);

    }


    private static double power1(int a,int b){
        double res = 1;
        for (int i = 0; i < b ; i++){
            res *= a;
        }
        return a == 0 ? 0 : res;
    }


    private static double power2(int a,int b){
        if(b == 1){
            return a;
        }
        if((b & 1) == 1){
           return power2(a,b - 1) * a;
        }else {
            double temp =  power2(a,b / 2);
            return temp * temp;
        }
    }

    private static double power3(int a,int b){
        double res = 1;
        double base = a;
        while(b > 0) {
            if ((b & 1) == 1) {
                res *= base;
            }
            base *= base;
            b >>= 1;
        }
        return res;
    }

}
复制代码