5
\$\begingroup\$

I wrote this method that adds two integers in the form of strings together. This way I can add large integers without overflowing.

How efficient is the code that I wrote? I am by no means a great coder, but I would consider myself somewhat decent. Is there anyway that would make it better?

I am a self taught coder and have only been doing it for about a year, so please be easy on me.


static string addString(string num1, string num2) {
        string retVal = null, cNum1 = null, cNum2 = null;
        int bf1 = 0, bf2 = 0;
        if (num1.Length > num2.Length) {
            for (int i = 0; i < (num1.Length - num2.Length); i++) {
                cNum2 += "0";
            }
        } else if (num1.Length < num2.Length) {
            for (int i = 0; i < (num2.Length - num1.Length); i++) {
                cNum1 += "0";
            }
        }
        cNum1 += num1; 
        cNum2 += num2;
        char[] cAN1 = cNum1.ToCharArray(); 
        Array.Reverse(cAN1); 
        cNum1 = new string(cAN1);
        char[] cAN2 = cNum2.ToCharArray(); 
        Array.Reverse(cAN2); 
        cNum2 = new string(cAN2);
        for (int i = 0; i < cNum1.Length; i++) {
            bf2 = bf1 + int.Parse(cNum1.Substring(i, 1)) + int.Parse(cNum2.Substring(i, 1));
            if (bf2 > 9) {
                retVal += bf2.ToString().Substring(bf2.ToString().Length - 1, 1);
                bf1 = int.Parse(bf2.ToString().Substring(0, bf2.ToString().Length - 1));
            } else {
                retVal += bf2.ToString();
                bf1 = 0;
            }
        }
        if (bf1 != 0) {
            retVal += bf1.ToString();
        }
        char[] ret1 = retVal.ToCharArray(); 
        Array.Reverse(ret1); 
        retVal = new string(ret1);
        return retVal;
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ Why is it that you are using int.Parse() on each digit but not on the entire number? Would like to know the actual purpose as I didn't understand what you mean by 'without overflowing'. \$\endgroup\$ – elimad Aug 5 '15 at 5:41
  • \$\begingroup\$ This function is used for numbers that are too large to have any operators done on them, such as numbers larger than: 18446744073709551615. \$\endgroup\$ – GriffinMite Aug 5 '15 at 5:44
  • 1
    \$\begingroup\$ No one mentioned BigInteger yet? Still, what you're doing is a good coding exercise. \$\endgroup\$ – Dennis_E Aug 5 '15 at 8:05
  • \$\begingroup\$ @Dennis_E I have now :) I assumed that it would be the first answer to this question. Don't reinvent the wheel. \$\endgroup\$ – Viktor Mellgren Aug 5 '15 at 9:17
5
\$\begingroup\$

Some style comments

  • Add vertical spaces to group code which logically belongs together.
  • Don't declare multiple variables on the same line.
  • Name your variables as meaningfully as possible. Names like bf1 won't tell Bob the maintainer what it is about, making it harder to maintain the code.
  • methods should be named using PascalCase casing. See: C# naming guidelines
  • Usually a C# developer would expect one to use the Allman indention style; i.e. place the opening brace on the next line.
  • Always add a scope specifier (access modifier) to methods and variables.

This method is violating the Single responsibility principle. It is just doing too much like normalizing the given input, adding the numeric values of the chars and constructing the result.

Let us take a look at what you are doing to normalize the string

    string cNum1 = null;
    string cNum2 = null;
    if (num1.Length > num2.Length) {
        for (int i = 0; i < (num1.Length - num2.Length); i++) {
            cNum2 += "0";
        }
    } else if (num1.Length < num2.Length) {
        for (int i = 0; i < (num2.Length - num1.Length); i++) {
            cNum1 += "0";
        }
    }
    cNum1 += num1; 
    cNum2 += num2;

Each time you call cNum1 += "0" or cNum2 += "0" you are creating a new string. By using the PadLeft() method together with Math.Max() and extracting the the normalization to a separate method your code will look cleaner.

private static string NormalizeValue(string value, int maxLength)
{
    return value.PadLeft(maxLength, '0');
}  

This has also the advantage that you won't need cNum1 and cNum2 anymore.

static string addString(string num1, string num2) {

    int maxLength = Math.Max(num1.Length, num2.Length);
    num1 = NormalizeValue(num1, maxLength);
    num2 = NormalizeValue(num2, maxLength);

    .....

}

If you start the for loop at maxLength - 1 and decrement the index you won't need the reversing of the char arrays anymore.

Using a StringBuilder to add the results of the single additions will result in fewer created strings.

If you are sure that the passed in strings only contain digits you can use a neat little trick. You can subtract a char '0' from the current char like e.g

Assume first = '2' and second = '4' are the chars currently be processed.

int result = first - '0' + second - '0';  

this boils down to

int result = '2' - '0' + '4' - '0' ;

and is subtracting the ASCII values of the chars

int result = 50 - 48 - 52 - 48;

so there is no need to call int.Parse() anymore. By extracting the two uses of '0' to a const this will be beautified.

const int doubleZeroValue = 96;
int result = first + second - doubleZeroValue;  

This will lead to

private static string NormalizeValue(string value, int maxLength)
{
    return value.PadLeft(maxLength, '0');
}

private static string AddString(string firstNumber, string secondNumber)
{
    const int doubleZeroValue = 96;
    int maxLength = Math.Max(firstNumber.Length, secondNumber.Length);
    firstNumber = NormalizeValue(firstNumber, maxLength);
    secondNumber = NormalizeValue(secondNumber, maxLength);

    StringBuilder sb = new StringBuilder(maxLength + 1);
    int result = 0;
    for (int i = maxLength - 1; i >= 0; i--)
    {
        result += firstNumber[i] + secondNumber[i] - doubleZeroValue;
        if (result < 10)
        {
            sb.Append(result);
            result = 0;
            continue;
        }
        sb.Append(result - 10);
        result /= 10;

    }

    if (result > 0)
    {
        sb.Append(result);
    }

    char[] resultDigits = sb.ToString().ToCharArray();
    Array.Reverse(resultDigits);

    return new string(resultDigits);

}

It still has some magic numbers in it like

sb.Append(result - 10);
result /= 10;  

which could/should be extracted to meaningful constants but I couldn't come up with the names lacking enough english.

\$\endgroup\$
  • \$\begingroup\$ +1 The explanation about the char as a number is great. i feel that not every programmer knows that -- but because of that reason i would parse it as an int \$\endgroup\$ – Jens Aug 5 '15 at 8:56
  • 1
    \$\begingroup\$ I would not use the doubleZero trick, it makes the code harder to read and I don't think it will really speed the whole process up very much \$\endgroup\$ – Falco Aug 5 '15 at 11:11
  • \$\begingroup\$ char computation is nice, but it removes the input validation given by the use of int.parse. Therefore, this function allows to add carrots and cauliflowers. \$\endgroup\$ – njzk2 Aug 5 '15 at 14:30
  • \$\begingroup\$ also result -= 9; should be result /= 10; \$\endgroup\$ – njzk2 Aug 5 '15 at 14:31
  • \$\begingroup\$ and the continue is often considered bad practice if it can easily be replaced by something else. in this case, an else block. \$\endgroup\$ – njzk2 Aug 5 '15 at 14:32
4
\$\begingroup\$

What about simply using the built in BigInteger?

using System.Numerics;

using System;

public class Program
{
    public static void Main()
    {
        BigInteger num1 = BigInteger.Parse("112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123");
        BigInteger num2 = BigInteger.Parse("321112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123112354651312311235465131231123546513123");
        BigInteger sum = num1 + num2;
        Console.WriteLine(sum);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ then he could google it and find this SO question: stackoverflow.com/questions/10624815/…. This is code review. If he wanted a ready solution i am sure he found one. Otherwise he learned his lesson - First think/google then do/code. But for sure it is the easiest, safest und maybe best implemented way. and it is only available in .NET 4 or higher. so if you need to use .NET < 4 you want to programm it yourself. \$\endgroup\$ – Jens Aug 5 '15 at 9:19
  • 3
    \$\begingroup\$ Yes, of course. But even if it is "obvious" I think makes sense to answer anyway, if it has been missed, or for completeness sake. \$\endgroup\$ – Viktor Mellgren Aug 5 '15 at 9:28
2
\$\begingroup\$

Well i think you solution is not that good because you are working very hard with string and working with string is very slow (compared to calculations with integer). So and what's about the code maintainability? It is not that good too, because you can read that code only very hard (which also is because of that decent code readability @Heslacher spoke about in his answer). But the main aspect is the fact that you work with strings. as a code reader without debugger you will have a very hard time reading and understanding your code.

What is a good Solution for this problem?
The first thing i would always do is to create a class! I called mine BigInt

class BigInt
{
    public List<int> Integer { get; set; }

    public BigInt(string number)
    {
        this.Integer = this.CalculateBigInteger(number);
    }

    public BigInt(List<int> list)
    {
        this.Integer = list;
    }

    private List<int> CalculateBigInteger(string number)
    {
        return number.Reverse()
                     .Select(chararcter =>int.Parse(chararcter.ToString()))
                     .ToList();
    }
}

With this code i am able to read the string into an int with -- yeah nearly -- infinite length.

Now we implement the add function which is the hardest parts and wich took me 2 and a half try:

The problems:

  • One Number may be longer than the other one
  • you need to add from the back (this is covered in the code snipped above)
  • you have carryover(when you have 8 + 4 you have 12 so your add-result is 2 and your carryover is 1)

The add method:

public static BigInt Add(BigInt int_1, BigInt int_2)
{
    var result = new List<int>();

    int carryOver = 0;

    IEnumerator<int> enumerator_1 = int_1.Integer.GetEnumerator();
    IEnumerator<int> enumerator_2 = int_2.Integer.GetEnumerator();

    enumerator_1.MoveNext();
    enumerator_2.MoveNext();

    bool hasNext_1 = true;
    bool hasNext_2 = true;

    while (hasNext_1 || hasNext_2)
    {
        var value = NumberAdd(enumerator_1.Current, enumerator_2.Current, ref carryOver);
        result.Add(value);

        hasNext_1 = enumerator_1.MoveNext();
        hasNext_2 = enumerator_2.MoveNext();
    }

    if (carryOver != 0)
    {
        result.Add(carryOver);
    }

    return new BigInt(result);
}

I iterate over my two integer lists with an enumerator. when the enumerator has no more elements enumerator.MoveNext() return false, but if you call enumerator.Current it will also return 0 which is pretty nice, because enumerator1.Current + enumerator2.Current is enumerator1.Current when enumerator2 has no more elements.

I also added these small helper method to make the code better readable:

private static int NumberAdd(int value_1, int value_2, ref int carryOver)
{
    var addResult = value_1 + value_2 + carryOver;
    carryOver = addResult / 10;
    var addValue = addResult % 10;
    return addValue;
}

the ref word means that this variable is referenced. that means when you change the value it is also changed in the calling scope. otherwise the change would be garbage collected because an integer is call by value and not call by reference. in other words: ref makes this integer call by reference.

Print the result:
This code is nearly 1:1 copied from SO:

public string ToString()
{
    StringBuilder sb = new StringBuilder();
    foreach (var number in this.Integer)
    {
        sb.Append(number.ToString());
    }

    var reverseString = sb.ToString().ToCharArray();
    Array.Reverse(reverseString);
    return new string(reverseString);
}

Usage:

static void Main(string[] args)
{
    var bigInt_1 = new BigInt("1346876136548");
    var bigInt_2 = new BigInt("984651484651484654");

    var result = BigInt.Add(bigInt_1, bigInt_2);
    Console.WriteLine(result.ToString());
    Console.ReadKey();
}

i create 2 objects of BigInt with the Constructor passing the big values as a string. The Result is:

984652831527621202

Advices:

  1. Try to get clear about the problem
  2. Find good data structures to solve your problem -- this is most of the time one or even more new classes and in my case the data structure list (a dynamic data structure)
  3. Try to program as clear as possible -- always think about someone other is reading your code and ask yourself the question: is he able to understand your code without a book of comments? if no, try to code it again and better. i also coded this example 3 times because i was not happy about my code even if the code worked

    Very interesting topic. i asked me this a bunch of time what is a good solution to work with bigger values than an integer / long can hold. But please see that this solution has very very bad memory handle. For one number from 0-9 you allocate memory of the with of one integer. if you have problems with memory you should use byte or need another even much better solution!

If you have questions or other things you want to talk about, i'd would be happy to answer you

\$\endgroup\$

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.