0

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.

João Pires
  • 927
  • 1
  • 5
  • 16
  • Curious, why using "int unsigned greater" while vec1 and vec2 are "long long unsigned"? – Dan Armstrong Dec 12 '16 at 21:44
  • This is not an [MCVE](https://stackoverflow.com/help/MCVE), since it's unclear how you're calling this code or displaying the results. Please provide enough code to reproduce your correct and incorrect results. It's not completely useless, but I thought I'd mention this while I look at what you've got, in case the problem isn't there. – ShadowRanger Dec 12 '16 at 21:45
  • I didn't even thought about that xD that was just a prototype I did to see how stuff works, it's normal if it ended up rushed – João Pires Dec 12 '16 at 21:46
  • @ShadowRanger, I added up some more stuff ;) – João Pires Dec 12 '16 at 21:51
  • @DagobertoPires Are you using the debugger to debug your code? If you did, all you have to do is see where your code diverges from the plan you had (preferably written out already). – PaulMcKenzie Dec 12 '16 at 22:00
  • Just an FYI, your attempt to handle a shorter `vec2` is not going to work because your code is big endian on words. If `vec2` is shorter, you're omitting it in the calculation for the low magnitude words, not the high, so it behaves as if `vec2` was padded to the same length as `vec1` with additional zeroes; if it were little endian, that would be fine, but for big-endian, that means you're interpreting all the values as if they've been multiplied by `2 ** (32 * (vec1.size() - vec2.size()))`. – ShadowRanger Dec 12 '16 at 22:36

2 Answers2

1

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

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • 1
    I prefer to arrange the vector little endian, so that adding a new highest digit is a `push_back` instead of `insert`. See http://stackoverflow.com/a/22004815/5987 – Mark Ransom Dec 12 '16 at 22:12
  • @MarkRansom: Agreed, all the multiprecision integer libraries I know of off-hand store the magnitude with the "words" in little endian order because it's much easier when you need to expand due to carry. It also means you're reading/writing memory in sequential order, which might be helpful on some architectures, and even if it isn't, is usually easier to code. – ShadowRanger Dec 12 '16 at 22:22
  • If you notice, the front is well formed, the problem arrises in the back of the vector: I edited to result to clearly show where the discrepancy happens. Also, notice that my for loop is in reverse. – João Pires Dec 12 '16 at 22:43
  • @DagobertoPires: And? The problem is in the back, because the carry from the front ended up being added to the back. When computing the value for `vec1[0]`, you computed `4294967295 + 4294967295 + 1`, determined there was carry, then applied the carry from that calculation to `vec1.back()`, aka `vec1[2]` in this case. The problem arises at the end of the vector because you essentially implemented a circular carry; it runs off the front and you put it on the back. If you want to check, just try deleting that `if (carry) {}` block outside the loop; you'll get the answer you expected. – ShadowRanger Dec 12 '16 at 23:07
  • @ShadowRanger The problem is, that in some cases, the result would still be wrong even without the carry at the end! Try this: try executing my code with the outside if deleted and try the following number: `429496729522949672953294967295`. My prototype will gave me `858993459025899345905589934589`, the real result is `858993459045899345906589934590`, the 10th and last digit are wrong. – João Pires Dec 13 '16 at 00:31
  • @DagobertoPires: Yes, you have many things wrong with your code. The carry issue is what causes the problem in this case, but using `+=` instead of `=` for your `if (result <= greater) {` case is highly suspicious, and you've got tons of issues involving mismatched `vector` sizes, etc. Your question only asked about the specific flaw with carry overflow though. – ShadowRanger Dec 13 '16 at 00:43
  • Tomorrow, I'll get it right, at least I got something slightly working, it's better than nothing. 3 days ago I didn't knew nothing about it. :) I'll be able to get it right in the end. – João Pires Dec 13 '16 at 01:08
  • @ShadowRanger: Not all. Java's BigInteger uses a big-endian arrangement, but with some empty room "ahead" so expansion isn't too costly. – Rudy Velthuis Dec 13 '16 at 07:25
  • This was answered a few days ago: http://stackoverflow.com/a/41078120/95954. The trick is to use two carries. It is what I do in my BigInteger library too (the non-assembler version). And my results are correct. – Rudy Velthuis Dec 13 '16 at 07:27
0

This 

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

adds one to the last bin.

Perhaps you want to insert one to the front?

BeniBela
  • 16,412
  • 4
  • 45
  • 52