7

我试图在 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 中？

4

3 回答 3

5

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

于 2014-02-28T03:28:22.270 回答
3

您陷入无限循环，因为i += 1/32与i += 0.

另外：注意：memcpy(&d[3l/2-i], dstM1, 1/8);是memcpy(&d[1-i], dstM1, 0);

于 2014-02-28T05:38:30.223 回答
1

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

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;
于 2014-02-28T07:19:02.200 回答