小數乘法器中的錯誤

Question

我正在用C++編寫小數乘法器。乘法器通過將兩個整數表示爲數字矢量來實現。每個矢量以相反的順序存儲其數字，以便更容易用十的冪來表示。例如，3497 = 3 * 10^3 + 4 * 10^2 + 9 * 10^1 + 7 * 10^0並存儲在向量中作爲{7,9,4,3}。因此，向量的每個索引表示該數字在該整數中的相應冪數。

但是，我在我的乘法有一些錯誤。 1位數x 1位數和2位數x 1位數乘法運算完美無缺，但卻以2位數x 2位數分解。我相當肯定，修復這個錯誤會修復所有其他錯誤與n位數字x m數字。我的乘法和加法方法的代碼如下。

vector<int> multiply(vector<int> &a, vector<int> &b) { 
    // check for emptiness 
    if(a.size() == 0) 
     return b; 
    else if(b.size() == 0) 
     return a; 

    unsigned int i; // increment counter 

    // compensate for size differences 
    if(a.size() > b.size()) 
     for(i = 0; i < a.size()-b.size(); ++i) 
      b.push_back(0); 
    else 
     for(i = 0; i < b.size()-a.size(); ++i) 
      a.push_back(0); 

    int c = 0; // carry value 
    int temp; // temporary integer 
    vector<int> p; // product vector 
    vector<int> s; // sum vector 
    s.push_back(0); // initialize to 0 

    // multiply each digit of a by an index of b 
    for(i = 0; i < b.size(); ++i) { 
     // skip digits of 0 
     if(b[i] == 0) 
      continue; 

     p.resize(i,0); // resize p and add 0s 

     // multiply b[i] by each digit of a 
     for(unsigned int j = 0; j < a.size(); ++j) { 
      temp = c + b[i] * a[j]; // calculate temporary value 

      // two cases 
      if(temp > 9) { 
       c = temp/10; // new carry 
       p.push_back(temp % 10); 
      } 
      else { 
       c = 0; 
       p.push_back(temp); 
      } 
     } 

     // append carry if relevant 
     if(c != 0) 
      p.push_back(c); 

     // sum p and s 
     s = add(p, s); 
     p.clear(); // empty p 
    } 

    return s; // return summed vector (total product) 
} 

vector<int> add(vector<int> &a, vector<int> &b) { 
    // check for emptiness 
    if(a.size() == 0) 
     return b; 
    else if(b.size() == 0) 
     return a; 

    unsigned int i; // increment counter 

    // compensate size differences 
    if(a.size() > b.size()) 
     for(i = 0; i < a.size()-b.size(); ++i) 
      b.push_back(0); 
    else 
     for(i = 0; i < b.size()-a.size(); ++i) 
      a.push_back(0); 

    int c = 0; // carry value 
    vector<int> s; // sum vector 
    int temp; // temporary value 

    // iterate through decimal vectors 
    for(i = 0; i < a.size(); ++i) { 
     temp = c + a[i] + b[i]; // sum three terms 

     // two cases 
     if(temp > 9) { 
      c = temp/10; // new carry 
      s.push_back(temp % 10); // push back remainder 
     } 
     else { 
      c = 0; 
      s.push_back(temp); 
     } 
    } 

    // append carry if relevant 
    if(c != 0) 
     s.push_back(c); 

    return s; // return sum 
} 

幾個測試用例：

45 * 16點返回740（應該是720） 34 * 18返回542（應該是532） 67 * 29返回2003（應爲1943） 28 * 12返回336（正確）

我能想到的唯一問題就是攜帶方面的問題，但是當我瀏覽代碼時，所有內容似乎都會檢查出來。任何人都可以看到錯誤？或者我完全採取錯誤的方法？

Answer 1

您不清除內部循環之前（或之後）的進位。

// iterate through decimal vectors 
    for(i = 0; i < a.size(); ++i) { 
     ... 
    } 

    // append carry if relevant 
    if(c != 0) { 
     p.push_back(c); 
     // add this line 
     c=0; 
    } 

此外，在add你可能想：

// compensate size differences 
while (a.size() > b.size()) 
    b.push_back(0); 
while (b.size() > a.size()) 
    a.push_back(0); 

原樣，那麼您只需按下一個號碼零等於（我相信）陣列之間的初始差值的一半。嘗試使用交互式調試器（正如James所建議的那樣），並且您可能會發現其他的錯誤（儘管也可以說這些代碼的運行時間與手動執行代碼一樣短）。

Answer 2

一些其他風格的註釋：

1. 不要測試空載體，然後回到你回來的東西，因爲空載體的存在表明一個編程錯誤在其他地方 - 無論是拋出一個異常，或者（可能更好）使用一個斷言。當然，除非你用空向量表示0--在這種情況下，邏輯仍然是錯誤的; 0 *東西= 0，而不是東西。

2. 當你測試一個向量爲空時，使用.empty()。

3. 應該沒有必要用零填充矢量到相同的長度。你沒有考慮元素的配對。你把每個乘以一個。你有沒有注意到目前你可能會用零填充b，但是你有邏輯在循環內完全跳過那些零？

4. 但填充可以更加整齊反正做：

   size_t len = std::max(a.size(), b.size()); 
   a.resize(len); b.resize(len); // Note that 0 is the default "fill" 
   

5. 特殊情況不是夠特別。你的邏輯處理temp > 9將工作得很好的情況下，當temp <= 9也。不要過早地優化。保持代碼簡單。（通過在現代處理器上添加分支，可以很容易地通過避免div/mod工作獲得的性能。）

6. 不要通過反覆清除和調整大小重新使用矢量。相反，在該範圍內構建它（再次，不要過早地優化）。一般來說，儘可能限制變量作用域。類似的評論適用於其他變量。尤其適用於循環計數器（ugh）。緩存像迭代的矢量大小（當大小不變時）。編譯器難以優化。

7. 更好的是，當不需要索引時，使用迭代器遍歷向量。

8. 輸入向量不會改變，所以做廣告。

9. 在有合理全長名稱的地方使用全名。

10. 你真的不需要評論那麼多。這很清楚發生了什麼事情。

11. 你正在做的運行總數（'累計'）是一個很好的候選人（少數幾個很好的理由之一），可以使用非const引用。

我會寫（不考慮顯著更改算法）（警告，沒有測試！）：

// I give the function a noun-type name because it returns a value. Just a convention. 
vector<int> product(const vector<int> &a, const vector<int> &b) { 
    assert !a.empty(); 
    assert !b.empty(); 

    vector<int> result(1); // initialized to hold 1 digit with value 0. 

    vector<int>::const_iterator a_begin = b.begin(), a_end = b.end(); 
    size_t b_len = b.size(); 

    for (unsigned int i = 0; i < b_len; ++i) { 
     vector<int> row(i); 
     int carry = 0; // notice that proper scoping auto-fixes the bug. 

     for (vector<int>::const_iterator it = a_begin; it != a_end; ++it) { 
      int value = carry + b[i] * *it; 
      carry = value/10; 
      row.push_back(value % 10); 
     } 
     if (carry != 0) value.push_back(carry); 
     add(result, row); 
    } 
    return result; 
} 

// Similarly, if I were to return the sum, I would call this 'sum'. 
void add(vector<int> &target, const vector<int> &to_add) { 
    assert !target.empty(); 
    assert !to_add.empty(); 

    int count = to_add.size(); 

    // Make sure 'target' is long enough 
    target.resize(std::max(target.size(), count)); 
    int size = target.size(); // after resizing. 

    int carry = 0; 

    // iterate through decimal vectors 
    for (int i = 0; i < size; ++i) { 
     int value = carry + target[i]; 
     if (i < count) { value += to_add[i]; } 
     carry = value/10; 
     target[i] = value % 10; 
    } 

    if (carry != 0) { target.push_back(carry); } 
}