快速指数法

快速指数法在计算高次方时十分高效，也称为快速幂。

原理

• 计算机中采用二进制存储数据，对于一个数字$M$，它的二进制位数为$log_2(M)+1$。

• 对于一个二进制表示的数字$M_{(2)}$，$2*M$即为在$M_{(2)}$的末尾追加（位右移运算）一个$0$，同理，$2*M+1$即为在$M_{(2)}$的末尾追加一个$1$。

• 将$0_{(2)}$进行$log_2(M)+1$次上述操作（追加高到低位的二进制位），即可得到$M_{(2)}$。

$$a^n=R\\ \Rightarrow a^{2n}=R^2\\ \Rightarrow a^{2n+1}=R^2\cdot a$$

算法实现

确定 $M_{(2)}$ 序列，逐步对$n$追二进制位（初始为0），并更新计算$a^n$，追加完二进制位时，即得到$a^M$。

时间复杂度：$O(log(M))$。