< Free Open Study > 
Implementing a Large Integer ADT
The range of integer values that can be supported varies from one computer to another. In most C++ environments, file <climits> shows you the limits. For example, long integers range from 2,147,483,648 to +2,147,483,647 on many machines. However long they may be on a particular machine, some user is bound to want to represent integers with even larger values. Let's design and implement a class LargeInt that allows the user to manipulate integers where the number of digits is limited only by the size of the free store.
Because we are providing an alternative implementation for a mathematical object, an integer number, most of the operations are already specified: addition, subtraction, multiplication, division, assignment, and the relational operators. For this Case Study, we limit our attention to addition, subtraction, equality, and less than. Enhancing this ADT with the other operations is left as a programming assignment.
In addition to the standard mathematical operations, we need an operation that constructs a number one digit at a time. This operation cannot be a parameterized constructor because the integer parameter might be too large to represent in the machineafter all, that is the idea of this ADT. Instead, we need a special member function that can be called within a loop that inserts the digits one at a time. We also need an operation that writes the integer to a file, one digit at a time, from most significant digit to least significant digit.
Before we can begin to look at the algorithms for these operations, we need to decide on our representation. Earlier we were designing the class SpecializedList for use in this Case Study, so you know that we will use a circular, doubly linked list. Why doubly linked? Because we need to access the digits from most significant to least significant to write them to a file, and we need to access the digits from least significant to most significant to manipulate them arithmetically. Why circular? Because we need to insert digits from most significant to least significant when constructing an object, and we need to insert digits from least significant to most significant when constructing an object that is the result of an arithmetic operation.
Figure 6.23 shows several examples of numbers in a singly linked list and an addition. Figure 6.23(a) and (c) show one digit per node; Figure 6.23(b) shows several digits per node. We develop the algorithms for a single digit per node. You are asked in the exercises to explore the necessary changes to include more than one digit in each node.
Here is the first approximation of the class LargeInt:
#include "SpecializedList.h" #include <fstream> class LargeInt { public: LargeInt(); ~LargeInt(); LargeInt(const LargeInt&); bool operator<(LargeInt second); bool operator==(LargeInt second); LargeInt operator+(LargeInt second); LargeInt operator(LargeInt second); void InsertDigit(int); void Write(std::ofstream&); private: SpecializedList number; };
Earlier we said that classes in a program typically exhibit one of the following relationships: They are independent of each other, they are related by composition, or they are related by inheritance. The classes LargeInt and SpecializedList are related by composition. As you see in the private part of the class definition, a LargeInt Object is composed of (or contains) a SpecializedList object. Just as inheritance expresses an is a relationship (a CountedQueType object is a QueType object [and more]), composition expresses a has a relationship (a LargeInt object has a SpecializedList object inside it).
Addition and Subtraction Let's look at addition of positive integers first, and then look at the role of the sign. We begin by adding the two least significant digits (the units position). Next, we add the digits in the tens position (if present) plus the carry from the sum of the least significant digits (if any). This process continues until one of three things happens: (1) the first operand runs out of digits; (2) the second operand runs out of digits; or (3) both run out of digits simultaneously. Rather than try to determine which operand is self at this stage, let's summarize these observations in an algorithm with three parameters of type SpecializedList: first, second, and result where result = first + second.
Add(first, second, result)
Set carry to 0 Set finished1 to false Set finished2 to false first.ResetBackward() second.ResetBackward() while (!finished1 AND !finished2) first.GetPriorItem(digit1, finished1) second.GetPriorItem(digit2, finished2) Set temp to digit1 + digit2 + carry Set carry to temp/10 result.InsertFront(temp % 10) Finish up digits in first, adding carries as necessary Finish up digits in second, adding carries as necessary if (carry != 0) result.InsertFront(carry)
Apply the algorithm to the following examples.
322 388 399 999 3 1 988 0 44 108 1 11 44 99 100 0         366 496 400 1010 47 100 1088 0
Now let's examine subtraction in the simplest case: Both integers are positive and the smaller one (second) is subtracted from the larger one (first). Again, we begin with the digits in the units position. Let's call the digit in first digit1 and the digit in second digit2. If digit2 is less than digit1, we subtract and insert the resulting digit at the front of the result. If digit2 is greater than digit1, we borrow 10 and subtract. Then we access the digits in the tens position. If we have borrowed, we subtract 1 from the new digit1 and proceed as before. Because we have limited our problem to the case where first is larger than second, they either run out of digits together or first still contains digits when second has been processed. Note also that this constraint guarantees that borrowing does not extend beyond the most significant digit of first.
Sub(first, second, result)
Set borrow to false Set finished1 to false Set finished2 to false first.ResetBackward() second.ResetBackward() while (!finished1 AND ! finished2) first.GetPriorItem(digit1, finished1) if (borrow) if (digit1 != 0) Set digit1 to digit1  1 Set borrow to false else Set digit1 to 9 Set borrow to true second.GetPriorItem(digit2, finished2) if (digit2 <= digit1) result.InsertFront(digit1  digit2) else Set borrow to true result.InsertFront(digit1 + 10  digit2) while (!finished1) first.GetPriorItem(digit1,finished1) if (borrow) if (digit1 != 0) Set digit1 to digit1  1 Set borrow to false else Set digit1 to 9; Set borrow to true result.InsertFront(digit1)
By now you are wondering about the usefulness of a subtraction algorithm that is so restricted. With these restricted subtraction and addition algorithms, we can implement addition and subtraction with all combinations of signs. Here are the rules.
Addition Rules
If both operands are positive, use the addition algorithm.
If one operand is negative and one operand is positive, subtract the smaller absolute value from the larger absolute value and give the result the sign of the larger absolute value.
If both operands are negative, use the addition algorithm and give the result a minus sign.
Subtraction Rules
Remember how subtraction seemed more difficult than addition when you were first learning arithmetic? Not anymore. We need to use only one subtraction rule: "Change the sign of the subtrahend and add." We do have to be careful about how we change the sign because we do not want to actually change the sign of the argument passed to subtract, as that would produce an unwanted side effect. Therefore, we create a new LargeInt object, make it a copy of the second parameter, invert its sign, and then add.
These rules indicate that the signs should be manipulated separately from the actual addition or subtraction. Therefore, we must add a sign data member to our LargeInt class. How shall we represent the sign? Let's define an enumeration type SignType having two constants (MINUS and PLUS) and adopt the convention that zero has the sign PLUS. Let's encode our simplified addition and subtraction algorithms into the auxiliary functions Add and Sub, which take three arguments each of type SpecializedList. The code for each overloaded arithmetic symbol applies the rules for its operation and calls either Add or Sub. Sub should not be called, however, if the two operands are the same, as the result would be zero. Here are the algorithms for operator+ and operator.
operator+{LargeInt second)
// self is first operand if sign = second.sign Add(number, second.number, result.number) Set result.sign to sign else if self < second Sub(second.number, number, result.number) Set result.sign to second.sign else if second < self Sub(number, second.number, result.number) Set result.sign to sign return result
operator(Largelnt second)
Set copy to a copy of second Set copy.sign to !second.sign Add(number, copy.number, result.number) return result
Relational Operators When comparing strings, we compare the characters in each character position, one at a time, from left to right. The first characters that do not match determine which string comes first. When comparing numbers, we simply compare the numbers digit by digit if they have the same sign and are the same length (have the same number of digits). Here are the rules:
A negative number is less than a positive number.
If the signs are positive and one number has more digits than the other, then the number with fewer digits is the smaller value.
If the signs are both negative and one number has more digits than the other, then the number with more digits is the smaller value.
If the signs are the same and the number of digits is the same, compare the digits from left to right. The first unequal pair determines the result.
Look at the following examples carefully and convince yourself that all the cases for "less than" are represented.
True 
False 

1 < 1 
1 < 1 
5 < 10 
10 < 5 
10 < 5 
5 < 10 
54 < 55 
55 < 54 
55 < 54 
54 < 55 
55 < 55 

55 < 55 
Let's summarize these observations for the "less than" operation. Because we have only one digit per node, the class SpecializedList's LengthIs function gives us the number of digits in the number. It is a member function, so the first operand is self and the second operand is second.
operator<(second)
if (sign is MINUS AND second.sign is PLUS) return true else if (sign is PLUS AND second.sign is MINUS) return false else if (sign is PLUS AND number.LengthIs() < second.number.LengthIs()) return true else if (sign is PLUS AND number.LengthIs() > second.number.Length Is()) return false else if (sign is MINUS AND number.Lengthls() > second.number.LengthIs()) return true else if (sign is MINUS AND number.LengthIs() < second.number.LengthIs()) return false else // Must compare digit by digit Set relation to CompareDigits(number, second.number) if (sign is PLUS AND relation is LESS) return true else if (sign is PLUS AND relation is GREATER) return false else if (sign is MINUS AND relation is GREATER) return true else return false
This algorithm calls the function LengthIs of class SpecializedList eight times. We should make the number of digits be a data member of the class LargeInt and avoid these function calls. Thus each operation that defines a new large integer must call LengthIs once and store this value in the LargeInt object. Let's call the new data member numDigits. We now need to specify an operation that compares the digits in two equallength lists and returns LESS, GREATER, or EQUAL depending on the relationship of its two arguments. We pass the list of digits only, so this function compares the absolute values of its two arguments.
RelationType CompareDigits(operand1, operand2)
operand 1.ResetForward() operand2.ResetForward() Set same to true Set finished to false while !finished operand1.GetNextItem(digit1, finished) operand2.GetNextItem(digit2, finished) if (digit1 < digit2) return LESS else if (digit1 > digit2) return GREATER return EQUAL
The algorithm for operator== is very similar. If the signs are not the same, it returns false. If the signs are the same, it calls CompareDigits.
operator==(second)
if (sign is MINUS AND second.sign is PLUS) OR (sign is PLUS AND second.sign is MINUS) return false else return (CompareDigits(number, second.number) == EQUAL)
Other Operations We have now examined all of the algorithms for the linked long integer representation except for Write and InsertDigit and the class constructors and destructor. Before we look at which implicit operations we need, we should examine the relationship between the classes LargeInt and SpecializedList. The only data member in LargeInt that contains dynamic pointers is number, which is of type SpecializedList. Because SpecializedList has a destructor, we do not need one for LargeInt. For the same reason, we do not need a class copy constructor. We can delete these constructors from our preliminary class definition, but we should retain the default class constructor to set the object to 0. Figure 6.24 shows our final objects and their interactions.
The following code shows the revised class definition, the complete addition operation, and the "less than" operator. We have implemented the changes that were made in the algorithm discussions. We leave the completion of the other operations as a programming assignment.
#include "SpecializedList.h" // Gain access to SpecializedList #include <fstream> enum SignType {PLUS. MINUS}; class LargeInt { public: LargeInt() ; bool operator<(LargeInt second); bool operator==(LargeInt second); LargeInt operator+(LargeInt second); LargeInt operator(LargeInt second); void IneertDigit(int); void Write(std::ofstream&); private: SpecializedList number; SignType sign; int numDigits; }; void Add(SpecializedList first, SpecializedList second. SpecializedList& result) // Post: result = first + second. { int carry = 0; bool finished1 = false; bool finished2 = false; int temp; int digit1; int digit2; first.ResetBackward(); second.ResetBackward(); while ( !finished1 && !finished2) { first.GetPriorItem(digit1, finished1); second.GetPriorItem(digit2, finished2); temp = digit1 + digit2 + carry; carry = temp / 10; result.InsertFront(temp % 10); } while ( !finished1) {// Adds remaining digits (if any) in first to the sum. first.GetPriorItem(digit1, finished1); temp = digit1 + carry; carry = temp / 10; result.InsertFront(temp % 10); } while ( !finished2) {// Adds remaining digits (if any) in second to the sum. second.GetPriorItem(digit2, finished2); temp = digit2 + carry; carry  temp / 10; result.InsertFront(temp % 10); } if (carry != 0) // Adds in carry (if any). result.InsertFront(carry); } LargeInt LargeInt::operator+(LargeInt second) // self is first operand. { SignType selfSign; SignType secondSign; LargeInt result; if (sign == second.sign) { Add(number, second.number, result.number); result.sign = sign; } else { selfSign = sign; secondSign = second.sign; sign = PLUS; second.sign = PLUS; if (*this < second) { Sub(second.number, number, result.number); result.sign = secondSign; } else if (second < *this) { Sub(number, second.number, result.number); result.sign = selfSign; } sign = selfSign; } result.numDigits = result.number.LengthIs(); return result; } enum RelationType {LESS, GREATER, EQUAL}; RelationType CompareDigits(SpecializedList first, SpecializedList second); bool LargeInt::operator<(LargeInt second) { RelationType relation: if (sign == MINUS && second.sign == PLUS) return true; else if (sign == PLUS && second.sign == MINUS) return false; else if (sign == PLUS && numDigits < second.numDigits) return true; else if (sign == PLUS && numDigits > second.numDigits) return false; else if (sign == MINUS && numDigits > second.numDigits) return true; else if (sign == MINUS && numDigits < second.numDigits) return false; else // Must compare digit by digit. { relation = CompareDigits(number, second.number); if (sign == PLUS && relation == LESS) return true; else if (sign == PLUS && relation == GREATER) return false; else if (sign == MINUS && relation == GREATER) return true; else return false; } } RelationType CompareDigits(SpecializedList first, SpecializedList second) { bool same = true; bool finished = false; int digit1; int digit2; first.ResetForward(); second.ResetForward(); while ( !finished) { first.GetNextItem(digit1. finished); second.GetNextItem(digit2, finished); if (digit1 < digit2) return LESS; if (digit1 > digit2) return GREATER; } return EQUAL; }
The object to which a member function is applied can reference its data members directly. On some occasions, an object needs to refer to itself as a whole, not just to its data members. An example occurs in the code for overloading the plus operator. Within this function, we have to determine whether self is less than the other operand. Here is that segment of the algorithm:
if self < second Sub(second.number, number, result.number) Set result.sign to second.sign
We need to apply the relational operator "less than" to two LargeInt objects from within a member function. How do we reference self? C++ has a hidden pointer called this. When a class member function is invoked, this points to the object to which the function is applied. The this pointer is available for use by the programmer. The algorithm segment shown here can be implemented by substituting *this for self.
secondSign = second.sign; sign = PLUS; second.sign = PLUS; if (*this < second) { Sub(second.number, number, result.number); result.sign = secondSign; }
Look at the layers of abstraction represented in this Case Study. The application programmer uses the class LargeInt to define and manipulate very large integers in an application program. The LargeInt programmer uses SpecializedList to define and manipulate large integers represented as a linked list of digits. The SpecializedList programmer creates a utility that inserts items of type int into a circular, doubly linked list and traverses the list in either direction.
Test Plan Each LargeInt operation must be unit tested. The complexity of the code for each operation is evident in the number of if statements found in the algorithms. The more complex the code, the more test cases are necessary to test it. A whitebox testing strategy would require going through the code of each operation and identifying data to test at least all branches. A blackbox testing strategy would involve choosing data that test the various possible inputs. It would require varying combinations of signs and relative relationships between operands. In the case of "less than," addition, and subtraction, the examples used in the discussion would serve as test data for those operations. Other end cases should be included as well, such as cases where one or both of the operands are zero.
Of course, this discussion presupposes that SpecializedList has been thoroughly tested!
< Free Open Study > 
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) 