長乘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; } 
} 

基本上你有相同的代碼，以鑄造，以確保它使用了正確的類型。