Links

03.快速幂

前言

幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂,那么想当然的就会写出一个 N 次的循环,然后累乘得到结果。这种幂运算的复杂度是O(N)。
var res = 1
for _ in 0..<n {
res *= x
}
return res

一、 快速幂

那么有没有更快的运算方式呢?
在计算机领域有一种常用的快速幂算法:蒙哥马利幂(Montgomery reduction)算法。将复杂度从O(N) 降到了 O(logN)

1.1 思路一:递归

  • 若 N 为偶数,可以先求 xN/2,然后再平方。
  • 若 N 为奇数,可以先求 x(N-1)/2,然后再平方,再乘以x
快速幂的最基础思想就是上面两条了。
求解 xN/2,x(N-1)/2 时也可以用到上面的思路,每次将指数除以2,每次都可以将复杂度降低一半,知道最后指数为1。

Swift实现

  • 这里不考虑大数,仅作为思路展示
func quickpow(_ x: Int, _ n: Int) -> Int {
if n == 0 {// 直到最后指数为0
return 1
}
let res = quickpow(x, n/2)
if n%2 != 0 {// n 为奇数
return res * res * x
}
// n为偶数
return res * res
}

1.2 思路二:二进制拆分

我们以 x14 为例进行推导。
x14(10) = x1110(2) = x1000(2) * x100(2) * x10(2)
换个方向,更直观:
x1110(2) = x10(2) * x100(2) * x1000(2)
推论:
  • 设 x 的 N 次幂等于 res
    • 1: 在指数 N 的二进制形式下,从最低位开始左移一位,x自乘一次(和指数N左移一位保持一致)
    • 如果当前位为1
      • 当前位a到最低位,中间位全部置0时表示的值b,xb的累乘
    • 如果当前位位0
      • 执行1
    • 循环直到指数N等于0
当前位
指数b
res
1110
0
x0(2)
1110
10
x10(2)
1110
100
x10(2) * x100(2)
1110
1000
x10(2) x100(2) x1000(2)

Swift实现

  • 这里不考虑大数,仅作为思路展示
func quickpow(_ x: Int, _ n: Int) -> Int {
var res = 1
var x = x
var n = n
while n > 0 {
if n & 1 == 1 { // 如果n的当前末位为1
res *= x // res乘上当前的x
}
x *= x// x自乘,当前指数左移一位
n >>= 1// n右移一位,想当于 n / 2
}
return res
}

1.3 参考

二、 快速幂取模

2.1 模运算规律

  • (a + b) % p = (a % p + b % p) % p
  • (a - b) % p = (a % p - b % p + p) % p
  • (a b) % p = (a % p b % p) % p
  • ab % p = ((a % p)b) % p
根据这个规律,可以推导出同余性质

2.2 常见问题场景

我们经常会看到 输出结果对x取模。这种题目一般考察两点:
  • 在原算法的基础上,多一个取模运算来考察你对取模运算规律的掌握
  • 大数据时数据增长太快,64 位甚至 128 位的整形无法表示

2.3 利用快速幂,控制数据范围

14-II.剪绳子 中通过快速幂,结合模运算规律,控制了幂运算结果的范围不会超过 1_000_000_007
func modPow(_ x: Int, _ n: Int) -> Int {
var res = 1
var x = x
var n = n
while n > 0 {
if n & 1 == 1 {
res *= x
res %= 1_000_000_007 // 限制了数据范围
}
x *= x
x %= 1_000_000_007 // 限制了数据范围
n >>= 1
}
return res
}