gmp

GMP大数库

（https://gmplib.org/）

大整数（mpz_t）

储存方式

使用“字”（limb）数组来模拟大数。GMP 不使用字符串或高层封装来表示大数，而是模拟 CPU 的“低位字”运算，直接操作无符号整型数组，效率极高。

typedef struct {
  int _mp_alloc;     // 分配了多少个 limb（内存块）
  int _mp_size;      // 实际使用的 limb 个数（正负表示符号）
  mp_limb_t *_mp_d;  // 指向 limb 数组的指针
} __mpz_struct;

typedef __mpz_struct mpz_t[1];

其中：

• mp_limb_t 是一个无符号整型，通常是 unsigned long（32 或 64 位，依 CPU 架构而定）。
• 整数以**低位在前（小端）**的方式存储在 _mp_d 指向的数组中。

运行时动态扩容机制

GMP 在执行运算（如加法、乘法、左移）时，会自动检查当前 _mp_alloc 是否足够。如果不够用，GMP 会调用内部的 _mpz_realloc() 或相关函数来重新分配更大的 limb 数组。

在 GMP 源码中，扩容主要由宏/函数 MPZ_REALLOC 或 _mpz_realloc 实现，它们在以下场景被调用：

• 目标变量 limb 数量不足
• 当前操作将产生更大的结果（如进位）
• 乘法结果位数大于任一操作数

乘法

原理见mpn/mul_n.c，大致思路是根据limb个数而采用不同的算法。

• BELOW_THRESHOLD (n, MUL_TOOM22_THRESHOLD)时，使用mul_basecase算法。
• BELOW_THRESHOLD (n, MUL_TOOM33_THRESHOLD)时，使用mpn_toom22_mul算法。
• BELOW_THRESHOLD (n, MUL_TOOM44_THRESHOLD)时，使用mpn_toom33_mul算法。
• BELOW_THRESHOLD (n, MUL_TOOM6H_THRESHOLD)时，使用mpn_toom44_mul算法.
• BELOW_THRESHOLD (n, MUL_TOOM8H_THRESHOLD)时，使用mpn_toom6h_mul算法。
• BELOW_THRESHOLD (n, MUL_FFT_THRESHOLD)时，使用mpn_toom8h_mul算法。
• 否则最终使用mpn_fft_mul算法。
• 这些阈值是编译时或运行时通过性能基准（tune）测量决定的。