c - 将两个 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。