c++ - 10 進乗数のバグ

Question

C++ で 10 進乗数を作成しています。乗数は、数字のベクトルとして表される 2 つの整数を取得することによって実装されます。各ベクトルは、10 の累乗で簡単に表現できるように、その桁を逆順に格納します。たとえば、3497 = 3 * 10^3 + 4 * 10^2 + 9 * 10^1 + 7 *10^0 であり、{7, 9, 4, 3} としてベクトルに格納されます。したがって、ベクトルの各インデックスは、その桁のそれぞれの整数の 10 乗を表します。

ただし、乗算にはいくつかのバグがあります。1桁×1桁、2桁×1桁の掛け算は問題なく動くのですが、2桁×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. あなたは本当にそれほどコメントする必要はありません。何が起こっているのかは非常に明確です。

12. あなたが行っているランニングトータルの種類（「累積」）は、非定数参照を利用するための良い候補です（いくつかの正当な理由の1つ）。

私は次のように書きます（アルゴリズムへの重要な変更を考慮していません）（警告、テストされていません！）：

// 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); }
}