Home arrow C++ arrow Page 4 - Large Numbers
C++

Large Numbers


People in general seem to dislike the concept of number arithmetic, especially if it’s all about large numbers – and here we literally mean huge ones. However, the twenty-first century is the era of computers. Our everyday lives are covered by tons of data encapsulated in computers. In this series we’re going to discuss and code operations of which Euler wouldn’t dare to dream.

Author Info:
By: Gabor Bernat
Rating: 5 stars5 stars5 stars5 stars5 stars / 8
July 15, 2008
TABLE OF CONTENTS:
  1. · Large Numbers
  2. · The User Interface
  3. · File Input Lesson
  4. · Addition and Subtraction
  5. · Conclusion

print this article
SEARCH DEVARTICLES

Large Numbers - Addition and Subtraction
(Page 4 of 5 )

We are back to the basics then. Each of us learned during our first years of elementary school how to complete these basic arithmetic operations. It isn't all that devilish. And it can be even simpler if we use a little trick to play around with the signs of the two numbers.

To start with, we will eliminate the problem of subtraction by perceiving it as an adding procedure; it's just that the right side of the operator will suffer a sign change and after that we add the two numbers. This way we can allow negative numbers for addition and also resolve this issue in one operator. So the subtraction is going to be just a few lines long. Check out the following block of code to get a sense of what I mean.

Large_Numbers Large_Numbers::operator-( Large_Numbers& x)

{

x.sign*=-1; //Inverse x's sign

Large_Numbers alfa = x + (*this) ;

x.sign *= -1; // Reset the sign

 

return alfa;

}

However, it is now up to the addition to take care of the subtraction. Both subtraction and addition are evaluated from right to left. The only significant difference is that during the subtraction operation, there may be a need to borrow from the following element, while in addition the opposite is the case. An overflow may occur and we need to carry it further to the next element.

But for now let's go back to subtraction seen as addition. The easy way is to play around a little with the signs of the two numbers. Manipulating the sign isn't hard and can save quite a lot of time for us. First we shall categorize adding two negative numbers as a standard addition but with a negative result.

Secondly the subtraction issue needs to be handled. The only problem here is that we may come to the end with a borrowed item and we don't have anywhere from which to take it. You will see the problem in the example below. Using the method of subtracting each item from the one below (stepping through the numbers from left to right) we'll came up with a strange result.

0.99 - 1.00 -

1.00 0.99

-1.99 and a -1 item to borrow from somewhere. 0.01 * (-1)

The solution is quite simple. Instead of looking at the subtraction as 0.99 - 1 we'll reformulate it as - (1 - 0.99). By this we maintained its mathematical correctness (it's a valid operation) and we only need to change the results sign. If you think about this a little, you'll see that this situation pops up only in situations where, when looking at the absolute of the two numbers, the subtracted number is larger than the one from which we are subtracting. That's it; we got rid of the most annoying problem.

Now we only need to make the proper Addition and Subtraction. All the work described above is completed by the following lines. Also note here that I give in many places the variables for a function by reference. This is so we can get away with using less memory, as the returned items would be first locally created and then sent back as a copy. This is quite unnecessary for us, however take a look at the code snippet:

if( x.sign == +1 && sign == +1 || (x.sign ==-1 &&sign==-1))

{

CalculateAdd(*this,x,t_temp,t_all,t_whole); t_sign = sign; // Set sign

}

else

{ // it's a Subtract procedure

int signls = this->sign;

int signrs = x.sign;

int compare_result;

this->abs();

x.abs();

if(((compare_result=this->compare(x))>0 && signls == -1)

||(compare_result < 0 && signrs == -1 ))

{

// Switch the signs

this->sign = signls;

x.sign = signrs;

t_sign = -1;

sign *= -1;

x.sign *= -1;

 

CalculateSubtract(*this,x,t_temp, t_all,t_whole);

 

//Switch back the signs

sign *= -1;

x.sign *=-1;

}

else

{

this->sign = signls;

x.sign = signrs;

CalculateSubtract(*this,x,t_temp, t_all,t_whole); t_sign = 1; }

}

Now we need to take care of the CalculateAdd and the CalculateSubtract functions. The addition is completed as though in the primary classes, just that adding two numbers isn't done by bringing both of the numbers to the same real and integer digit number. That would be an awful waste of memory. Instead we are taking it slowly and divide it into sessions.

Any extra element that exists for an addition at the real side is just copied into the result. Once we are at the same end position in both of the numbers we start adding until, in one of them, we reach the end. Any overflow that we have is truncated. The last digit is entered in the result and the rest is passed to the next number through the carry (remainder) member. At the end we take care of the eventual carry item and copy the rest of the number from which there still are members to the result.

The subtraction follows the same principle, but it doesn't have overflow. Instead, we need to borrow. Still it remains the same in principle, it's just that now we'll have a negative carry item. Also at the end of the operation we are calling the optimization function on the result so we won't store unnecessary zeroes. I won't cover the question more deeply. If you are interested, examine the source code provided in the download on the last page of this article. The code is almost painfully commented. In comments, I explain what I'm doing and why I'm doing it in each line. 


blog comments powered by Disqus
C++ ARTICLES

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials