Handling Large Number in a Simple Way

• Download binaries - 66.37 KB
• Download source - 1.31 KB

Introduction

This article shows how to manipulate very large numbers. The purpose of this article is to illustrate the basic logic behind the handling of large numbers. After reading this article and going through the code, you would be able to answer the following questions:

1. How to manipulate very large numbers
2. How to add, subtract and multiply very large numbers
3. Break large calculations into smaller fragments and deal with the smaller problems with ease and then combine the result to obtain the solution of a large problem

Background

• The large numbers are represented in the form of arrays of 64byte integer. Like 12345678 is stored as element[0] =5678, element[1]=1234, element[2]=0000, element[3]= 0000
• To add two such numbers, the following logic is used:

  BigNum1 = 0000 1234 1111 2222 
  BigNum2 = 1111 2222 3333 4444 
  ---------------------------------------- 
  BigNum1+BigNum2 = 1111 3456 4444 666

• To multiply two such numbers, the following logic is used:

  (a<sub>1</sub>x +b<sub>1</sub>)(a<sub>2</sub>x+b<sub>2</sub>) = a<sub>1</sub>a<sub>2</sub>x<sup>2</sup> + (a<sub>1</sub>b<sub>2</sub>+b<sub>2</sub>a<sub>1</sub>)x + b<sub>1</sub>b<sub>2</sub> 

This logic can be expanded further for more powers of x.

Using the Code

The source code consists of single file BigNum.cpp. There is a BigNum class in the code. This class represents a Big Number greater than 64 bits and less than 10³²- 1. There are overloaded methods for the operators Addition(+), Subtraction(-) and Multiplication(*). There is also a method named void Normalize(BigNum). It convert any BigNum not in proper representation into a array of 4 long numbers where each element stores 8 digits of the number.

Addition and Subtraction operations are done as follows:

1. Both BigNum objects to be added and subtracted are normalized.
2. Addition/subtraction operations are applied to the corresponding array elements to form a new BigNum.
3. The resulting BigNum is normalized again. This contains the result of addition or subtraction.

Following is the code for the addition:

friend BigNum operator + (BigNum b1, BigNum b2 )
        { 
               BigNum b3;
               b1.Normalize();
               b2.Normalize();
 
               for( int i=0;i<4;i++)
               {
                       b3.no[i] = b1.no[i] + b2.no[i];
               }
               
               for( int i=0;i<3;i++)
               {
                       if ( b3.no[i] < b2.no[i])
                        b3.no[i] = b3.no[i] + 1;
               }
               b3.Normalize();
               return b3;
        } 

Multiplication operation is done as follows:

1. Both BigNum objects to be added and subtracted are normalized.
2. Linear Cross multiplication method is used for calculation of each single array element in the resulting BigNum variable.
3. Resulting BigNum variable is normalized.

Following is the code for multiplication:

friend BigNum operator * (BigNum b1, BigNum b2 )
        {
               BigNum b3;
               b1.Normalize();
               b2.Normalize();
               
               b3.no[3] = b2.no[3]*b1.no[3];
               b3.no[2] = b2.no[2]*b1.no[3] + b2.no[3]*b1.no[2];
               b3.no[1] = b2.no[1]*b1.no[3] + b2.no[2]*b1.no[2] + b2.no[1]*b1.no[3];
               b3.no[0] = b2.no[0]*b1.no[3] + b2.no[1]*b1.no[2] + 
		b2.no[2]*b1.no[1] + b2.no[3]*b1.no[0];
    
               b3.Normalize();
               return b3;
        }

Points of Interest

During the time I was drafting this article, I was getting a good exposure of the kind of problems that come in technical writing. To be very honest, this is my first article of this type and I am enjoying writing this article. The code is purely written by me. Suggestions regarding the clarity, confusion, code, technical writing are welcome. Comments are also welcome. You can also mail me at funatlearn@ontheedge.co.in with subject BigNum CodeProject article regarding the same.

History

The code is the first draft of the program. So, no history regarding the code is available. Though I would definitely like to enhance the code and make it more efficient and useful utility rather than bounding its current limits, I have some inputs from my side and suggestions from your side are more than welcome.

Hope you enjoyed understanding the code. Thank you!