高精度加减法

为什么需要高精度计算？

在 C++ 中，基础的整数类型（如 int、long long）有存储范围的限制：

• int：通常为 32 位，最大值约 21 亿 (2.1 × 10⁹)
• long long：通常为 64 位，最大值约 9 百亿亿 (9.2 × 10¹⁸)

当我们需要处理超出这些范围的超大整数时，比如在以下场景，内置类型就不够用了：

• 密码学计算（如 RSA 算法中的大素数运算）
• 科学计算（处理极大数据，如天文距离、粒子数量）
• 金融领域（需要极高精度的金额计算）
• 算法竞赛（题目常常要求处理大数）

如何存储大整数？

既然无法直接用 long long 存储，我们可以换种方式：

• 字符串 (string)：每个字符存储数字的一位。例如 "12345..."。这是最直观的方式。
• 整型数组 (vector<int> 或 int[])：数组的每个元素存储数字的一位，或者为了优化效率存储多位（如每 4 位或 8 位存一个元素）。通常将数字的**低位存储在数组的低索引**处（如个位在 `a[0]`），方便进位/借位处理。

高精度加法 (Addition)

高精度加法的核心思想是**模拟我们手算加法的过程**：列竖式，从个位（最低位）开始，逐位相加，并处理进位。

算法步骤 (使用字符串存储)

1. 将两个大整数（字符串形式）反转，使得个位在前，方便从低位开始处理。
2. 初始化进位 carry = 0。
3. 从索引 0 开始，逐位遍历两个（反转后的）字符串：
   • 取出当前位的数字 (a[i] - '0', b[i] - '0')。如果某个数已经遍历完，则该位视为 0。
   • 计算当前位的和：sum = digit_a + digit_b + carry。
   • 当前位的结果是 sum % 10。将其转换为字符后追加到结果字符串。
   • 新的进位是 carry = sum / 10 (整数除法)。
4. 遍历结束后，如果最终 carry > 0，需要将这个进位追加到结果字符串的末尾。
5. 将结果字符串再次反转，得到最终的正确顺序的和。
6. 注意处理结果可能为 "0" 的情况。

高精度减法 (Subtraction)

高精度减法同样模拟手算减法：列竖式，从个位（最低位）开始，逐位相减。如果不够减，则向高位**借位**。

算法步骤 (处理非负整数，a >= b)

1. **比较大小**：首先要确保被减数 `a` 大于等于减数 `b`。如果 `a < b`，则交换 `a` 和 `b`，计算 `b - a`，最后在结果前加上负号（这部分在基础演示中可能简化，但完整实现需要考虑）。
2. 同样，将两个大整数（字符串）反转。
3. 初始化借位 borrow = 0。
4. 从索引 0 开始，逐位遍历两个（反转后的）字符串：
   • 取出当前位的数字 (a[i] - '0', b[i] - '0')。b 遍历完则视为 0。
   • 计算被减数当前位受上一位借位影响后的值：digit_a = digit_a - borrow。
   • 判断是否需要向更高位借位：如果 digit_a < digit_b，则需要借位。当前位变为 digit_a + 10，同时设置下一位的借位 borrow = 1。否则，borrow = 0。
   • 计算当前位的差：diff = digit_a - digit_b。
   • 将差值 diff 转换为字符追加到结果字符串。
5. 遍历结束后，结果字符串可能包含前导零（例如 1000 - 999 = 0001）。需要**去除前导零**：从结果末尾（反转后的最高位）向前查找，直到找到第一个非 '0' 的字符，或者只剩下一个 '0'。
6. 将处理好前导零的结果字符串再次反转，得到最终答案。

练习与巩固

知识延伸

高精度乘法与除法

加减法相对简单，乘除法复杂度更高：

• 乘法:
  • 朴素算法：模拟手算乘法（一个数的每一位乘另一个数，然后错位相加），时间复杂度 O(N*M) 或 O(N²)。
  • Karatsuba 算法：分治法，将乘法分解为规模更小的乘法和加减法，时间复杂度 O(N^log₂3 ≈ N^1.58)。
  • FFT/NTT 算法：利用快速傅里叶变换 (FFT) 或数论变换 (NTT)，将大数乘法转换为多项式乘法，在频域进行点积运算，时间复杂度优化至 O(N log N)。这是目前最快的大整数乘法算法之一。
• 除法:
  • 通常模拟手算除法（试商、相减、余数），涉及多次高精度减法和比较，复杂度较高，约为 O(N*M) 或 O(N²)。
  • 也可以基于牛顿迭代法等进行优化。

高精度小数

处理高精度小数通常有几种方法：

• 定点数：将所有数乘以一个大的 10 的幂（如 10^k），转换为整数进行计算，最后再除以 10^k 得到结果。需要预先确定精度 k。
• 字符串/数组模拟：分别存储整数和小数部分，或者将整个数（包括小数点）视为一个大数处理，计算时注意对齐小数点、处理小数位的进位/借位。
• 使用专门的库（如 GMP 的 mpf_t）。

其他编程语言中的大数支持

不像 C++ 需要手动实现或依赖库，许多现代语言内置了大数支持：

• Python: int 类型自动支持任意精度整数。运算就像普通整数一样简单。
• Java: 提供 java.math.BigInteger 类用于任意精度整数，java.math.BigDecimal 用于任意精度定点小数。
• JavaScript: ES2020 引入了 BigInt 类型 (以 `n` 结尾，如 123n) 用于处理大于 Number.MAX_SAFE_INTEGER 的整数。但 BigInt 和 Number 不能混合运算。
• C#: System.Numerics.BigInteger 结构。
• Go: math/big 包提供了 Int 和 Rat (有理数)。

C++ 标准库与第三方库

虽然 C++ 标准库没有内置高精度类型，但有强大的第三方库可用：

• GMP (GNU Multiple Precision Arithmetic Library): C 语言库，提供非常高效和功能全面的任意精度算术运算，有 C++ 封装。是性能要求高的场景下的首选。
• Boost.Multiprecision: Boost 库的一部分，提供 C++ 风格的多精度类型，可以后端选择 GMP 或其他实现。