Addition, Multiplication of Very Long Integers

• Download source code - 2.67 KB

Introduction

Well, I am posting an article after a long gap. When I was reading a C++ program, I came across a program that was showing the use of very long integers. It was quite good and that impressed me and made me write the same in C#.

Overview

The purpose of the article is to be able to build a class that allows any C# programmer to use very long integer related functionalities like addition and multiplication. I have implement it using operator overloading. While reading in C++ and while analyzing the program to write in C#, I came to the conclusion that using operator overloading makes the performance easy and it is very easy to understand the code and functionality in certain cases.

What is Operator Overloading? (Definition from Wikipedia)

In computer programming, operator overloading (less commonly known as operator ad-hoc polymorphism) is a specific case of polymorphism in which some or all of operators like +, =, or == have different implementations depending on the types of their arguments. Sometimes the overloadings are defined by the language; sometimes the programmer can implement support for new types. Operator overloading is claimed to be useful because it allows the developer to program using notation "closer to the target domain" and allows user-defined types a similar level of syntactic support as types built into the language. It can easily be emulated using function calls; for an example, consider the integers a, b, c:

a + b * c

In a language that supports operator overloading, and assuming the '*' operator has higher precedence than '+', this is effectively a more concise way of writing:

add (a, multiply (b,c))

What is Operator Overloading in C#?

All unary and binary operators have pre-defined implementations that are automatically available in any expressions. In addition to this pre-defined implementation, user defined implementations can also be introduced in C#. The mechanism of giving a special meaning to a standard C# operator with respect to a user defined data type such as classes or structures is known as operator overloading. Remember that it is not possible to overload all operators in C#. The following table shows the operators and their overloadability in C#.

Operators Overloadability

• +, -, *, /, %, &, |, <<, >> All C# binary operators can be overloaded.
• +, -, !, ~, ++, –, true, false All C# unary operators can be overloaded.
• ==, !=, <, >, <= , >= All relational operators can be overloaded, but only as pairs.
• &&, || They can’t be overloaded.
• () (Conversion operator) They can’t be overloaded.
• +=, -=, *=, /=, %= These compound assignment operators can be overloaded. But in C#, these operators are automatically overloaded when the respective binary operator is overloaded.
• =, . , ?:, ->, new, is, as, size of These operators can’t be overloaded.

In C#, a special function called operator function is used for overloading purpose. These special functions or methods must be public and static. They can take only value arguments.The ref and out parameters are not allowed as arguments to operator functions. The general form of an operator function is as follows:

public static return_type operator op (argument list)

Where the op is the operator to be overloaded and operator is the required keyword. For overloading the unary operators, there is only one argument and for overloading a binary operator, there are two arguments. Remember that at least one of the arguments must be a user-defined type such as class or struct type.

Overloading Unary Operators – the general form of operator function for unary operators is as follows:

public static return_type operator op (Type t){// Statements}

where Type must be a class or struct. The return type can be any type except void for unary operators like +,~, ! and dot (.). But the return type must be the type of ‘Type’ for ++ and o remember that the true and false operators can be overloaded only as pairs. The compilation error occurs if a class declares one of these operators without declaring the other.

Why Operator Overloading?

Operating overloading allows us to pass different variable types to the same function and produce different results. In this article, I have given the low-down on operator overloading in C#. Operator overloading is common-place among many efficient C# programmers. It allows you to use the same function name, but as different functions.

In this article, I have shown exactly what operator overloading is, and how you can get it to work for you in C#.

Under the hood

1. Addition

First the very long numbers are inputted as string. Then each character in the string is converted as integers. Before performing the operations, the string is reversed.

The operator +() method adds two very long objects and leaves the result in a third very long object. It does this by considering their digits one at a time. It adds digits from both numbers storing a carry if necessary. Then it adds the digits in position 1 adding the carry if necessary. It continues until it has added all the digits in the larger of the two numbers. If the numbers are different length, the nonexistent digits in the short number are set to 0 before being added.

Diagrammatic Representation of the Addition

Addition Code

// Adds two very long numbers.
public static VeryLongInteger operator +(VeryLongInteger veryLongInteger1, 
	VeryLongInteger veryLongInteger2)
    {
        char[] outputChars = new char[MAXLENGTH];
        string veryLongString1 = Reverse(veryLongInteger1.ToString());
        string veryLongString2 = Reverse(veryLongInteger2.ToString());
        int length1 = veryLongString1.Length;
        int length2 = veryLongString2.Length;
        int maxLength = length1 > length2 ? length1 : length2;
        int carry = 0;
        int j = 0;
        for (j = 0; j < maxLength; j++)
        {
            int digit1 = (j > length1 - 1) ? 0 : 
		Convert.ToInt32(veryLongString1[j].ToString());
            int digit2 = (j > length2 - 1) ? 0 : 
		Convert.ToInt32(veryLongString2[j].ToString());
            int digitsum = digit1 + digit2 + carry;
            if (digitsum >= 10)
            {
                digitsum -= 10;
                carry = 1;
            }
            else
                carry = 0;
            outputChars[j] = Convert.ToChar(Convert.ToString(digitsum));
        }
        if (carry == 1)
            outputChars[j++] = '1';
        return new VeryLongInteger(Reverse(new string(outputChars)));
    }

2. Multiplication

Here also the same logic. Multiplication uses the operator *() method. This method performs multiplication by multiplying the multiplicand by each separate digit in the multiplier. It calls the MultiplyDigit() method to this. The results are then multiplied by 10 an appropriate number of times to shift the result to match the position of the digit, using the Mulitply10() method. The result of these separate calculations are then added together using operator +() method.

Multiplication Code

// Multiplies two very long numbers.
public static VeryLongInteger operator *(VeryLongInteger veryLongInteger1, 
	VeryLongInteger veryLongInteger2)
    {
        char[] outputChars = new char[MAXLENGTH];
        string veryLongString = Reverse(veryLongInteger2.ToString());
        VeryLongInteger powerproduct = null;
        VeryLongInteger outputVeryLongInteger = new VeryLongInteger("0");
        int j = 0;
        for (j = 0; j < veryLongString.Length; j++)
        {
            int digit = Convert.ToInt32(veryLongString[j].ToString());
            powerproduct = MultiplyDigit(veryLongInteger1, digit);
            for (int k = 0; k < j; k++)
            {
                powerproduct = Multiply10(powerproduct);
            }
            outputVeryLongInteger = outputVeryLongInteger + powerproduct;
        }
        return outputVeryLongInteger;
    }

3. Factorial

Here we acheive factorial as a recursive calling of multiplication. We can find factorial of number upto 250 (!Wow).

Factorial Code

VeryLongInteger v1 = new VeryLongInteger("1");
int num = 100;
for (int i = num; i > 0; i--)
{
    VeryLongInteger v2 = new VeryLongInteger(i.ToString());
    v1 = v1 * v2;
}

Sample Output

Points of Interest

Yes, of course .NET 4.0 has a BigInteger class which is more efficient. But well, I think this VeryLongInteger class can be used for the previous versions. And of course, we can understand the internal working of these types of functionalities.

Conclusion

Thanks for viewing this article. I expect feedback from you. You expect more from me.