# 03.快速幂

## 前言

幂运算是我们最常用的运算之一。如果我们要求 x 的 N 次幂，那么想当然的就会写出一个 N 次的循环，然后累乘得到结果。这种幂运算的复杂度是O(N)。

```swift
var res = 1
for _ in 0..<n {
    res *= x
}
return res
```

## 一、 快速幂

***那么有没有更快的运算方式呢？***

在计算机领域有一种常用的快速幂算法：`蒙哥马利幂（Montgomery reduction）算法`。将复杂度&#x4ECE;***O(N)*** 降到了 ***O(logN)***

### 1.1 思路一：递归

* 若 N 为偶数，可以先求 xN/2，然后再平方。
* 若 N 为奇数，可以先求 x(N-1)/2，然后再平方，再乘以x

快速幂的最基础思想就是上面两条了。

求解 xN/2，x(N-1)/2 时也可以用到上面的思路，每次将指数除以2，每次都可以将复杂度降低一半，知道最后指数为1。

#### Swift实现

* 这里不考虑大数，仅作为思路展示

```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 为例进行推导。

&#x20;x14(10) = x1110(2) = x1000(2) \* x100(2) \* x10(2)

换个方向，更直观：

&#x20;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            |
| :----: | :--: | :-----------------------: |
| 111`0` |   0  |           x0(2)           |
| 11`1`0 |  10  |           x10(2)          |
| 1`1`10 |  100 |     x10(2) \* x100(2)     |
| `1`110 | 1000 | x10(2) *x100(2)* x1000(2) |

#### Swift实现

* 这里不考虑大数，仅作为思路展示

```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 参考

[Pecco-算法学习笔记(4)：快速幂](https://zhuanlan.zhihu.com/p/95902286)

[【朝夕的ACM笔记】杂项-快速幂](https://zhuanlan.zhihu.com/p/112312044)

## 二、 快速幂取模

### 2.1 模运算规律

* (a + b) % p = (a % p + b % p) % p&#x20;
* (a - b) % p = (a % p - b % p + p) % p&#x20;
* (a *b) % p = (a % p* b % p) % p&#x20;
* ab % p = ((a % p)b) % p&#x20;

> 根据这个规律，可以推导出[同余性质](/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/02.-tong-yu-xing-zhi.md)

### 2.2 常见问题场景

我们经常会看到 `输出结果对x取模`。这种题目一般考察两点：

* 在原算法的基础上，多一个取模运算来考察你对取模运算规律的掌握
* 大数据时数据增长太快，64 位甚至 128 位的整形无法表示
  * [「剑指Offer」14-II.剪绳子](/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/14ii.-jian-sheng-zi.md)是个典型问题
    * [题解](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/tan-xin-kuai-su-mi-by-happy-austin9mq-6bxz/)

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

`14-II.剪绳子` 中通过快速幂，结合模运算规律，控制了幂运算结果的范围不会超过 `1_000_000_007`。

```swift
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
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/ji-qiao/03.-kuai-su-mi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.