BigInteger implementation, carry discrepancy

Question

lately, I've been trying to make my on Big Integer class. Right now, I've been doing some prototypes, they almost work. This prototype is not a function, nor a class, just a quick stuff I did to see if it worked.

This is my prototype so far: (it looks a bit ugly with all the casts just to please the compiler)

    std::vector<long long unsigned> vec1 {4294967295, 2294967295, 1294967295};
    std::vector<long long unsigned> vec2 {4294967295, 2294967295, 1294967295};

    int carry {};
    for (int i {static_cast<int>(vec1.size()) - 1}; i != -1; --i) {
        int unsigned greater = static_cast<unsigned int>(std::max(vec1[i], vec2[i]));
        int unsigned result {};

        if (i < static_cast<int>(vec2.size())) {
            result = static_cast<int unsigned>(vec2[i] + vec1[i] + carry);
        } else if (carry) {
            result = static_cast<int unsigned>(vec1[i] + carry);
        } else {
            break;
        }

        if (result <= greater) {
            vec1[i] += result;
            carry = 1;
        } else {
            vec1[i] = result;
            carry = 0;
        }
    }

    if (carry) {
        vec1.back() += 1;
    }

    for (auto const n : vec1) {
        cout << n;
    }

And these is the result:

858993459025899345892589934591
                  ^          ^
858993459045899345902589934590 -> the correct one!

So, what I'm doing wrong?

It does give the same result in gcc and visual studio.

Answer 1

This

if (carry) {
    vec1.back() += 1;
}

adds one to the last bin.

Perhaps you want to insert one to the front?

Answer 2

As written, if the highest magnitude addition carries, you end up incrementing the lowest magnitude value:

if (carry) {
    vec1.back() += 1;
}

Presumably, the correct behavior would be to expand the vector and allow the carry to occupy the new highest value, e.g.:

if (carry) {
    vec1.insert(vec1.begin(), 1);
}

This does mean you end up expanding vec1 (and copying all the existing values, because insertion at the beginning of a vector isn't cheap), which might or might not be correct given the design of your class (your addition operation looks unsafe if vec1 and vec2 don't have matching size, so it's unclear whether vec1 is allowed to expand).