Question

In C++ the largest int value is 2147483647. So, an integer larger than
this cannot be stored and processed as an integer. Similarly if the sum or
product of two positive integers is greater than 2147483647, the result will
be incorrect.
One way to store and manipulate large integers is to store each individual
digit of the number in an array. In this assignment, you will design a class
named LargeInteger such that an object of this class can store an integer
of any number of digits. Your abstract data type LargeInteger will support
member functions to add() two LargeInteger objects together and return
a new resulting LargeInteger object. You will only implement an unsigned
integer, we will not worry about handling negative large integers in this assignment.
Likewise, subtraction and especially multiplication are a bit more
complicated, and we will leave those operations for later. But in addition
to the add() member function, you will implement several other member
functions and constructors, that will be useful to implementing addition of
the LargeInteger values.

C++ , Please add function documentation, Use the @param tags for all parameters, and @return tag for the return value

For this assignment you need to perform the following tasks. You will be given 3 template les, and some of the LargeInteger class will already have been implemented for you (I will give you a simple constructor and the class destructor). You should implement the member functions, in this order, and uncomment the test code incrementally to test your functions as you implement them.

1. Implement a tostring() member function. This function will return a string representation of the LargeInteger. You should probably used string streams to implement this function. Note that the digits of the large integer are stored in reverse of their display order, e.g. the 1's place (100 ) is in index 0 of digits, the 10's place (101 ) is in index 1, etc.

2. Implement a second constructor for the LargeInteger. This constructor will be used to construct a large integer from an array of digits. This constructor takes an int, which is the size of the array of digits, and an integer array as the second parameter. You will need to dynamically allocate the space for the digitis in your constructor (see the given constructor for an example).

3. Implement a member function named maxDigits(). This function will take a reference to a LargeInteger as its only parameter. This function should return the number of digits in the larger LargeInteger comparing the passed in object to this object.

4. Implement a member function named digitAtPlace(). This function returns the digit of this large integer object at a particular digit index. So this function takes an integer index as its input parameter, and returns an integer as its result. Again, if you ask for the digitAtPlace() index 0, this should return the 1's place 100 digit of the integer. If asked for the digit at place 1, this should return the 10's place 101 digit. If you ask for a digit place that is larger than the number of digits in the integer the member function should return 0. For example, if the integer represents 345, and you ask for the digit at place 3, then the function will return a 0. Likewise, if a negative index is given to this function, it should also return 0.

5. Implement a member function named appendDigit(). This functions takes an int digit as its only parameter. This will be a void function as it does not return any value result from calling it. The function is not something a normal user of the LargeInteger type is likely to need to do to an integer, but it will be very useful for our add function. This function appends the digit to become the new most signicant digit of the LargeInteger object. For example, if the large integer object represents the value 345 and we ask it to appendDigit(7), then the new value of the object will be 7345. This function needs to manage memory to perform its task. You need to perform the following steps 1) allocate a new array of digits of numDigits+1 (e.g. enough space to hold one more digit). 2) copy the old digits to the new array of digits you created. 3) append the new passed in digit to the end of the array. Then 4) free up the old original array of digits, and make sure you class now uses the new array of allocated digits. Also, you might want to have this function ignore the append of a '0' digit (e.g. do not grow the large integer if trying to append a 0, as this does not need to be represented by the LargeInteger).

6. And nally, implement the add() member function. This function takes a reference to another LargeInteger object, and adds the digits of the other object to this object together.

Lets discuss the algorithm for the add() member function in more detail. This function will simply take a reference parameter of type LargeInteger as its one and only parameter. You need to perform the following steps in your add() member function:

1. Dynamically allocate a new array to hold the resulting sum of this and the other LargeInteger. Use the maxDigits() member function to determine the size needed for this new array. The size of the resulting sum will either be equal to the number of digits of the larger of the 2 numbers, or this value + 1 if there is a carry on the most signicat sum. We handle needing to grow the result in the last step of the algorithm. For example if this large ineteger has the value 4537 (4 digits) and the other has the value of 23 (2 digits), the result will t in 4 digits, which is what maxDigits() should return. Only if we have a carry would we need an extra digit. For example if this is 4537 and the other is 7242 the result of adding them together would be 11779, which needs 5 digits. But as mentioned, we will grow to accomodate a nal carry in the last step of the algorithm.

2. Perform the addition, from least signicant digit to most signicant digit, handling carry as needed. Use the digitAtPlace() member function here, as this will determine if each number has a digit, or will return a 0 if you are beyond the size of each number. The resulting digits should be stored in the new array you allocated in step 1. Also make sure you keep track of the carry, and at the end, you should know if a 0 or 1 was carried from the addition of the last most signicant digits.

3. Dynamically allocate a new LargeInteger() object, using the constructor you created that takes an array as its parameter. You will pass in the array of new digits you summed up in step 2 and its size that you determined and dynamically allocated in step 1.

4. If there was a carry on the last most signicant digit, use the appendDigit() member function to add the carry value as the new most signicant digit to the new LargeInteger() you created in step 3. As mentioned above, you could also just have your appendDigit() function ignore a request to append a '0' digit, thus in your add() you could always just call appendDigit() with the nal carray, and the append would append or ignore as appropriate.

5. Finally the add() function should return a reference to the new LargeInteger() that contains the calculated sum you just computed and assigned to it.

***You should add the function prototypes to the class declaration in the LargeInteger.hpp le, and implement the class member functions asked for in the LargeInteger.cpp le. You should not add any code to the assg-03.cpp le, only remove the comments to perform the tests shown on your functions.

Answer 1

// LargeInteger.hpp

#ifndef LARGEINTEGER_HPP_

#define LARGEINTEGER_HPP_

#include <iostream>

#include <string>

#include <sstream>

#include <cmath>

using namespace std;

/** LargeInteger class.

*

* @param numDigits Private member integer variable, contains the number

* of digits currently in the LargeInteger, or equivalently, the size

* of they digits array of integers.

* @param digits A dynamically allocated array of integers. This array

* holds the digits of the large integer this object represents. The

* digits in the array are orderd such that the 1's place (10^0) is in

* index 0 of the array, the 10's place (10^1) is in the index 1, and so

* on.

*/

class LargeInteger

{

private:

int numDigits; // number of digits in LargeInt / size of alloc array

int* digits; // the digits of the LargeInt we are representing

public:

       LargeInteger(int value);

       ~LargeInteger();

       LargeInteger(int size, int *digits);

       int maxDigits(LargeInteger &other);

       int digitAtPlace(int index);

       void appendDigit(int digit);

       LargeInteger& add(LargeInteger &other);

       string tostring();

};

#endif /* LARGEINTEGER_HPP_ */

//end of LargeInteger.hpp

// LargeInteger.cpp

#include "LargeInteger.hpp"

using namespace std;

/** LargeInteger constructor

* Constructor for LargeInteger class that takes a simple built-in

* integer to be used as the initial value of the large integer.

*

* @param value A regular (32-bit) integer that we will use as the

* initial value of this LargeInteger data type.

*/

LargeInteger::LargeInteger(int value)

{

       // first determine number of digits, so we know what size of array

       // to construct dynamically

       numDigits = (int) log10((double) value) + 1;

       // allocate an array of the right size

       digits = new int[numDigits];

       // iterate through the digits in value, putting them into our

       // array of digits.

       int digit;

       for (int digitIndex = 0; digitIndex < numDigits; digitIndex++)

       {

             // least significant digit

             digit = value % 10;

             digits[digitIndex] = digit;

             // integer division to chop of least significant digit

             value = value / 10;

       }

}

/** LargeInteger destructor

* Destructor for the LargeInteger class. Make sure we are good

* managers of memory by freeing up our digits when this object

* goes out of scope.

*/

LargeInteger::~LargeInteger()

{

       delete [] this->digits;

}

LargeInteger::LargeInteger(int size, int *digits)

{

       id = nextLargeIntegerId++;

       numDigits = size;

       this->digits = new int[size];

       for(int i=0;i<size;i++)

             this->digits[i] = digits[i];

}

int LargeInteger::maxDigits(LargeInteger &other)

{

       if(numDigits > other.numDigits)

             return numDigits;

       else

             return other.numDigits;

}

int LargeInteger::digitAtPlace(int index)

{

       if(index >=0 && index < numDigits)

             return digits[index];

       return 0;

}

void LargeInteger::appendDigit(int digit)

{

       if(digit != 0)

       {

             int *temp = new int[numDigits+1];

             for(int i=0;i<numDigits;i++)

                    temp[i] = digits[i];

             delete [] digits;

             temp[numDigits] = digit;

             numDigits++;

             digits = temp;

       }

}

LargeInteger& LargeInteger::add(LargeInteger &other)

{

       int carry = 0, sum;

       int i;

       LargeInteger *addInt;

       if(numDigits > other.numDigits)

       {

             addInt = new LargeInteger(this->numDigits,this->digits);

             for(i=0;i<other.numDigits;i++)

             {

                    sum = addInt->digitAtPlace(i) + other.digits[i] + carry;

                    if(sum > 9)

                    {

                           addInt->digits[i] = sum%10;

                           carry = sum/10;

                    }else

                    {

                           addInt->digits[i] = sum;

                           carry = 0;

                    }

             }

             while(carry > 0 && (i < numDigits))

             {

                    sum = addInt->digitAtPlace(i) + carry;

                    addInt->digits[i] = sum%10;

                    carry = sum/10;

                    i++;

             }

       }else

       {

             addInt = new LargeInteger(other.numDigits,other.digits);

             for( i=0;i<numDigits;i++)

             {

                    sum = addInt->digitAtPlace(i) + digits[i] + carry;

                    if(sum > 9)

                    {

                           addInt->digits[i] = sum%10;

                           carry = sum/10;

                    }else

                    {

                           addInt->digits[i] = sum;

                           carry = 0;

                    }

             }

             while(carry > 0 && (i < other.numDigits))

             {

                    sum = addInt->digitAtPlace(i) + carry;

                    addInt->digits[i] = sum%10;

                    carry = sum/10;

                    i++;

             }

       }

       addInt->appendDigit(carry);

       return *addInt;

}

string LargeInteger::tostring()

{

       string outStr = "";

       for(int i=0;i<numDigits;i++)

       {

             stringstream ss;

             ss<<digits[i];

             outStr = ss.str() + outStr;

       }

       return outStr;

}

//end of LargeInteger.cpp