快速幂原理解析

发表于   |   分类于   |  

问题描述

求n的m次方，时间复杂度O(log(N)).不考虑大数情况。

解决方法：快速幂

求解方法和步骤

1）假设n=3,m=10

2）将m转化为二进制为t=1010,数组形式为a={1,0,1,0}，a[i]表示m的第i位上的二进制数组。

3）f[i]表示m的前i个二进制数字的十进制形式。我们可以得到 f[i+1] = (f[i]+a[i] )2 * ，如：10 =((((1+0)2+1)2+0)2+1)2 。

4）2^3^4 = (2^3)^4 ，2^(1+2) = 2^22 ,由上面两条定理可以推得 g[i+1] = (g[i] (n^a[i]))^2 。

其中g[i]表示 n^f[i]。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


package acm;

/**

 * Created by hubaobin on 16/7/22.

 */

public class QuickPower {



    public static int getPower(int n, int m) throws RuntimeException {

        if (n == 0) {

            if (m == 0) throw new RuntimeException("不能同时为0");

            else return 1;

        }

        if (m == 0) return 1;

        int result = 1;

        while (m > 0) {

            if ((m & 1) == 1) {

                result *= n;

            }

            result *= result;

            m >>= 1;

        }

        return result;

    }



    public static void main(String[] args) {

        System.out.println(getPower(2, 10));

    }

}