将两个128位整数相乘

Question

我试图在C中乘以两个128位整数.

这是我的算法:

将两个128位序列拆分为S1和S2.

然后将S1分成S11(前/上半部分)和S12(后/下半部分)并将S2分成S21(前/上半部分)和S22(后/下半部分).

将S12乘以S22 ... = S1222.

将S11乘以S21 ... = S1121,然后将其乘以2 ^ 128进行位移

将S1222和S1121组合成新阵列的前半部分和后半部分.我们称之为"Array1".新数组的长度是S1的两倍.

然后我们必须将S12乘以S21并将S11乘以S22.我将这两个相乘得到S1221和S1122(并相应地对它们进行位移).现在我必须将它们添加到Array1.这是我要求帮助的部分.我不知道如何将这些一个一个地添加到Array1.请记住,当您从Array1的3/4到Array1的1/4时,可能会有一个1的进位,因为这是需要添加S1221和S1122的跨度.

我的问题是:如何将dstM1和dstM2添加到已填充的数组d中？

Answer 1

如果您使用的是gcc或clang，则可以直接使用__int128和unsigned __int128。

Answer 2

总结您的问题：如何将两个传播进位的（无符号）整数数组相加。

uint16_t foo[4];  // 0000 aaaa FFFF cccc
uint16_t bar[4];  // dddd eeee FFFF 0000

优点是“FFFF+FFFF+1”只是 (1)FFFF。因此，始终可以在每个字中添加进位，而不会产生额外的进位（就好像总和可以是 20000）。

进行临时求和：sum = foo[3] + bar[3] + carry;进位最初为 0，该和要么产生新的进位，要么不产生新的进位。

• 进位由 (A+B) 产生，如果(A+B) < A
• 当求和 (A+B+c) 时，如果产生进位((A + c) < A) || (((A + c) + B) < B)

另一种可能性是通过对列中的多项求和来计算“多位进位”，这通常出现在 bignum 乘法中：

            AAAA BBBB CCCC
       DDDD EEEE FFFF ....
  GGGG HHHH IIII .... ....
--------------------------
  col4 col3 col2 col1 col0

现在，每一列都会生成 32 位或 64 位结果以及不一定适合单个位的进位。

uint32_t sum_low = carry_in_from_previous_column;
uint32_t sum_high = 0;

for (i = 0; i < N; i++) {
     sum_low += matrix[i][column] & 0xffff;
     sum_high += matrix[i][column] >> 16;
}
sum_high += sum_low >> 16;    // add the multibit half carry

result = (sum_low & 0xffff) | (sum_high << 16);
carry_out = sum_high >> 16;