快速幂

• 类似题目:
  • 50. Pow(x, n)

快速幂

计算 $x^ n$ 通常需要 $n$ 次乘法, 时间复杂度为 $O(n)$ , 当 $n$ 非常大的时候, 运算效率很低.

快速幂是通过把 $n$ 转化为二进制来实现的. 例如: 计算 $x^{14}$, 14 可以用二进制表示为:

$14 = (1110)_ 2 = 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 $

那么对应的乘法可以表示为:

$x^{14} = x^{2 ^3} * x^{2^2} * x^{2 ^1} $

转换后乘法运算次数减少, 每次计算 $x^{2^n}$, 再决定是否将这个数字加入到最终结果里面去. 代码如下:

def fpowx(x, n):
    res = 1
    while n:
        if n & 1:
            res = res * x
        # compute x^2 x^4 x^8
        x *= x
        n >>= 1
    return res

乘法防止溢出

注: 对于 python 没有任何帮助, python整数直接相乘取模会快10倍

f_multi: 0.030360s
s_multi: 0.003781s

防止溢出的乘法和快速幂类似, 出现的原因是, 想两个数直接相乘发生溢出时, 改为相加运算, 并且可以直接取模. 这样保证了数据的正确性.

例如 $x\times 14$ 可以转化为:

$x\times 14 = 8\times x + 4\times x + 2\times x$

def fmulti(m, n, mod=10 ** 9 + 7):
    res = 0
    while n:
        if n & 1:
            res += m
        m = (m + m) % mod
        res %= mod
        n >>= 1
    return res