How to add or subtract very large numbers without bigint in C#?

Question

So let me start by saying that I'm a newbie with little to moderate knowledge about C#.

Coming to the topic: I need to make a program that is able to add/subtract very large integers. Initially, used BigInt only to find out it's not allowed. There should be a logical workaround for this? I have an idea which is using "elementary school method" where you add each digit starting from right to left.

I made a string which I split into char array and added each digit from right to left(GetUpperBound-i). But it doesn't seem to work.

My Code:

string s, s2;
char[] c_arr, c_arr2;
int i, erg;

s = "1234";
s2 = "5678";
c_arr = s.ToCharArray();
c_arr2 = s2.ToCharArray();
for (i = 0; i <= c_arr.GetUpperBound(0); i++)
{
    erg = c_arr[c_arr.GetUpperBound(0)-i]+c_arr2[c_arr2.GetUpperBound(0)-i];
    Console.Write(erg);
}

Console.ReadKey();

Answer 1

There are a few things wrong with your code for the 'elementary school method'. You don't account for carry, you're adding up ascii values rather than actual values between 0-9, and you're outputting the results in the wrong order.

The code below, whilst not very elegant, does produce the correct results:

var s1 = "12345";
var s2 = "5678";
var carry = false;
var result = String.Empty;

if(s1.Length != s2.Length)
{
    var diff = Math.Abs(s1.Length - s2.Length);

    if(s1.Length < s2.Length)
    {
        s1 = String.Join("", Enumerable.Repeat("0", diff)) + s1;
    }
    else
    {
        s2 = String.Join("", Enumerable.Repeat("0", diff)) + s2;
    }
}


for(int i = s1.Length-1;i >= 0; i--)
{
    var augend = Convert.ToInt32(s1.Substring(i,1));
    var addend = Convert.ToInt32(s2.Substring(i,1));
    var sum = augend + addend;
    sum += (carry ? 1 : 0);
    carry = false;
    if(sum > 9)
    {
        carry = true;
        sum -= 10;
    }

    result = sum.ToString() + result;
}

if(carry)
{
    result = "1" + result;
}

Console.WriteLine(result);

Answer 2

The following program can be used to add two large numbers, I have used string builder to store the result. You can add numbers containing digits upto '2,147,483,647'.

Using System;

using System.Text;

using System.Linq;

public class Test

{

public static void Main()

{

    string term1="15245142151235123512352362362352351236";

    string term2="1522135123612646436143613461344";

    StringBuilder sum=new StringBuilder();

    int n1=term1.Length;

    int n2=term2.Length;

    int carry=0;

    int n=(n1>n2)?n1:n2;

    if(n1>n2)

    term2=term2.PadLeft(n1,'0');

    else

    term1=term1.PadLeft(n2,'0');

    for(int i=n-1;i>=0;i--)

    {

        int value=(carry+term1[i]-48+term2[i]-48)%10;

        sum.Append(value);

        carry=(carry+term1[i]-48+term2[i]-48)/10;

    }

    char[] c=sum.ToString().ToCharArray();

    Array.Reverse(c);

    Console.WriteLine(c);

}

}

Answer 3

string Add(string s1, string s2)
{
    bool carry = false;
    string result = string.Empty;
    if(s1[0] != '-' && s2[0] != '-')
    {
        if (s1.Length < s2.Length)
            s1 = s1.PadLeft(s2.Length, '0');
        if(s2.Length < s1.Length)
            s2 = s2.PadLeft(s1.Length, '0');

        for(int i = s1.Length-1; i >= 0; i--)
        {
            var augend = Convert.ToInt64(s1.Substring(i,1));
            var addend = Convert.ToInt64(s2.Substring(i,1));
            var sum = augend + addend;
            sum += (carry ? 1 : 0);
            carry = false;
            if(sum > 9)
            {
                carry = true;
                sum -= 10;
            }
            result = sum.ToString() + result;
        }
        if(carry)
        {
            result = "1" + result;
        }
    }

    else if(s1[0] == '-' || s2[0] == '-')
    {
        long sum = 0;
        if(s2[0] == '-')
        {
            //Removing negative sign
            char[] MyChar = {'-'};
            string NewString = s2.TrimStart(MyChar);
            s2 = NewString;

            if(s2.Length < s1.Length)
                s2 = s2.PadLeft(s1.Length, '0');

            for (int i = s1.Length - 1; i >= 0; i--)
            {
                var augend = Convert.ToInt64(s1.Substring(i,1));
                var addend = Convert.ToInt64(s2.Substring(i,1));
                if(augend >= addend)
                {
                    sum = augend - addend;
                }
                else 
                {
                    int temp = i - 1;
                    long numberNext = Convert.ToInt64(s1.Substring(temp,1));
                    //if number before is 0
                    while(numberNext == 0)
                    {
                        temp--;
                        numberNext = Convert.ToInt64(s1.Substring(temp,1));
                    }
                    //taking one from the neighbor number
                    int a = int.Parse(s1[temp].ToString());
                    a--;
                    StringBuilder tempString = new StringBuilder(s1);
                    string aString = a.ToString();
                    tempString[temp] = Convert.ToChar(aString);
                    s1 = tempString.ToString(); 
                    while(temp < i)
                    {
                        temp++;
                        StringBuilder copyS1 = new StringBuilder(s1);
                        string nine = "9"; 
                        tempString[temp] = Convert.ToChar(nine);
                        s1 = tempString.ToString();
                    }
                    augend += 10;
                    sum = augend - addend;
                }
                result = sum.ToString() + result;
            }
            //Removing the zero infront of the answer
            char[] zeroChar = {'0'};
            string tempResult = result.TrimStart(zeroChar);
            result = tempResult;
        }
    }

    return result;
}
string Multiply(string s1, string s2)
{
    string result = string.Empty;
    //For multipication
    bool Negative = false;
    if(s1[0] == '-' && s2[0] == '-')
        Negative = false;
    else if(s1[0] == '-' || s2[0] == '-')
        Negative = true;

    char[] minusChar = {'-'};
    string NewString;
    NewString = s2.TrimStart(minusChar);
    s2 = NewString;
    NewString = s1.TrimStart(minusChar);
    s1 = NewString;

    List<string> resultList = new List<string>();
    for(int i = s2.Length - 1; i >= 0; i--)
    {
        string multiplycation = string.Empty;
        for (int j = s1.Length - 1; j >= 0; j--)
        {
            var augend = Convert.ToInt64(s1.Substring(j,1));
            var addend = Convert.ToInt64(s2.Substring(i,1));
            long multiply = augend * addend;
            // print(multiply); 
            multiplycation = multiply.ToString() + multiplycation;
        }
        //Adding zero at the end of the multiplication
        for (int k =  s2.Length - 1 - i; k > 0; k--)
        {
            multiplycation += "0";
        }
        resultList.Add(multiplycation);
    }

    for (int i = 1; i < resultList.Count; i++)
    {
        resultList[0] = Add(resultList[0],resultList[i]);
    }

    //Finally assigning if negative negative sign in front of the number
    if(Negative)
        result = resultList[0].Insert(0,"-");
    else
        result = resultList[0];

    return result;
}
string Divide(string dividend, string divisor)
{
    string result = string.Empty;

    int remainder = 0;
    int intNumberstoGet = divisor.Length;
    int currentInt = 0;
    int dividing = int.Parse(dividend.Substring(currentInt,intNumberstoGet));

    int intDivisor = int.Parse(divisor);

    while(currentInt < dividend.Length)
    {
        if(dividing == 0)
        {
            currentInt++;
            result += "0";
        }
        else
        {
            while(dividing < intDivisor)
            {
                intNumberstoGet++;
                dividing = int.Parse(dividend.Substring(currentInt,intNumberstoGet));
            }

            if (dividing > 0)
            {   
                remainder = dividing % intDivisor;
                result += ((dividing - remainder) / intDivisor).ToString();
                intNumberstoGet = 1;

                if(currentInt < dividend.Length - 2)
                    currentInt += 2;
                else
                    currentInt++;

                if(currentInt != dividend.Length)
                {
                    dividing = int.Parse(dividend.Substring(currentInt,intNumberstoGet));
                    remainder *= 10;
                    dividing += remainder;
                }
            }
        }
    }
    return result;
}

Answer 4

Here you go. Another example. It's 10 to 30 times faster than the accepted answer.

    static string AddNumStr(string v1, string v2)
    {
        var v1Len = v1.Length;
        var v2Len = v2.Length;
        var count = Math.Max(v1Len, v2Len);
        var answ = new char[count + 1];
        while (count >= 0) answ[count--] = (char)((v1Len > 0 ? v1[--v1Len] & 0xF:0) + (v2Len>0 ? v2[--v2Len]&0xF : 0));
        for (var i = answ.Length - 1; i >= 0; i--)
        {
            if (answ[i] > 9)
            {
                answ[i - 1]++;
                answ[i] -= (char)10;
            }
            answ[i] = (char)(answ[i] | 48);
        }
        return new string(answ).TrimStart('0');
    }

Answer 5

Below SO question has some interesting approaches. Though the answer is in Java, but you will surely get to know what needs to be done.

How to handle very large numbers in Java without using java.math.BigInteger

Answer 6

    public static int[] addTwoNumbers(string s1, string s2)
    {

        char[] num1 = s1.ToCharArray();
        char[] num2 = s2.ToCharArray();
        int sum = 0;
        int carry = 0;
        int size = (s1.Length > s2.Length) ? s1.Length + 1 : s2.Length + 1;
        int[] result = new int[size];
        int index = size - 1;
        int num1index = num1.Length - 1;
        int num2index = num2.Length - 1;


        while (true)
        {
            if (num1index >= 0 && num2index >= 0)
            {
                sum = (num1[num1index]-'0') + (num2[num2index]-'0') + carry;
            }
            else if(num1index< 0 && num2index >= 0)
            {
                sum = (num2[num2index]-'0') + carry;
            }
            else if (num1index >= 0 && num2index < 0)
            {
                sum = (num1[num1index]-'0') + carry;
            }
            else { break; }


            carry = sum /10;
            result[index] = sum % 10;
            index--;
            num1index--;
            num2index--;
        } 

            if(carry>0)
            {
                result[index] = carry;
            }


        return result;
    }