Add Two Large Numbers Using Strings - Without Use of BigInt

Question

_{Saturday, July 5, 2014 8:17 PM}

I'm attempting to create a function to add two infinitely large numbers using strings and an elementary style arithmetic of working out the sum two numbers in the format of strings. The problem that I'm facing is that I can't figure out what to do when it comes to corner cases like 99 + 1 and situations where a new character in the string must be created. Note, I'm performing the addition in reverse so the numbers in the string are always in reverse and any answer outputted will also be in revers (makes it a lot easier when using the for-loop).

Code:

    string firstNumber = "99"; // note: in reverse
            string secondNumber = "1";
            bool carry = false;
            string result = firstNumber; // large one

            for (int position = 0; position < secondNumber.Length; position++) // start with smallest
            {
                int firstNumberDigit = int.Parse(result[position].ToString());
                int secondNumberDigit = int.Parse(secondNumber[position].ToString());
                int sumOfDigits = firstNumberDigit + secondNumberDigit;

                int lastNum = sumOfDigits % 10;
                result = result.Remove(position, 1);
                result = result.Insert(position, lastNum.ToString());

                carry = false;

                if (sumOfDigits > 9)
                {
                    carry = true;

                    int currentCarry = sumOfDigits / 10;

                    int carryResult = int.Parse(result[position + 1].ToString()) + currentCarry;

                    if (carryResult > 9)
                    {
                        result = result.Replace(result[position + 1], Convert.ToChar(0));
                    }
                    else
                    {
                        result = result.Replace(result[position + 1], Convert.ToChar(carryResult.ToString())); 
                    }
                    
                }

            }

All replies (6)

_{Saturday, July 5, 2014 9:22 PM ✅Answered}

The way you're trying to handle carry is too complicated, instead of actually "carrying" the value you're trying to propagate it before the next result digit is computed. The simplest way to do this is to make carry an integer variable and add it to sumOfDigits.

The fact that you're sort of trying to modify one of the input strings doesn't make things easier. The result should be built into a char[], it's simpler and more efficient than inserting/replacing characters in the original input string. Here it helps noting that the maximum number of digits of the result is Max(firstNumber.Length, secondNumber.Length) + 1.

Here's an example:

static string Add(string a, string b) {
    char[] result = new char[Math.Max(a.Length, b.Length) + 1];
    int resultLength = 0;
    int carry = 0;

    // treat the two numbers as having the same length
    // by 'virtually' padding the shorter number with zeroes
    // this isn't the most efficient way of doing things but it's simpler
    for (int i = 0; i < Math.Max(a.Length, b.Length); i++) {
        int an = (i < a.Length) ? int.Parse(a[i].ToString()) : 0;
        int bn = (i < b.Length) ? int.Parse(b[i].ToString()) : 0;
        // add the two digits and the carry
        int rn = an + bn + carry;

        if (rn > 9) {
            carry = 1;
            // note that the maximum sum is 9+9+1=19
            // using % 10 isn't necessary, we can simply subtract 10
            rn -= 10;
        }
        else {
            carry = 0;
        }

        result[resultLength++] = (char)(rn + '0');
    }

    // if carry isn't 0 then we have to store it in the result
    // this is exactly the 99+1 "corner case" 
    if (carry != 0)
        result[resultLength++] = '1';

    // create the result string from the char array
    return new string(result, 0, resultLength);
}

Note that I used (char)('0' + rn) instead of something like Convert.ToChar(rn.ToString()), it's more efficient. If you know that the strings contain only digits then you can also replace int.Parse(a[i].ToString()) with a[i] - '0'. The character codes are such that adding/subtracting the code of character '0' gives you the digit character/digit value.

_{Sunday, July 6, 2014 7:37 AM | 1 vote}

I'm attempting to create a function to add two infinitely large numbers using strings and an elementary style arithmetic of working out the sum two numbers in the format of strings. The problem that I'm facing is that I can't figure out what to do when it comes to corner cases like 99 + 1 and situations where a new character in the string must be created. Note, I'm performing the addition in reverse so the numbers in the string are always in reverse and any answer outputted will also be in revers (makes it a lot easier when using the for-loop).

Code:

    string firstNumber = "99"; // note: in reverse
            string secondNumber = "1";
            bool carry = false;
            string result = firstNumber; // large one

            for (int position = 0; position < secondNumber.Length; position++) // start with smallest
            {
                int firstNumberDigit = int.Parse(result[position].ToString());
                int secondNumberDigit = int.Parse(secondNumber[position].ToString());
                int sumOfDigits = firstNumberDigit + secondNumberDigit;

                int lastNum = sumOfDigits % 10;
                result = result.Remove(position, 1);
                result = result.Insert(position, lastNum.ToString());

                carry = false;

                if (sumOfDigits > 9)
                {
                    carry = true;

                    int currentCarry = sumOfDigits / 10;

                    int carryResult = int.Parse(result[position + 1].ToString()) + currentCarry;

                    if (carryResult > 9)
                    {
                        result = result.Replace(result[position + 1], Convert.ToChar(0));
                    }
                    else
                    {
                        result = result.Replace(result[position + 1], Convert.ToChar(carryResult.ToString())); 
                    }
                    
                }

            }

I suggest a very simple method like this one (static method, or instance):

static string SumOf2Strings(string s1, string s2)
{
    string n1 = s1.Length >= s2.Length ? s1 : s2;
    string n2 = s1.Length >= s2.Length ? s2 : s1;

    int l1 = n1.Length - 1;
    int l2 = n2.Length - 1;
    int x2 = l1 - l2;
    int carry = 0;

    string reference = "01234567890123456789";
    string result = "";
    
    for (int i = l1; i >= 0; i--)
    {
        int ix = reference.IndexOf(n1[i]);
        if (i <= l2 + x2 && l1 - i <= l2)
            ix += reference.IndexOf(n2[i - x2]);
        ix += carry;
        carry = ix > 9 ? 1 : 0;

        result = reference[ix] + result;
    }
    return carry > 0 ? result = '1' + result : result;
}

An example using the code above is:

static void Main(string[] args)
{
    string s1 = "991";
    string s2 = "9";

    // or
    // string s1 = "9";
    // string s2 = "991";

    Console.WriteLine(
        SumOf2Strings(s1, s2)
    );
}

Notice that I'm not checking if the strings are valids, but you should do it.

It's very simple, ain't it?

•

_{Sunday, July 6, 2014 10:20 AM}

@_far_sunrise_ Your method works really well but could you explain to me how your method works, like why do you have a reference string with the all the numbers from 0-9 and what is the 'ix' variable doing?

_{Sunday, July 6, 2014 12:20 PM}

"like why do you have a reference string with the all the numbers from 0-9"

That's just a convoluted and inefficient way to get the numeric value of a char digit and vice versa.

The textbook way to obtain the numeric value of a digit is to subtract the code of character '0' from the code of the digit character. That is

int value = ch - '0';

That's because the codes of the Latin digit characters are consecutive - '0' has code 48, '1' has code 49 and so on.

This also allows you to easily check if a character is a digit:

if (ch < '0' || '9' < ch) throw new FormatException();

To obtain a digit character from an integer number between 0 and 9 you just add '0' and cast to char:

char ch = (char)(value + '0');

_{Sunday, July 6, 2014 3:41 PM}

"like why do you have a reference string with the all the numbers from 0-9"

That's just a convoluted and inefficient way to get the numeric value of a char digit and vice versa.

The textbook way to obtain the numeric value of a digit is to subtract the code of character '0' from the code of the digit character. That is

int value = ch - '0';

That's because the codes of the Latin digit characters are consecutive - '0' has code 48, '1' has code 49 and so on.

This also allows you to easily check if a character is a digit:

if (ch < '0' || '9' < ch) throw new FormatException();

To obtain a digit character from an integer number between 0 and 9 you just add '0' and cast to char:

char ch = (char)(value + '0');

Oh, I see now, so we're basically converting the ascii values into their corresponding numbers! Thanks Mike for all the help, I now see how much more efficient your method is.

_{Sunday, July 6, 2014 7:36 PM}

Note that my sample is still adding in reverse like you did. I don't know what you need this code for but if you want to add "normal" numbers then you can change the string/array indices like this:

• a[i] becomes a[a.Length - 1 - i]
• b[i] becomes b[b.Length - 1 - i]
• r[resultLength++] becomes r[r.Length - 1 - resultLength++]
• new string(result, 0, resultLength) becomes new string(result, result.Length - resultLength, resultLength)