Abstract Data Type
Learn about the abstract huge integer data type.
Let’s explore the abstract data type (ADT) for storing huge integers. Here are some examples of huge integers of various lengths:
-100385934890589348509834895+20034985348598394850983498598348598349850834-27374759690493727283939222737475969049372728393922332957273757217+3329593827228272737572172737475969049372728393922-300
To effectively store such huge integers, we require three fundamental elements: the sign of the number, the number of digits, and a dynamic array (a pointer that points to a heap array holding its individual digits).
Let’s discuss how we can implement this ADT in C++.
The HugeInt class structure
This class structure includes private members for the sign (isNeg ), size (size), and array of digits (Ds). Along with this, we add a basic constructor for initializing the huge integer.
class HugeInt{bool isNeg;int size;int *Ds;public:HugeInt(string s); // Constructor to initialize digits and sign};
Before we delve into the implementation of HugeInt.cpp, let’s first grasp the logical and physical representation of how a huge integer will be stored, taking into consideration stack and heap segments.
Pictorial representation of a huge integer object
Take a moment to examine the pictorial representation below of a huge integer object, where the object is declared within the stack at a local level, the digits array is a dynamic memory (residing in the heap), and Ds points toward it:
Deeper view of huge integer ADT
Let’s delve deeper into the ADT and identify the necessary functions to enhance our huge integer class, enabling the demonstration outlined below. The demo involves processing a set of huge integers, as specified in the HIs.txt file, which initially indicates the number of huge integers to process, followed by their respective numerical values.
5 12 200 2 999999999999999999999999999999 -61969987109750917095790
Input and output functions
We’ll add the constructor that initializes the object from an input stream (ifstream) and overloads the output stream operator (<<) to facilitate the printing of HugeInt objects in the output stream.
// Input streamHugeInt(ifstream& Rdr);// Output the numbersfriend ostream& operator<<(ostream&, const HugeInt& I);
Utility functions (arithmetic operations)
To enable arithmetic and logical operators, we’ll base our foundation on some of the helper functions. These utility functions include value-based addition and subtraction, as well as comparisons for less than, greater than, and equal to, based on value. We’ll see how these utility functions simplify our operators’ implementations. Also, we use the trim method to remove leading zeros and the overloaded subscript operators [] enable access to individual digits of HugeInt. By incorporating these helper functions, the versatility of the HugeInt class is significantly augmented, enabling the execution of diverse arithmetic and relational operations on large integers.
HugeInt quantitywiseAdd(const HugeInt& I2)const;HugeInt quantitywiseSub(const HugeInt& I2)const;bool isQuantitywiseLess(const HugeInt& I2)const;bool isQuantitywiseGreater(const HugeInt& I2)const;bool isQuantitywiseEqual(const HugeInt& I2)const;void trim();int operator[](int i)const;int& operator[](int i);
Add and subtract operator
After adding the constructors and utility functions, we’ll augment the HugeInt class with operators for addition and subtraction (as operators). These operators provide a concise and convenient way to perform arithmetic operations between HugeInt objects, just like any primitive data type. The following operators will be added to the HugeInt ADT:
HugeInt operator+(const HugeInt& I2)const; // H1 + H2const HugeInt& operator+=(const HugeInt& I2); // H1 += H2HugeInt operator-(const HugeInt& I2)const; // H1 - H2HugeInt operator-=(const HugeInt& b); // H1-= H2HugeInt operator-()const; // H1 = -H2
Unary operators
In C++ syntax, the preferred method for incrementing or decrementing a value by 1 is typically through the unary ++ or -- operators. Therefore, we’ll implement post-increment, pre-increment, post-decrement, and pre-decrement operators. These additions facilitate the seamless manipulation of HugeInt objects, offering pre- and post-increment/decrement functionality.
HugeInt operator++(int b); // H1++HugeInt operator++(); // ++H1HugeInt operator--(int b); // H1--HugeInt operator--(); // --H1
Comparison operators
In C++ syntax, using comparison operators, such as <, <=, >, >=, ==, is a straightforward way to evaluate relationships between values. We’ll incorporate these operators into our HugeInt class, allowing easy and intuitive comparisons. This integration empowers users to assess relationships between HugeInt objects effortlessly, using the standard set of comparison operators.
bool operator<(const HugeInt& I2)const; // H1< H2bool operator<=(const HugeInt& I2)const; // H1<=H2bool operator>(const HugeInt& I2)const; // H1> H2bool operator>=(const HugeInt& I2)const; // H1>=H2bool operator==(const HugeInt& I2)const; // H1==H2
Multiplication and division operators
To finalize the implementation of our HugeInt class and equip it with additional robust functionality, we’ll integrate the multiplication and division operators, i.e., *, *=, /, /=, %, %=. These operators provide essential arithmetic capabilities, allowing users to perform nontrivial operations on HugeInt objects. This comprehensive addition ensures a fully featured and versatile HugeInt class capable of handling a wide range of mathematical operations with ease.
HugeInt operator*(const HugeInt& b)const;HugeInt operator/(const HugeInt& b)const;HugeInt operator%(const HugeInt& b)const;const HugeInt& operator*=(const HugeInt& I2);const HugeInt& operator/=(const HugeInt& I2);const HugeInt& operator%=(const HugeInt& I2);