在C语言中进行多精度无符号减法

Question

我正在尝试在C语言中实现有限域（p=2^191-19）上的多精度无符号减法，但我无法解决借位问题！ 我的操作数以基数2^16表示：

typedef unsigned long long T[12];

这意味着T类型数组的每个元素都有16位数据（基数为2^16）。现在我想减去两个T类型的操作数，但我不知道哪一个更小！如果结果为负数，我想将结果加到质数值上，以在模运算中得到正结果。以下是我的实现，基于这本书第30页（多精度减法算法）：

void bigint192_sub(T r, const T a, const T b){
    int i;
    int borrow;
    r[0] = a[0] - b[0];
    borrow = r[0] >> 16;
    r[0] &= 0xFFFF;
    for(i=1;i<12;++i){
        r[i] = a[i] - b[i] - borrow;
        borrow = r[i] >> 16;
        r[i] &= 0xFFFF;
    }
}

但是我得到了错误的答案！

My inputs:
a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576
b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72
Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604
Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604

- A23149577

---

你的输入是什么，期望输出是什么，实际输出又是什么？ - Scott Hunter

这看起来不对。如果a[i]小于b[i]，难道你不会从0x10000借用吗？ - Kerrek SB

@KerrekSB 我在我的问题中放了一个参考。我知道这对我来说似乎很奇怪，但这正是书中所显示的方式！！ - A23149577

Answer 1

你应该修复borrow评估，因为它可能只是0或1。所以你应该将下溢视为borrow等于1：

borrow = (r[i] >> 16) != 0;

此外，我会将函数重写为更一般的形式，因为我们可以将第一次传递视为没有借用：

void bigint192_sub(T r, const T a, const T b){
    int i;
    int borrow;
    for (borrow = 0, i = 0; i < 12; ++i) {
        r[i] = a[i] - b[i] - borrow;
        borrow = (r[i] >> 16) != 0;
        r[i] &= 0xFFFF;
    }
}

- Sergio

---

你也可以写成 borrow = (r[i] >> 16) != 0; // 没必要加 trick 注释。 - Darklighter

@Darklighter嗯，是的，它甚至更简单。谢谢！ - Sergio