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?

• raptortech97: I don't know C#, but I think you can replace your two lines of carry logic with carry = total / 10.
• Rezo Megrelidze: @raptortech97 Yeah it works. But i think carry = total > 9 ? 1 : 0; is clearer.
• Dmitry: Why not use the BigInteger struct?

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.

• aydjay: In your ToString() is it not better to use: string.Concat(array.SkipWhile(x => x == 0))
• Dmitry: Don't you think you reinvented a lite version of the BigInteger struct?
• Heslacher: @Dmitry I have added the reinventing-the-wheel tag to the question.
• Rezo Megrelidze: @d347hm4n Didn't know about that overload of string.Concat.

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.

• raptortech97: This might be faster, but it's certainly not cleaner.
• Dmitry: @raptortech97 Maybe you're right, but the OP's question is How can I improve this implementation? Thus a performance is also an option.
• Heslacher: You could reuse the maxLen for creating of the sum array and also for the loop.

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.

• svick: Ok, you explained what Multiple Precision Arithmetic is and how can you use it. How is that related to the code in the question?
• ben rudgers: @svick "Use numeric methods instead of string methods," answers the question "How can I improve this implementation?" for some meanings of 'improve'. It is theoretically possible to get from New York to London in vehicle made of concrete, but it will need to be a boat, not an aeroplane.