a more simple big adder in c#?

Question

Hi,

I just had the task in school to write a big adder. Meaning a method that can put very large numbers together. We had 10 minutes and I did complete it on time. The teacher approved it.

I am not too satisfied with the result though, and I thought I perhaps were taking the wrong approach.

Here is my version:

using System;
using System.Text;

namespace kæmpe_adder
{
    static class Program
    {
        static void Main()
        {
            var x = "1111";
            var y = "111111111";

            Console.WriteLine(BigAdder(x, y));
            Console.ReadLine();
        }
        public static StringBuilder BigAdder(string x, string y)
        {
            var a = new StringBuilder(x);
            var b = new StringBuilder(y);
            return BigAdder(a, b);
        }
        public static StringBuilder BigAdder(StringBuilder x, StringBuilder y)
        {
            int biggest;
            int carry = 0;
            int sum;
            var stringSum = new StringBuilder();

            if (x.Length > y.Length)
            {
                y.FillString(x.Length - y.Length);
                biggest = x.Length;
            }
            else if (y.Length > x.Length)
            {
                x.FillString(y.Length - x.Length);
                biggest = y.Length;
            }
            else
            {
                biggest = y.Length;
            }

            for (int i = biggest - 1; i >= 0; i--)
            {
                sum = Convert.ToInt32(x[i].ToString()) + Convert.ToInt32(y[i].ToString()) + carry;
                carry = sum / 10;
                stringSum.Insert(0, sum % 10);
            }

            if (carry != 0)
            {
                stringSum.Insert(0, carry);
            }

            return stringSum;
        }
        public static void FillString(this StringBuilder str, int max)
        {
            for (int i = 0; i < max; i++)
            {
                str.Insert(0, "0");
            }
        }
    }
}

When I wrote it, I thought of how you do it with binaries.

Is there a shorter and/or perhaps simpler way to do this?

Answer 1

From the algebraic point of view your code looks correct. From the design point of view, you would definitely prefer to encapsulate each of these big numbers in a class, so that you don't have to reference the string/string builders all the time. I am also not a big fan of this FillString approach, it seems more reasonable to add the digits while both numbers have non-zero values, and then just add the carry to the bigger number until you are done.

Not sure what was the question about binaries? The normal length numbers (32bit and 64bit) are added by the CPU as a single operation.

Answer 2

There are a number of open source implementations you could look to for inspiration.

http://www.codeproject.com/KB/cs/biginteger.aspx

http://biginteger.codeplex.com/

In general, I would recommend using an array of byte or long for best performance, but the conversion from a string to the array would be non-trivial.

Store the numbers in reverse order; this makes finding equivalent places trivial.

This makes it easier to add differently sized strings numbers:

int place = 0;
int carry = 0;

while ( place < shorter.Length ) {
    result.Append (AddDigits (longer[place], shorter[place], ref carry));
    ++place;
}

while ( place < longer.Length ) {
    result.Append (AddDigits (longer[place], 0, ref carry));
    ++place;
}

if ( carry != 0 )
    result.Append (carry.ToString ());