Chapter-6 Calculation 第6章 计算 - Exponentiation 幂运算

问题

求整数 x 的 n 次方的最低 m 位数字。

解法

循环的计算 x x … * x 共 n 次乘法，然后截取最低 m 位数字，该算法的时间复杂度为 O(n) ，显然我们希望有更快的算法。

快速求幂算法基于下面的递归公式：

x^n =
begin{cases}
1 & n == 0
x & n == 1
x * (x ^ 2)^((n - 1) / 2) & x为奇数
(x ^ 2)^(n / 2) & x为偶数
end{cases}

可以写出递归函数来算出 x^n 。因为次方运算会使 x 迅速增大，导致计算机无法存储结果，因此每次计算次方后都可以对 m 取模，防止 x 增大到 int32 无法表示。

该算法还可以改写为非递归的二进制形式，性能更高。

Wikipedia Exponentiation by squaring

• 2k-ary算法
• Sliding-Window算法(滑动窗口算法)
• Montgomery’s ladder技术(M的阶梯算法)