乘两个128位的整数 [英] Multiplying two 128-bit ints

问题描述

我想在C乘两个128位的整数。

I'm trying to multiply two 128-bit integers in C.

下面是我的算法：

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

Split the two 128-bit sequences into S1 and S2.

再拆成S1 S11（前/半高）和S12（后/下半部分），分裂成S2 S21（前/半高）和S22（后/下半部分）。

Then split S1 into S11 (front/higher half) and S12 (back/lower half) and split S2 into S21 (front/higher half) and S22 (back/lower half).

S12乘以由S22 ... = S1222。

Multiply S12 by S22... = S1222.

S11乘以由S21 ... = S1121，然后位由2 ^ 128乘以接班

Multiply S11 by S21... = S1121 and then bit shift it by multiplying it by 2^128

联合S1222和S1121是一个新的阵列的正面和背面半部。让我们把它称为数组1。新阵列的长度的两倍长为S1。

Combine S1222 and S1121 to be the front and back halves of a new array. Let's call it "Array1". The new array's length is twice as long as S1.

那么就需要通过S21和S11 S22被乘以S12。我成倍这两个让S1221和S1122，分别为（和位移它们相应）。现在我必须将它们添加到数组1。这是我寻求帮助的部分。我不知道如何接一个，添加这些，一个数组1。请记住，有可能是1进你去的点点滴滴在array1的3/4数组1的1/4，因为这是S1221和S1122需要添加的跨度。

Then we have to multiply S12 by S21 and S11 by S22. I have multiplied these two to get S1221 and S1122, respectively (and bit-shifted them accordingly). Now I have to add them to Array1. This is the part where I'm asking for help. I'm not sure how to add these, one by one, to Array1. Keep in mind there may be a carry of 1 as you go bit by bit from 3/4 of Array1 to 1/4 of Array1, as this is the span where S1221 and S1122 need to be added.

我的问题是：如何添加dstM1和dstM2到数组D，它已经充满

My question is: How do I add dstM1 and dstM2 to the array d, which is already filled?

推荐答案

总结你的问题：你怎么能添加的（无符号）整数两个数组传播进

Summarizing your question: How can you add two arrays of (unsigned) integers propagating the carry.

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

好一点是，'FFFF + FFFF + 1'简直是（1）FFFF。因此，进位总是可以在每个单词被添加，而不产生额外的进位（如如果总和可以是20000）。

The good point is that 'FFFF+FFFF+1' is simply (1)FFFF. Thus the carry can always be added in each word without producing an extra carry (as if the sum could be 20000).

制作一个临时的总和：和= foo的[3] +酒吧[3] +随身携带; 带进位是最初为0，无论这笔钱产生了新的进位，或没有。

Making a temporary sum: sum = foo[3] + bar[3] + carry; with carry being initially 0, either this sum produces a new carry, or not.

• 进从（A + B）产生的，如果（A + B）＆LT; A


• 当总结（A + B + C），进位产生，如果（（A + C）＆LT; A）|| （（（A + C）+ B）＆LT; B）

• Carry is produced from (A+B), if (A+B) < A
• When summing (A+B+c), the carry is produced if ((A + c) < A) || (((A + c) + B) < B)

另一种可能性是通过总结列几个方面，这在BIGNUM乘法经常发生计算多位携带

Another possibility is to calculate "multi-bit carry" by summing up several terms in columns, which occurs often in bignum multiplications:

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

现在每列产生32位或64位的结果，并不一定适合在单个位的进位。

Now each column produces 32-bit or 64-bit result and a carry that doesn't necessarily fit a single bit.

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;

这篇关于乘两个128位的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！