4
\$\begingroup\$

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?

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

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ In your ToString() is it not better to use: string.Concat(array.SkipWhile(x => x == 0)); \$\endgroup\$ – d347hm4n Nov 6 '14 at 10:27
  • \$\begingroup\$ Don't you think you reinvented a lite version of the BigInteger struct? \$\endgroup\$ – Dmitry Nov 6 '14 at 11:06
  • \$\begingroup\$ @Dmitry I have added the reinventing-the-wheel tag to the question. \$\endgroup\$ – Heslacher Nov 6 '14 at 11:17
  • \$\begingroup\$ @d347hm4n Didn't know about that overload of string.Concat. \$\endgroup\$ – Raz Megrelidze Nov 6 '14 at 12:03
2
\$\begingroup\$

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.

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

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ok, you explained what Multiple Precision Arithmetic is and how can you use it. How is that related to the code in the question? \$\endgroup\$ – svick Nov 9 '14 at 12:06
  • \$\begingroup\$ @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. \$\endgroup\$ – ben rudgers Nov 9 '14 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.