Ошибки в десятичном множителе

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

Как есть, вы будете выдвигать только нули, равные (я полагаю) половине первоначальной разницы между массивами. Попробуйте интерактивный отладчик (как предлагает Джеймс), и вы можете обнаружить другие ошибки (хотя есть и кое-что, что можно сказать о выполнении кода, такого короткого, как это вручную).

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. Не используйте повторно вектор, повторно очищая и изменяя его размер. Вместо этого создайте его внутри этой области (опять же, не оптимизируйте преждевременно). В общем, ограничивайте области видимости переменных настолько, насколько это возможно. Подобные комментарии применимы к другим переменным. Специально для счетчиков петель ( тьфу ).

7. Но делать кэшировать такие вещи, как размер вектора, который повторяется (когда этот размер постоянен). Компилятору труднее оптимизировать.

8. Еще лучше: использовать итераторы для итерации по вектору, когда индексы не нужны.

9. Входные векторы не изменятся, поэтому сообщите об этом.

10. Используйте полные имена, если есть разумное полное имя.

11. Вам действительно не нужно так много комментировать. Совершенно ясно, что происходит.

12. Тип промежуточного итога («накопление»), который вы выполняете (хороший накопитель), является хорошим кандидатом (одна из нескольких веских причин) для использования неконстантной ссылки.

Я бы написал (не считая существенных изменений в алгоритме) (предупреждение, не проверено!):

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