使用GMP底层API实现192位整数除法的函数选型疑问

你需要先对除数做有效长度归一化，再调用对应mpn函数，就能覆盖所有随机3-limb（192位）整数的除法场景，包括除数为65-128位的情况。具体步骤如下：

核心思路 #

GMP的mpn_tdiv_qr要求除数最高有效limb非零，本质是要求除数是归一化的（无前导零limb）。对于随机生成的3-limb除数，我们先判断它的有效limb长度（1/2/3），再分情况调用合适的函数，最后将结果还原为3-limb的固定长度。

具体实现（基于64位limb） #

假设你的uint192类型对应GMP的小端存储：limb[0]是最低64位，limb[2]是最高64位。定义变量：

mp_limb_t a[3];    // 被除数（3-limb）
mp_limb_t d[3];    // 除数（3-limb）
mp_limb_t q[3];    // 商（固定3-limb）
mp_limb_t r[3];    // 余数（固定3-limb）

1. 判断除数的有效长度

先确定除数的非零最高limb位置，得到有效长度k：

int k;
if (d[2] != 0) {
    k = 3; // 除数是完整3-limb（≥129位）
} else if (d[1] != 0) {
    k = 2; // 除数是2-limb（65~128位）
} else {
    k = 1; // 除数是1-limb（≤64位）
}

2. 分情况处理除法

• 情况1：除数是3-limb（k=3）
  直接调用mpn_tdiv_qr，此时商最多1-limb（3-limb除以3-limb，商不会超过64位），补零扩展为3-limb：

  mp_limb_t q_tmp[1];
  // q_tmp存储商（1-limb），r存储余数（3-limb）
  mpn_tdiv_qr(q_tmp, r, 0, a, 3, d, 3);
  // 扩展商为3-limb
  q[0] = q_tmp[0];
  q[1] = 0;
  q[2] = 0;
  

• 情况2：除数是2-limb（k=2）
  调用mpn_tdiv_qr处理3-limb被除数和2-limb除数，商为2-limb，余数为2-limb，补零扩展为3-limb：

  mp_limb_t q_tmp[2], r_tmp[2];
  // q_tmp存储商（2-limb），r_tmp存储余数（2-limb）
  mpn_tdiv_qr(q_tmp, r_tmp, 0, a, 3, d, 2);
  // 扩展商和余数为3-limb
  q[0] = q_tmp[0];
  q[1] = q_tmp[1];
  q[2] = 0;
  r[0] = r_tmp[0];
  r[1] = r_tmp[1];
  r[2] = 0;
  

• 情况3：除数是1-limb（k=1）
  直接用mpn_divrem_1处理，它专门支持单limb除数，商直接是3-limb，余数补零扩展：

  mp_limb_t r_tmp;
  // q直接存储3-limb商，r_tmp存储单limb余数
  r_tmp = mpn_divrem_1(q, 0, a, 3, d[0]);
  // 扩展余数为3-limb
  r[0] = r_tmp;
  r[1] = 0;
  r[2] = 0;
  

关键说明 #

• 所有情况处理后，余数r都会满足r < d（符合除法定义）。
• 小端存储的顺序要和你的uint192类型保持一致，避免数据错位。

内容的提问来源于stack exchange，提问作者Silicomancer