下面的内容面向需要用 任意精度整数/小数（big integer / big decimal / arbitrary-precision arithmetic）做工程实现或算法研究的人。我们从表示方法、基础运算、进阶算法、模运算与密码学优化、实现细节与工程实践、到常用库与测试策略，给出清晰、可落地的实现思路与伪代码／示例，便于直接上手或用于教学/文案。

一、为什么需要高精度（动机）

  • 超出原生整数范围（例如大素数、RSA、椭圆曲线参数）。
  • 科学计算需更高精度的浮点（高精度小数、任意精度浮点）。
  • 精确算术（金融、计量）避免浮点误差。
  • 算法与数论研究需要精确的大数运算。

二、数的表示（核心设计决定性能）

常见选择——位元组/“limb”数组（每个 limb 存放若干位），两种主流基数：

  1. 基 (B = 2^{w})（w 通常为 32 或 64）
    • 优点：与机器字直接对应，移位、乘法快，易实现乘法/加法的 CPU 原语（带进位/溢出）。
    • 每个 limb 存为 uint32/uint64。
    • 常见实现：GMP、Go math/big。
  2. 基 (B = 10^{k})（如 10^9）
    • 优点：便于与十进制 I/O 交互（格式化快），实现简单。
    • 常用于教学、简单脚本实现（Python 学生实现）。

表示形式

  • 符号位 separate（正/负）。
  • little-endian limbs（低位 limb 在数组下标 0）便于加减。也可用 big-endian。
  • 归一化（无前导 0 limb）以保持唯一性和比较简单。

三、基础运算（O(n) 或 O(n^2) 时间）

设两数长度为 (n)（limb 个数），下面均指 limb 级别复杂度。

3.1 加法 / 减法（线性）

  • 逐 limb 加/减并处理进位/借位。
  • 伪代码（little-endian）：
function add(A[], B[]):
  carry = 0
  for i in 0..maxlen-1:
    t = carry
    if i < len(A): t += A[i]
    if i < len(B): t += B[i]
    R[i] = t mod B
    carry = t div B
  if carry: append carry
  normalize(R)
  return R
  • 复杂度：(O(n))。

3.2 乘法（学校乘法，O(n^2)）

  • 双重循环，逐 limb 相乘并累加到结果对应位置，处理进位。
  • 伪代码：
function mul(A[], B[]):
  R = zeros(len(A)+len(B))
  for i in 0..len(A)-1:
    carry = 0
    for j in 0..len(B)-1:
      t = R[i+j] + A[i]*B[j] + carry
      R[i+j] = t mod B
      carry = t div B
    R[i+len(B)] += carry
  normalize(R)
  return R
  • 复杂度：(O(n^2))。对小 n（如 < 64–128 limbs）常最快。

3.3 比较 / 移位

  • 比较：先比较长度，再自高位开始比较 limb。
  • 左/右移：移 limb（整 limb 移位） + 在 limb 内的位移（跨 limb carry）。

四、进阶乘法算法（为大数加速）

当长度 (n) 很大时，O(n^2) 不够快。常用算法：

4.1 Karatsuba（分治，O(n^{1.585})）

  • 思路：将数分成高/低两半 (x = x_1 B^m + x_0)，乘法 (xy) 用 3 次半大小乘法 + 加减：
    [
    z_0 = x_0 y_0,\quad z_2 = x_1 y_1,\quad z_1 = (x_0 + x_1)(y_0 + y_1) – z_0 – z_2
    ]
    然后组合为 (z_2 B^{2m} + z_1 B^m + z_0)。
  • 伪代码：递归实现，通常在 n 小于某阈值（threshold）返回学校乘法。
  • 复杂度：(O(n^{\log_2 3})\approx O(n^{1.585}))。

4.2 Toom-Cook（Toom-3、Toom-k）

  • 更高阶的分割（3 或更多分段），需要插值与多次评价，复杂度更低但实现复杂、常数大。
  • 常见 Toom-3（分 3 段）在中等大 n 下高效。

4.3 FFT / Schönhage–Strassen / Furer（O(n log n)）

  • 思路：把乘法转为多项式乘法，再用快速傅里叶变换（FFT）做卷积（在复数域或 NTT 在模素域）。
  • 适合非常大的整数（数千到百万位）。实现复杂，需处理精度和进位恢复问题。
  • Schönhage–Strassen 使用离散傅里叶变换在模 (2^{k}+1) 的域上实现超快乘法。
  • 复杂度：约 (O(n \log n \log\log n))（具体依算法不同）。

五、除法与求商（Division）

常用方法：

5.1 朴素“长除法”/Knuth 算法 D

  • 类似小学长除法，估商、乘回、减去、修正估商。
  • Knuth 在《The Art of Computer Programming》Vol.2 中给出规范实现（处理多 limb 估商、修正）。复杂度 (O(nm))（n 被除数长度，m 除数长度）。
  • 实现难点：估商 q̂ 的计算与修正；处理基数边界。

5.2 通过逆（Newton-Raphson）快速除法

  • 将除法转为乘以倒数：求 (1/d) 的高精度近似，然后乘以被除数，再截断得到商。
  • 使用 Newton 迭代求倒数：精度逐步翻倍，复杂度与乘法相同量级（因此适合大数）。
  • 常用于高性能库。

六、模运算与密码学优化

模运算在加密、RSA、ECC 中极常用。高效实现关键。

6.1 直接模运算

  • (a \bmod m)：用除法取余（复杂）。多次模乘可用重复模减/模乘。

6.2 Barrett 减法（Barrett Reduction）

  • 减少除法次数：预先计算 (\mu = \lfloor B^{2k}/m\rfloor)，之后用乘法与移位估计商并修正。
  • 适合固定模 (m) 的大量模运算。

6.3 Montgomery 乘法（最常见）

  • 将数转为 Montgomery 域（R 模基，例如 (R = B^k)），在该域中模乘避免显式除法（用移位和乘法替代除法）。
  • 需要事先将数转换进出 Montgomery 形式。用于快速模乘与模幂。
  • 非常适合大数模乘密集场景（RSA、模幂）。

6.4 快速模幂（modular exponentiation）

  • 指数算法：二进制平方/乘（square-and-multiply），复杂度与指数的二进制位数成正比。结合 Montgomery 可显著加速。
  • 侧信道防护（时间/功耗）在密码学实现中也非常关键（需常时操作）。

6.5 中国剩余定理（CRT）

  • 对 RSA 解密（有两个素因子 p,q）可用 CRT 将模运算分解到较小模 (p,q)，提高速度（约 4×）。
  • 需要正确实现重构与防止侧信道攻击（例如戴明攻击）。

七、高精度小数 / 任意精度浮点

两条路径：

  1. 定点小数：把小数乘以 (10^k) 或 (B^k) 转为整数运算。适合财务场景、固定小数位数。
  2. 任意精度浮点（多精度浮点）：采用类似 IEEE 浮点结构，但尾数（mantissa）用任意长整数，指数为整数：
    • 表示：sign, exponent (int), mantissa (bigint)
    • 运算：对齐指数→尾数加/减→标准化→舍入（多种舍入模式）。
    • 复杂：舍入、溢出/下溢、规范化逻辑都比整数更复杂。
    • 常用库：MPFR（基于 GMP）提供多精度浮点并严格遵守 IEEE-like 舍入。

八、实现细节与工程实践（关键点）

实现高性能高精度库时需注意大量工程细节：

8.1 Limb 大小与对齐

  • 64 位平台优先用 64-bit limb（uint64），但要处理乘法中溢出到 128 位（使用内建 __uint128_t 或平台内乘法指令）。
  • 32 位平台用 32-bit limb。

8.2 基数选择：2^w vs 10^k

  • 内部计算使用二进制基数，输出/输入再做基数转换更高效。
  • 若经常需要十进制 I/O，可用 10^9 的 limb 基数减少转换复杂度。

8.3 溢出/进位处理

  • 使用双宽度寄存器（例如 128 位）来捕获乘法的高低部分，正确传播 carry。
  • 在 C/C++ 中可用 GCC 的 __int128，或使用内嵌汇编（基于平台）。

8.4 内存与分配

  • 池化 limb buffers，避免频繁分配。
  • 使用按需增长并保留容量以减少 realloc 开销。

8.5 阈值选择（混算法）

  • 实际库在不同 n 下选不同算法（学校乘法→Karatsuba→Toom→FFT），需要通过基准测试选择转折点（threshold）。
  • 常见策略：当 n < 32 用学校乘法；32–512 用 Karatsuba；更大用 FFT（阈值依实现与硬件）。

8.6 并行化与 SIMD / 多核

  • 非常大的乘法（FFT）可并行。
  • 利用 CPU 的向量指令（AVX）可以加速 limb 加法/乘法环节（实现复杂）。

8.7 安全性（密码学实现）

  • 常时算法（constant time）避免数据相关分支/内存访问以减小侧信道泄露。
  • 使用 CRT 时注意重构漏洞（引入鲁棒的 blinding）。

九、示例代码（教学性、非高效生产版）

9.1 Python：简单基数为 10^9 的大整数类（示意）

BASE = 10**9

def add(a, b):
    # a,b as lists little-endian
    n = max(len(a), len(b))
    res = []
    carry = 0
    for i in range(n):
        x = carry
        if i &lt; len(a): x += a[i]
        if i &lt; len(b): x += b[i]
        res.append(x % BASE)
        carry = x // BASE
    if carry: res.append(carry)
    # trim zeros
    while len(res) > 1 and res[-1] == 0: res.pop()
    return res

def mul_school(a, b):
    res = [0] * (len(a) + len(b))
    for i in range(len(a)):
        carry = 0
        for j in range(len(b)):
            t = res[i+j] + a[i]*b[j] + carry
            res[i+j] = t % BASE
            carry = t // BASE
        res[i+len(b)] += carry
    while len(res) > 1 and res[-1] == 0: res.pop()
    return res

9.2 C++（伪示意）：使用 uint32_t limb 的加法要点

using limb = uint32_t;
using dlimb = uint64_t; // double width

void add(const vector&lt;limb>&amp; A, const vector&lt;limb>&amp; B, vector&lt;limb>&amp; R){
    size_t n = max(A.size(), B.size());
    R.assign(n, 0);
    dlimb carry = 0;
    for(size_t i=0;i&lt;n;i++){
        dlimb t = carry;
        if(i &lt; A.size()) t += A[i];
        if(i &lt; B.size()) t += B[i];
        R[i] = (limb)(t &amp; 0xFFFFFFFFu);
        carry = t >> 32;
    }
    if(carry) R.push_back((limb)carry);
}

生产级实现要处理归一化、内存复用、异常边界。

十、常用高精度库（工程建议）

  • GMP（GNU MP）：C 语言，高性能，支持整数/有理数/浮点，底层广泛优化（汇编）。生产级首选。
  • MPFR：基于 GMP 的任意精度浮点库（带舍入规则）。
  • OpenSSL BigNum / BIGNUM：常用于加密（但内部实现与 API 不同）。
  • Boost.Multiprecision（C++）：C++ 风格 arbitrary-precision。
  • Python 内建 int / decimal：Python 的 int 是任意精度，适合快速开发；decimal 支持任意精度十进小数。
  • Go math/big：标准库，支持 big.Int、big.Rat、big.Float。
  • Java BigInteger / BigDecimal：成熟实现，常用于企业级应用。

选择建议：对性能/规模有极高要求选 GMP；语言集成/快速开发用对应语言内建库或 Boost。

十一、测试、验证与基准

  • 单元测试：随机测试（随机大整数、边界 case：0、1、最大 limb、不同长度）。
  • 交叉验证：对照 GMP / Python int 等作为“金标准”。
  • 基准（microbench）：测不同长度下的加、乘、除、模、模幂时间，确定算法阈值（threshold）。
  • 精度测试（小数/浮点）：比较舍入模式、四舍五入/向下/向上/近偶位等。
  • 安全测试：对密码学实现测试常时性、侧信道敏感点（时间差异测量）。

十二、常见坑 & 优化建议（经验集）

  • 不要 用字符串逐字符做大数乘法（极慢），应使用 limb 结构。
  • 阈值很重要：混合使用学校乘法 / Karatsuba / FFT，并靠基准调整临界点。
  • I/O：十进制与二进制转换可能成为瓶颈。使用基数 10^9/10^18 可减少十进制转换次数。
  • 避免频繁内存分配：使用预分配/内存池。
  • 并行与向量化：在超大规模（百万位）时值得做，但增加实现复杂度。
  • 安全实现：密码学场景下，优先常时实现，避免表查或数据相关分支。

十三、学习路线与参考（书单 / 关键论文）

  • Knuth, The Art of Computer Programming, Vol. 2（关于多精度算法、Knuth 算法 D 等）。
  • GMP 项目文档与源代码（学习工程级实现）。
  • Schönhage & Strassen — “Schnelle Multiplikation großer Zahlen” （FFT 大数乘法基础）。
  • MPFR 手册（高精度浮点实现细节）。
  • 在线资源：GMP、MPFR 官网文档，以及各语言自带 BigInt 文档（Python、Go、Java）。

十四、实战任务（练习）

  1. 用基数 (10^9) 在 Python 实现 add, sub, mul（学校法），并测试与 Python 内置 int 的一致性。
  2. 在 C++ 中实现基于 32-bit limb 的乘法并用 __int128 做加速。
  3. 实现 Karatsuba，并基准比较学校法和 Karatsuba 的交替点（不同平台结果不同）。
  4. 用 FFT（可用 numpy/fftw 做原型）实现大整数乘法，学习如何处理进位并恢复结果。
  5. 实现 Montgomery 乘法并用它实现模幂（RSA 样例）。

十五、结语（落地建议）

  • 工程优先：先用成熟库（GMP / 语言自带）以节省开发成本。
  • 若要自己实现：从简单的 limb 表示 + 学校算法开始，逐步加入 Karatsuba、Toom、FFT；用基准驱动阈值选择。
  • 对于密码学：重点在正确性、性能和安全（常时性/防侧信道）。
  • 文档与测试不可少：实现后要有系统的单测、基准和对照验证。

以下是有关高精度算法（大整数/任意精度算术）的一些参考资料和出站链接，阿 杰可以将其作为文案中“参考资料”部分的来源。

📚 推荐参考资料

  • The Art of Computer Programming（Vol. 2 “Seminumerical Algorithms” 中含有多精度整数运算相关章节） (维基百科)
  • A Computational Introduction to Number Theory and Algebra — 其中 Chapter “Computing with large integers” 专门讨论大整数运算。 (Cambridge University Press & Assessment)
  • Fast Algorithms for Arithmetic Computations of Big Numbers — 针对大数运算的算法专著。 (亚马逊)
  • 在线分析文章 “Understanding and implementing a simple big (unsigned) big integer library” — 分享从头实现大整数库的思路。 (sunshine2k.de)

🔗 出站链接／网络资源

  • Karatsuba algorithm（快速大整数乘法）简介 — Brilliant Wiki。 (brilliant.org)
  • Schönhage-Strassen 算法（更大数规模的乘法） — Wikipedia。 (维基百科)
  • “Karatsuba Algorithm: Fast Integer Multiplication” — Medium 博文。 (Medium)
  • “Efficient Big Integer Multiplication and Squaring Algorithms for Cryptographic Applications” — 研究论文。 (ResearchGate)
  • “Big Integer Design” — 在线文章，讨论多精度整数库设计。 (bearssl.org)