(arbitrary-precision-arithmetic)=
# 0x03 高精度运算

```{epigraph}
The art of programming is the skill of controlling complexity.

-- Marijn Haverbeke
```

```{margin}
其实可以看作一类模拟题。
```

```{note}
**高精度运算（[Arbitrary-precision arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic)）** 
是指在计算机中进行数字运算时，使用一种算法或数据结构，可以支持更高位数的数字运算。
通常情况下，计算机中使用的数据类型有其固定的长度，例如，32 位整数（`int32`）的长度为 32 个二进制位 。
而高精度运算则允许处理更大的数字，可能有数百位或数千位。
需要实现高精度运算的原因有很多，其中最主要的原因是在某些应用程序中需要处理非常大的数字，
例如大型科学计算、加密算法、货币计算、精度要求较高的统计分析等。
在这些情况下，如果使用传统的数据类型和算法进行计算，可能会导致精度丢失或计算错误。
因此，使用高精度运算可以确保计算的准确性，并提高计算效率和可靠性。
```
[^store]
[^store]: {-} 💡 在进行高精度计算时，通常将每个数字的各个位数按照从低位到高位的顺序进行存储，
这是因为这种存储方式更符合我们进行手算的习惯，也更容易理解和计算。
与此同时也能够让权值位始终保持对齐，方便模拟计算过程。

```{attention}
- 这里更多讨论的是高精度整数的运算（大数 Big Number），而不是高精度浮点数的运算；
- 本文中的高精度整数指的是 **非负整数**，即大于等于 0 的整数；
- 本文中的高精度整数使用 `vector<int>` 来表示，其中每个元素表示一个位数，
  - 例如 `123` 表示为 `[3, 2, 1]` ；
  - 例如 `123456789` 表示为 `[9, 8, 7, 6, 5, 4, 3, 2, 1]` ；
```

(read-big-number)=
## 读入与还原

通常题目给出的大数都是以字符串的形式给出的，因此我们需要将其转换为 `vector<int>` 的形式。

```{code-block} cpp

vector<int> read(string &numString) { // E.g: 123456789
    vector<int> num;
    for (int i = numString.size() - 1; i >= 0; --i)
        num.push_back(numString[i] - '0');
    return num;  // [9, 8, 7, 6, 5, 4, 3, 2, 1]
}
```

最终要能够解析还原回字符串：

```{code-block} cpp
string parse(vector<int> &num) {
    string numString = "";
    for (int i = num.size() - 1; i >= 0; --i)
        numString += num[i] + '0';
    return numString;  // "123456789"
}
```

(big-number-add)=
## 高精度加法

基本思路：模拟手算过程，从低位到高位逐位相加，下面代码中的 `tmp` 变量既可以存放加法结果，也可以表示进位（carry）。
如果最高位加法有产生进位，则将其也加入到结果中。

```{code-block} cpp
vector<int> add(vector<int> &a, vector<int> &b) {
    vector<int> c;
    int tmp = 0;  // store carray or sum
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size()) tmp += a[i];
        if (i < b.size()) tmp += b[i];
        c.push_back(tmp % 10);
        tmp /= 10; // carry
    }
    if (tmp) c.push_back(1);
    return c;
}
```

{bdg-link-primary-line}`LeeCode 415 <https://leetcode.com/problems/add-strings/>`
{bdg-link-primary-line}`AcWing 791 <https://www.acwing.com/problem/content/793/>`

(big-number-sub)=
## 高精度减法

基本思路：模拟手算过程，从低位到高位逐位相减，下面代码中的 `tmp` 变量既可以存放减法结果，也可以表示借位（borrow）。
值得注意的是，相较于加法，减法由于不满足交换律，因此为了简化讨论情况，我们通过 `geq` 函数来比较两个数的大小，
人为地保证后续计算的 `a` 大于等于 `b`，然后再进行减法运算。
如果 `a` 小于 `b`，则交换 `a` 和 `b` 的位置（有标志变量 `swap`），最后再加上一个负号。
另外注意减法 **需要处理前导 0**. [^leading-zero]

[^leading-zero]: {-} 
🔍︎ 例如 `a = 123456789`, `b = 123456780`，`a - b == 9`, 
`vector<int> c == [9, 0, 0, 0, 0, 0, 0, 0, 0]`;

```{code-block} cpp
bool geq(vector<int> &a, vector<int> &b) {
    while (a.back() == 0 && a.size() > 1) a.pop_back();
    while (b.back() == 0 && b.size() > 1) b.pop_back();
    
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; --i)
        if (a[i] != b[i]) return a[i] > b[i];
    return true;
}

vector<int> sub(vector<int> &a, vector<int> &b, bool swap = false) {
    // make sure a is greater than or equal with b
    if (!geq(a, b)) return sub(b, a, true);

    vector<int> c;
    int tmp = 0;
    for (int i = 0; i < a.size() || i < b.size(); ++i) {
        if (i < a.size()) tmp += a[i];
        if (i < b.size()) tmp -= b[i];
        c.push_back((tmp + 10) % 10);
        tmp = tmp < 0 ? -1 : 0;  // borrow
    }

    // handle with leading zero and negative cases
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    if (swap) c.back() *= -1;
    return c;
}
```

{bdg-link-primary-line}`AcWing 792 <https://www.acwing.com/problem/content/794/>`

(big-number-mul)=
## 高精度乘法

基本原理：模拟竖式乘法 (AxB=C) ——

* （子功能实现）将 B 按十进制位拆成多项，分别与 A 相乘得到候选 `candidate`;
* （问题转化）计算 C 的过程即计算多项 `candidate` 错位求和，模拟手算加法；

```{attention}
:class: margin
不同项错位求和时，对应下标变化规律性极强，建议使用具体实例模拟一下计算过程辅助理解。
以及实际的求和次数由 `candidates.front().size()` 决定（而非 `a.size()` 值）；
```

```{margin}
$$
\begin{array}{r} 
         & & & & 1 & 2 & 3 & 4 \\
    \times & & & & & 9 & 2 & 3 \\
  \hline & & & & 3 & 7 & 0 & 2 \\
       & & & 2 & 4 & 6 & 8 \\
+  & 1 & 1 & 1 & 0 & 6 \\
\hline 
   & 1 & 1 & 3 & 8 & 9 & 8 & 2 \\
\end{array}
$$
```

```{code-block} cpp 
:emphasize-lines: 20, 21

vector<int> mul_per_digit(vector<int> &a, int b) {
    vector<int> candidate;  
    int tmp = 0;
    for (int i = 0; i < a.size(); ++i) {
        tmp += a[i] * b;
        candidate.push_back(tmp % 10);
        tmp /= 10;
    }
    if (tmp) candidate.push_back(tmp);
    return candidate;
}

vector<int> mul(vector<int> &a, vector<int> &b) {
    vector<int> c;
    vector<vector<int>> candidates;
    for (int i = 0; i < b.size(); ++i) {
        candidates.push_back(mul_per_digit(a, b[i]));
    }
    int tmp = 0;
    for (int i = 0; i < candidates.front().size() + b.size(); ++i) {
        for (int digit = i, idx = 0; idx < b.size(); ++idx, --digit) {
            if (digit >= 0 && digit <= a.size())
                tmp += candidates[idx][digit];
        }
        c.push_back(tmp % 10);
        tmp /= 10;
    }
    if (tmp) c.push_back(tmp);
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    return c;
}
```

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/Multiplication_algorithm>`
{bdg-link-primary-line}`LeeCode 43 <https://leetcode.com/problems/multiply-strings/>`
{bdg-link-primary-line}`AcWing 793 <https://www.acwing.com/problem/content/795/>`

(big-number-div)=
## 高精度除法

基本原理：模拟竖式除法（A/B=C...R），辗转相减，将除法转换为多次减法运算—— 

* 复用了高精度减法中的 `geq` 和 `sub` 函数（由于借位的存在，一定要处理前导 0）； [^div-leading-zero]
* 竖式除法的每一小步，都是用当前余数 `reamain` 尝试与除数 `b` 相除，得到当前最高位商和新余数；
* 用减法运算代替除法，当前的 `reamin` 减去除数 `b`，直到 `remain` 的长度小于 `b`, 减的次数即当前位的商；
* 如果 `remain` 的长度小于 `b`，则将 `a` 的下一位补充到 `remain` 的最后，商位补 0, 直到能继续减法运算；
* 除法过程中，如果在最后一项产生了借位，则计算完当前余数后，就不用再继续计算了。

[^div-leading-zero]: {-}
🔍︎ 例如计算 `230000027 / 23` 时, 中间过程会出现许多 `remain` 为 0 或包含前导 0 的情况，
需要在 `geq` 和 `sub` 中进行处理，同时起到剪枝的效果。

```{figure} https://upload.wikimedia.org/wikipedia/commons/f/f2/LongDivisionAnimated.gif
---
figclass: margin
alt: Long division
name: long-division
---
[Long division](https://en.wikipedia.org/wiki/Long_division#Example_with_multi-digit_divisor)
```

```{margin}
使用上面的示例，当前的代码实现中将从开头的 12 作为 `remain` 开始尝试除以 37，因此会有前导 0, 即得到商为 034061.
```

```{code-block} cpp
:emphasize-lines: 20-25

vector<int> div(vector<int> &a, vector<int> &b, vector<int> &remainder) {
    if (a.size() < b.size()) {
        remainder = a;
        return vector<int> (1, 0);
    }
    
    vector<int> c;
    int tmp = 0;
    
    vector<int> remain(a.end() - b.size(), a.end());
    
    int cur = a.size() - b.size(); // current digit in dividend to be handled
    while (cur >= 0) {

        while (cur >= 1 && !geq(remain, b)) {
            c.push_back(0);  // borrow
            remain.insert(remain.begin(), a[--cur]);  // shift remain item
        }
        
        while (geq(remain, b)) {  // sub multi-times
            remain = sub(remain, b);
            tmp += 1;
        }
        c.push_back(tmp);
        tmp = 0;
        
        if (cur == 0) break; // when borrowed the last digit, jump next step
        remain.insert(remain.begin(), a[--cur]); // supplement the remainder
    }

    remainder = remain;
    
    reverse(c.begin(), c.end());
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    
    return c;
}
```

{bdg-link-primary-line}`Wikipedia <https://en.wikipedia.org/wiki/Long_division>`
{bdg-link-primary-line}`AcWing 794 <https://www.acwing.com/problem/content/796/>`

```{warning}
另一种辗转相减的做法是，先将除数乘以 10 的幂，使得除数和被除数的位数相同，
然后再仿照上面的思路不断进行减法与“去”位（对除数），直到不能再去位。
虽然总是能取得一样的结果，但是这种做法的复杂度取决于被除数的位数，而原方法复杂度取决于除数的位数，
显然原方法更优。
```