Implementation of arbitrary-precision integer addition

Question

Implementation:

string Add(string a,string b)
{
    int maxLen = Math.Max(a.Length,b.Length);
    a = a.PadLeft(maxLen+1,'0');
    b = b.PadLeft(maxLen+1,'0');

    int[] arr1 = a.Select(x => int.Parse(x.ToString())).ToArray();
    int[] arr2 = b.Select(x => int.Parse(x.ToString())).ToArray();
    int[] sum = new int[arr1.Length];

    int carry = 0;
    for(int i = sum.Length-1;i >= 0;i--)
    {
        int total = arr1[i] + arr2[i] + carry;
        sum[i] = total % 10;
        if(total > 9) carry = 1;
        else carry = 0;
    }
    return string.Join("",sum.SkipWhile(x => x == 0));
}

Example:

void Main()
{
    string a = "12121213213213902139210903";
    string b = "1213212222132132113";
    Console.WriteLine(Add(a,b)); // 12121214426426124271343016
}

How can I improve this implementation?

Answer 1

How can I improve this implementation?

You could extract the string parsing to a separate int[] ToIntArray(String) method.
You could add a separate int[] Add(int[],int[]) method.
You could add a separate String ToString(int[]) method.

Right now your method is

1. parsing the String's to int[]
2. adding two int[]
3. composing a string out of the adding

So after extracting the methods your former Add() method would look like

string Add(string a,string b)
{
    int maxLen = Math.Max(a.Length,b.Length);
    a = a.PadLeft(maxLen+1,'0');
    b = b.PadLeft(maxLen+1,'0');

    int[] arr1 = ToIntArray(a);
    int[] arr2 = ToIntArray(b);

    int[] sum = Add(arr1,arr2);

    return ToString(sum);
}  

But wait, we can do much better using more OOP.

Let us introduce a new class IntArray ( which can be private ). In this class we override the ToString() method, add constructors for int[] and string and also add a + operator.

private class IntArray
{

    public int[] array { get; private set; }
    public IntArray(int[] arr)
    {
        array = arr;
    }

    public IntArray(String s)
    {
        array = s.Select(x => int.Parse(x.ToString())).ToArray();
    }

    public static IntArray operator +(IntArray summand1, IntArray summand2)
    {
        int[] sum = new int[summand1.array.Length];
        int carry = 0;

        for (int i = sum.Length - 1; i >= 0; i--)
        {
            int total = summand1.array[i] + summand2.array[i] + carry;
            sum[i] = total % 10;
            if (total > 9) 
            {
                 carry = 1;
            }
            else 
            {
                carry = 0;
            }
        }

        return new IntArray(sum);
    }
    public override string ToString()
    {
        return string.Concat(array.SkipWhile(x => x == 0));
    }

}  

This will simplify your former Add() method to

string Add(string a, string b)
{
    int maxLen = Math.Max(a.Length, b.Length);
    a = a.PadLeft(maxLen + 1, '0');
    b = b.PadLeft(maxLen + 1, '0');

    IntArray arr1 = new IntArray(a);
    IntArray arr2 = new IntArray(b);

    return (arr1 + arr2).ToString();
}

Update: Based on d347hm4n's comment and after checking the reference source, I changed to implementation of ToString() from String.Join() to String.Concat() method.

Answer 2

On my opinion, you don't need to parse a string's elements as int, you could address a particular digit as a char.

private static string Add(string a, string b)
{
    const string ArgumentExceptionString = "Argument is not represents a decimal number";

    int maxLen = Math.Max(a.Length, b.Length) + 1;
    a = a.PadLeft(maxLen, '0');
    b = b.PadLeft(maxLen, '0');

    char[] sum = new char[a.Length];
    int carry = 0;

    // The low loop margin is raised up to 1, because we don't need arithmetics for the 
    // first char, it can be only '0' or '1':
    for (int i = sum.Length - 1; i >= 1; i--)
    {
        int aDigit = a[i] - '0';
        if (aDigit < 0 || aDigit > 9)
            throw new ArgumentException(ArgumentExceptionString, "a");

        int bDigit = b[i] - '0';
        if (bDigit < 0 || bDigit > 9)
            throw new ArgumentException(ArgumentExceptionString, "b");

        int total = aDigit + bDigit + carry;
        sum[i] = (char)('0' + (total % 10));
        carry = total > 9 ? 1 : 0;
    }
    // Process the first char:
    sum[0] = (char)('0' + carry);
    // Return the entire `sum` chars if carry == 0, or return it without the first digit:
    return new String(sum, 1 - carry, maxLen - 1 + carry);
}

This approach should improve a performance.

Answer 3

Prolog

34. The string is a stark data structure and everywhere it is passed there is much duplication of process. It is a perfect vehicle for hiding information. --Alan J. Perlis, Epigrams on Programming

Multiple Precision Arithmetic

Knuth, in The Art of Computer Programming, volume 2: Seminumerical Algorithms; third edition, describes the classic addition algorithm for multiple precision arthmetic [ie. the sort of arithmetic we do every day by hand]:

• Addition of n-place integers giving an n-place answer and a carry.

• n-place integer addition is built from addition of one place integers, giving a one place integer and a carry.

• Defining "n-place integer" as b^n where b "is the radix of ordinary positional notation in which the numbers are expressed".

The key however is:

The most important fact to understand about extended-precision numbers is that they may be regarded as numbers writing in radix w notation, where w is the computer's word size. For example, an integer that fills 10 words on a computer whose word size is w = 10^10 has 100 decimal digits; but we will consider it to be a 10-place number to the base 10^10. This viewpoint is justified for the same reason that we may convert, say, from binary to hexadecimal notation, simply by grouping the bits together. [page 266].

Algorithm A and Program A which follow provide implementation details but in general these may be seen as equivalent to digital circuits for addition.

Resources

1. C# BigInteger Class at Code Project.

2. BigInteger at Codeplex.

3. StackOverflow question 1340397.