Click here to Skip to main content
13,291,084 members (68,496 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


14 bookmarked
Posted 2 Sep 2010

Addition, Multiplication of Very Long Integers

, 7 Sep 2010
Rate this:
Please Sign up or sign in to vote.
Performing addition, multiplication of very long integers using C#


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#.


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 : 
            int digit2 = (j > length2 - 1) ? 0 : 
            int digitsum = digit1 + digit2 + carry;
            if (digitsum >= 10)
                digitsum -= 10;
                carry = 1;
                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.


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


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

No Biography provided

You may also be interested in...


Comments and Discussions

QuestionThere are some bug Pin
rajeev7513-Jun-15 9:24
memberrajeev7513-Jun-15 9:24 
GeneralMy vote of 1 Pin
Zhekov14-Sep-10 6:42
memberZhekov14-Sep-10 6:42 
Generalmy vote of 3 Pin
sjelen10-Sep-10 7:28
membersjelen10-Sep-10 7:28 
GeneralMy vote of 3 [modified] Pin
icetea947-Sep-10 7:01
membericetea947-Sep-10 7:01 
GeneralC# 4.0 has a BigInteger class Pin
anandkj2-Sep-10 21:51
memberanandkj2-Sep-10 21:51 
GeneralRe: C# 4.0 has a BigInteger class Pin
Eddy Vluggen2-Sep-10 22:01
mvpEddy Vluggen2-Sep-10 22:01 
GeneralRe: C# 4.0 has a BigInteger class Pin
Luc Pattyn3-Sep-10 3:49
mvpLuc Pattyn3-Sep-10 3:49 
GeneralRe: C# 4.0 has a BigInteger class Pin
Eddy Vluggen3-Sep-10 9:41
mvpEddy Vluggen3-Sep-10 9:41 
Luc Pattyn wrote:
using strings for basic operations? OMG | :OMG:

Yes. No! I dunno, multiplying long.MaxValue + 1 by two wouldn't be a basic operation. At least not if you're not using .NET 4. Or .NET 3.5 and F#. And it would typically originate from a string, with a textbox or a configuration value as the source.

Meh, you confused me.

Luc Pattyn wrote:
ToString() on large integers is extremely expensive.

He's caching the result as a string, merely returning it in the ToString;
private string numberAsString; //very long number as string.
public override string ToString() 
    return numberAsString.TrimStart('\0');

And yes, it would have made me even happier if it was an array of int, containing each digit.

There's another toString in a loop, but I doubt that you'd call those large integers;
int digit1 = (j > length1 - 1) ? 0 : Convert.ToInt32(veryLongString1[j].ToString());

Point is that the solution is correct (it produces the correct result, based on a working algorithm) and not outdated. It's not the most efficient way of adding large numbers, but it doesn't claim to be so.

The thing I like about the DIY-BigInt is the fact that it's a nice translation of the addition-algorithm that we learned in school, and you can follow the computers action using the debugger. It's easy to step through, explaining on a single paper what's inside every variable (and proving that by inspecting it). Good as a homework assignment Smile | :)
I are Troll Suspicious | :suss:

GeneralRe: C# 4.0 has a BigInteger class Pin
Luc Pattyn3-Sep-10 15:55
mvpLuc Pattyn3-Sep-10 15:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171207.1 | Last Updated 8 Sep 2010
Article Copyright 2010 by Saleth Prakash
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid