# Implementation of arbitrary-precision integer addition

Implementation:

string Add(string a,string b)
{
int maxLen = Math.Max(a.Length,b.Length);

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";
}


How can I improve this implementation?

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

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.

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);

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

}


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.

• In your ToString() is it not better to use: string.Concat(array.SkipWhile(x => x == 0)); Nov 6, 2014 at 10:27
• Don't you think you reinvented a lite version of the BigInteger struct? Nov 6, 2014 at 11:06
• @Dmitry I have added the reinventing-the-wheel tag to the question. Nov 6, 2014 at 11:17
• @d347hm4n Didn't know about that overload of string.Concat. Nov 6, 2014 at 12:03

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;

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';
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 = (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.

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

# 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.

• Ok, you explained what Multiple Precision Arithmetic is and how can you use it. How is that related to the code in the question? Nov 9, 2014 at 12:06
• @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. Nov 9, 2014 at 14:46