长乘C

Question

我试图在C中实现长乘法（小学方法）。我需要编写我的程序在基地2^32。我不知道如何开始。我有我想在这里使用的算法：

for (i = 0; i < n; i++) { 
    carry = 0; 
    for (j = 0; j < n; j++) { 
     product = a[i] * b[j] + result[i + j] + carry; 
     result[i + j] = p % base; 
     carry = floor(product/base); 
    } 
    result[i + n] = carry; 
} 

任何提示的赞赏。我无法想出一个好主意。

Answer 1

想象一下，我有2个数字与 '数字'：

B_2 B_1 B_0

和：

A_1 A_0

繁殖这些结合在一起，我们首先通过所有的“B的乘由a_0。然后我们将所有的'b'乘以a_1并将结果移到左边（32位），然后再将两个结果相加。

要乘以a_0将a_0移到64位变量中，然后乘以b_0。最低32位是乘法结果c_0的低32位。前32位是进位。

接下来将a_0乘以b_1（再次以64位）。取结果的底部32位并添加进位，这将产生结果的下32位：'c_1'。前32位是下一个进位。重复此操作直到您乘以b中的所有数字。最后的进位是结果的前32位。

然后对a_1执行相同操作。一旦你有了乘法的结果，记得在a_1乘法的末尾添加额外的32位。然后将a_1和1_0的乘法结果加在一起。

Answer 2

主要的“诀窍”是找到一种方式来获取多个两个32位数字，并获得一个64位数字或两个32位数字，它们是高低两半。高半是进位，低半是结果（方式2^32）。在x86机器上有一个汇编语言指令，它完全符合这个要求，但要在直接C/C++中完成，您需要在乘数之前将被乘数转换为某种64位类型，然后使用移位和掩码来分隔高精度数据，和低半部分。

Answer 3

为了使base中的数字成倍数，您需要本地乘法和加法指令，这些指令可以处理base中的两位数字。因此，如果base是2 ，则需要64位类型以及32位类型。

就这样，你最终的代码看起来像：

/* multiply two n-word numbers, giving a 2n-word result */ 
void multiply(uint32_t *result, uint32_t *a, uint32_t* b, int n) { 
    int i, j; 
    for (i = 0; i < 2*n; i++) 
     result[i] = 0; 
    for (i = 0; i < n; i++) { 
     uint32_t carry = 0; 
     for (j = 0; j < n; j++) { 
      uint64_t product = (uint64_t)a[i] * b[j] + result[i + j] + carry; 
      result[i + j] = product & 0xffffffff; 
      carry = product >> 32; } 
     result[i+n] = carry; } 
} 

基本上你有相同的代码，以铸造，以确保它使用了正确的类型。