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.
Next: Conclusion >>
More C++ Articles
More By Gabor Bernat
/ 5 
