高效幂运算

问题描述：假设有一机器能够存储这样一些大整数（或有一个编译程序能够模拟它），求一个相对大的数字（一般为400位左右）的极大幂（400位左右）

显然我们可以使用Java内置函数pow()求解，但是这大概会需要进行10^400次乘法，而下面这种方法在最坏的情形下只需要大约2600次乘法

拆分解法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Pow {
    public static void main(String[] args) {
        long x = 2;
        int n = 5;
        System.out.println(pow(x,n));
    }

    public static long pow(long x,int n){
        if( n == 0 ){
            return 1;
        }
        if( n == 1 ){
            return x;
        }
        //偶数   相当于每次将x^n变为x^(n/2) * x^(n/2)
        if( n % 2 == 0 ){
            return pow(x * x, n / 2);
        }else {//奇数   相当于每次将x^n变为x^((n-1)/2) * x^((n-1)/2) * x
            //可以写成pow(x*x,n/2)   原因：(n-1)/2和n/2在Java中结果相同
            //可以写成pow(x,n-1)*2   原因：通过提出一个x，使n变为奇数
            return pow(x * x, (n-1) / 2) * x;
        }
    }
}

二进制解法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Pow {
    public static void main(String[] args) {
        long x = 2;
        int n = 5;
        System.out.println(pow(x, n));
    }

    private static long pow(long x, int n) {
        long pow = 1;
        if (n == 0) {
            return 1;
        }
        while (n > 0) {
            if (n % 2== 1) {
                pow *= x;
            }
            x *= x;
            n >>= 1;
        }
        return pow;
    }
}

当然，Java的基本存储结构是不允许我们存放很大的一个数字的，但是这种高效幂运算的算法是值得思考的