Previous Section
 < Free Open Study > 
Next Section


Case 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 machine-after 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.

Click To expand
Figure 6.23: Representing large integers with linked lists

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

  1. If both operands are positive, use the addition algorithm.

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

  3. 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:

  1. A negative number is less than a positive number.

  2. If the signs are positive and one number has more digits than the other, then the number with fewer digits is the smaller value.

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

  4. 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 equal-length 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.

Click To expand
Figure 6.24: An instance of class LargeInt

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;
}

C++: Explicit Reference to Self
Start example

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;
}
End example

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 white-box testing strategy would require going through the code of each operation and identifying data to test at least all branches. A black-box 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!



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)