Adding two strings arithmetically

Question

I'm trying to implement a function to add two overly large (let's say 1000 digit long) numbers stored in strings. I'm having problems with correct conversions so I can add numbers correctly.

So far, this is what I've done:

string addBegin (string low, string high, int diff)
{
    for (int i = 0; i <= diff; i++)
        low = "0" + low;
    high = "0" + high;

    cout << "low: " << low << "\nhigh: " << high << endl;

    string result;
    int sum, carry = 0;

    for (int i = low.length()-1; i >= 0; i--)
    {
        sum = (int)low[i] + (int)high[i] + carry;
        carry = 0;
        if (sum > 9)
        {
            sum -= 10;
            carry = 1;
        }
        result = to_string(sum) + result;
    }

    return result;
}

string add (string a, string b)
{
    int diff = a.length() - b.length();

    if (diff <= 0) return addBegin(a, b, abs(diff));
    else return addBegin(b, a, diff);
}

int main (void)
{
    string x = add("52","205");
    cout << "result: " << x << endl;

    return 0;
}

Output:

low: 0052
high: 0205 //the first zero is for potential carry
result: 87899293 //wrong, should be 0257

The result here is made of 4 numbers: 87, 89, 92 and 93. That is obviously wrong, I did some unwanted additions with ASCII values. Any ideas how to make this work? Or is there, by any chance, some ridiculously simple way to add two veeeeery long numbers?

pls help me understand, is `result = low + high`, if they are integers, not strings? and is the only caveat is the numbers are `"veeeeery long"`? — Bill, May 25 '13 at 02:02
When approaching such problems, try to think in small numbers. For example, what should the algorithm do in order to add 5+4? and then, 75+46? — Ilya Kogan, May 25 '13 at 02:05
i am unable to understand, so just asking -- if all you want to do is add two large numbers, why cann't you use them as big integers (http://stackoverflow.com/questions/117429/inputting-large-numbers-in-c#117472) instead of string, and do addition? — Bill, May 25 '13 at 02:07
@Bill A bigint is just a string in another numeric base :) This is a common exercise. — Potatoswatter, May 25 '13 at 02:08
@IlyaKogan Sure, but I don't think that's the main issue here. If I were to add up 75+46, I'd like to get sum of 5+6 and not the sum of their ASCII values. — Saraph, May 25 '13 at 02:09
Yes, but does your program work with 5+6? You're testing it with 52+205 before trying small numbers, but small numbers will be easier to debug. — Ilya Kogan, May 25 '13 at 02:30

score 5 · Accepted Answer · answered May 25 '13 at 02:05

5

    sum = (int)low[i] + (int)high[i] + carry;

This adds the values of the character encodings in e.g. ASCII. You want to subtract '0' from the encoding to get the numeric value.

    sum = low[i] - '0' + high[i] - '0' + carry;

answered May 25 '13 at 02:05

Potatoswatter

134,909
25
265
421

Aaaaand. Working solution is born. I remember doing something similar, but not entirely correct it seems. Thanks. – Saraph May 25 '13 at 02:13
I suspect an extra leading '0' is in the result, you may need to conditionally remove it. – chux - Reinstate Monica May 25 '13 at 02:16
@chux Yes, I'm well aware of that. Thanks. ;) – Saraph May 25 '13 at 02:19

score 4 · Answer 2 · edited May 25 '13 at 02:09

4

Do not forget subtracting '0' from low[i] and high[i] when doing the math.

(int)low[i] is 0x30..0x39 for chars '0'..'9'.

edited May 25 '13 at 02:09

Ken White

123,280
14
225
444

answered May 25 '13 at 02:03

jmihalicza

2,083
12
20

score 1 · Answer 3 · answered May 25 '13 at 02:09

1

A problem is that you use

sum = (int)low[i] + (int)high[i] + carry;

which should be

sum = low[i] - '0' + high[i] - '0' + carry;

answered May 25 '13 at 02:09

kaitian521

548
2
10
25

Adding two strings arithmetically

3 Answers3