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
Five huge integers

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.

Press + to interact
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:

The pictorial (logical and physical) representation of the huge integer object
The pictorial (logical and physical) representation of the huge integer object

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
A demo of huge integers

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.

Press + to interact
// Input stream
HugeInt(ifstream& Rdr);
// Output the numbers
friend 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.

Press + to interact
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:

Press + to interact
HugeInt operator+(const HugeInt& I2)const; // H1 + H2
const HugeInt& operator+=(const HugeInt& I2); // H1 += H2
HugeInt operator-(const HugeInt& I2)const; // H1 - H2
HugeInt operator-=(const HugeInt& b); // H1-= H2
HugeInt 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.

Press + to interact
HugeInt operator++(int b); // H1++
HugeInt operator++(); // ++H1
HugeInt 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.

Press + to interact
bool operator<(const HugeInt& I2)const; // H1< H2
bool operator<=(const HugeInt& I2)const; // H1<=H2
bool operator>(const HugeInt& I2)const; // H1> H2
bool operator>=(const HugeInt& I2)const; // H1>=H2
bool 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.

Press + to interact
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);