Help with adding really huge numbers.

[CodeMonkey2000]

One of the contest question at the UVA site required us to do basic addition to really huge numbers. I decided to make an array of integers to hold each digits, and then make an add function to add two big numbers. I kept getting WA (wrong answer) and I'm pretty sure it has to do with my method of adding. Could some one please look over it?

c++:

std::vector<int> add  (std::vector<int> a, std::vector<int> b) {         //c is the answer         std::vector<int> c;         c.resize( max(a.size() , b.size())+1);                 int carry; //the carry over                 //just to be on the safe side         c[1]=0;         a[0]=0;         b[0]=0;                 int x,y;  //counters         int cur; //current digit of c                 x=a.size()-1;         y=b.size()-1;                 cur=c.size()-1;         carry=0;                 //where the actual addition happens         while (cur>0)         {                 if (x<0)                         x=0;                 if(y<0)                         y=0;                 c[cur]=(a[x]+b[y]+carry)%10;                 carry=(a[x]+b[y])/10;                 cur--;                 x--;                 y--;         }         //corrects the trailing zeros         while (c[1]==0)         {                 for (int m=1;m<c.size(); m++)                         c[m]=c[m+1];                                 c.pop_back();         }         return c; }

[md]

First, why are you setting a[0] and b[0] to 0? That would be changing the numbers you want to add... of course you get the wrong answer! Second, c[1] = 0? shouldn't that be c[0]?

It also seems to me like maybe there is an issue in the way you go through your arrays. I would give you more pointers... but I don't want to ruin it if this is a contest or something.

[zylum]

Your method looks more complicated than necessary.. Try to adjust your input data such that the resulting computations are more elegant. For instance, if both input integer arrays are equal in length where the shorter one has leading zeros to compensate, you can have a simple solutions such as this:

Turing:

var a : array 1 .. 7 of int := init (9, 9, 9, 1, 1, 1, 1) var b : array 1 .. 7 of int := init (0, 0, 1, 1, 1, 1, 1) var c := 0 for decreasing i : upper (a) .. 1     a (i) := a (i) + b (i) + c     c := a (i) div 10     a (i) := a (i) mod 10 end for put c .. for i : 1 .. upper (a)     put a (i) .. end for

To create a new array for the shorter array which contains leading zeros takes no effort and makes the resulting algorithm easier to implement. This contrasts to your solution where you have to set certain elements in the arrays to zero 'just in case' as well as dealing with three indexes. This is just a small tip for contest situations.. Doing a little extra work that doesn't require much thought but makes coding the rest of the solution easier is well worth the extra couple of minutes.. Saves you lots of headaches from unnecessary debugging

[md]

Ack! Turing in the C++ help forums! I think that's a ban worthy offense!

Zylum's approach will work though, even if the arrays are of different sizes. It just requires a bit more effort as you need to keep track of each array's index seperately and once they reach -1 use 0 instead of actually accessing the array.

[zylum]

sorry but I don't have any c++ compilers installed atm and I don't like posting code without testing it first..

[CodeMonkey2000]

Zylum's method is a lot better. What's a safe amount of digits to use? 50? 1000?

[Nick]

I say use a flexible array or vector

[CodeMonkey2000]

Also using your way, wouldn't taking the input backwards be easier to work with?