Problem: “Big” Integer Arithmetic This problem asks you to create a custom data
ID: 3835054 • Letter: P
Question
Problem: “Big” Integer Arithmetic
This problem asks you to create a custom data type to handle large integer arithmetic, by creating a custom C++ class called BigInt. C++ has a number of types to handle integer data, including ints, short ints and long ints, and their signed and unsigned variants. However, the maximum positive number that one can store in the largest of these, which is an unsigned long int, is 18,446,744,073,709,551,615. This number, as you can see, has 20 digits. In many scientific and engineering applications, this does not suffice to hold values required for complex computations. Anything about 1020 would be too big to hold in the unsigned long int type. So your task in this assignment is to create a C++ class called BigInt which will allow basic arithmetic operations on positive integer values of up to 300 digits, storing integers from 0 to 9999 ...9 (300 9s). The three operations you have to do are addition, subtraction and multiplication. Specific tasks are these:
1. Add two BigInt objects, and store the result in another BigInt, using the + operator.
2. Add an int to a BigInt object, and store the result in another BigInt, also using the +operator.
3. Subtract one BigInt object from another, and store the result in another BigInt, using the –operator. The second BigInt can always be smaller or equal to the first BigInt. In other words, the results shall never be negative.
4. Subtract an int from a BigInt object, and store the result in another BigInt, also using the –operator. Should be obvious in this case that the results shall never be negative.
5. Multiply two BigInt objects, and store the result in another BigInt, using the * operator. The resulting BigInt shall not exceed 300 digits.
6. Multiply a BigInt object with an int, and store the result in another BigInt, using the * operator. Again, the resulting BigInt shall not exceed 300 digits.
7. Overload the >> and << operators to input and output BigInt objects to streams, respectively. Of course, they have to be overloaded as friend functions.
To start, here’s a bare skeleton of the BigInt class. You are welcome to start with this, but do not have to. As a hint, you have to remember your basic school-level arithmetic, and implement this in a C++ class to solve this problem.
// Complete this below
class BigInt {
private:
int digits[300];
...
public:
BigInt();
BigInt( string value );
...
BigInt operator+(BigInt b);
BigInt operator-(BigInt b);
BigInt operator*(BigInt b);
friend ostream& operator<<(ostream &os, BigInt b);
...
};
The program will run as follows:
1. Ask the user to input two BigInts.
2. Output the results of addition, subtraction, and multiplication of these two BigInts
3. Then, ask the user to input a BigInt and an integers
4. Output the results of addition, subtraction, and multiplication of the BigInt and int
See the example output below.
Example (user input is bold):
Enter the first BigInt:
222222222222222222222222222222
Enter the second BigInt:
111111111111111111111111111111
Adding: 333333333333333333333333333333
Subtracting: 111111111111111111111111111111
Multiplying: 24691358024691358024691358024641975308641975308641975308642
------------
Enter a BigInt:
222222222222222222222222222222
Enter an int: 4
Adding: 222222222222222222222222222226
Subtracting: 222222222222222222222222222218
Multiplying: 888888888888888888888888888888
For this problem, you have to create three files: one HPP file containing the BigInt class declaration, a CPP file containing the BigInt class definition, and a driver file that implements the program.
Explanation / Answer
bigint arithmetic operations in c++
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
using namespace std;
#define MAX 20 // Max. number of buckets. Default 20 buckets (max 20*9 digits).
#define BUCKET_LIMIT 1000000000 // 999999999 is the highest possible number in a single bucket
#define BUCKET_NUM_DIGITS 9 // Max. number of digits of in one bucket
class BigInt {
private:
long long content[MAX]; // Buckets holding actual number
short sign; // -1/0/1; depending on number being negetive, zero r positive respectively
unsigned short length; // Number of buckets actually utilized to hold the number
void addLSBucket(int); // Add Least Significant Buckets: Internally used in multiplication operation
public:
// Constructors
BigInt ();
BigInt (long long);
BigInt (string);
BigInt (const BigInt &n);
// Assignment Operators
BigInt operator = (BigInt);
BigInt operator = (long long); // TODO
// Comparison operators
bool operator == (BigInt);
bool operator == (long long); // TODO
bool operator != (BigInt);
bool operator != (int); // TODO
bool operator < (BigInt);
bool operator < (int); // TODO
bool operator <= (BigInt);
bool operator <= (int); // TODO
bool operator > (BigInt);
bool operator > (int); // TODO
bool operator >= (BigInt);
bool operator >= (int); // TODO
// Arithmetic operators
BigInt operator + (long long);
BigInt operator + (BigInt);
BigInt operator - (long long);
BigInt operator - (BigInt);
BigInt operator * (long long);
BigInt operator * (BigInt);
BigInt operator / (long long); // TODO
BigInt operator / (BigInt); // TODO
BigInt operator % (long long); // TODO
BigInt operator % (BigInt); // TODO
// Methods
string toString(void); // Serializes BigInt object
void debug(void);
};
BigInt :: BigInt () {
length = 0;
sign = 0;
memset(content, 0, sizeof(content));
}
BigInt :: BigInt (long long n) {
length = 0;
if (n == 0) {
sign = 0;
}
else {
sign = (n > 0) ? 1 : -1;
if (n < 0) n = 0 - n; // Removing minus sign
for (int i = 0; n > 0; n /= BUCKET_LIMIT) {
length ++;
content[i ++] = n % BUCKET_LIMIT;
}
}
memset(content + length, 0, (MAX - length) * sizeof(long long));
}
BigInt :: BigInt (string n) {
length = 0;
if (n[0] == '0') {
sign = 0;
memset(content, 0, sizeof(content));
}
else {
int i, posFirstDigit;
stringstream s;
if (n[0] == '-') {
sign = -1;
posFirstDigit = 1;
}
else {
sign = 1;
posFirstDigit = 0;
}
for (i = n.size() - BUCKET_NUM_DIGITS; i >= posFirstDigit; i -= 9) {
s << n.substr(i, BUCKET_NUM_DIGITS);
s >> content[length ++];
s.clear();
}
if (i < posFirstDigit) {
s << n.substr(posFirstDigit, BUCKET_NUM_DIGITS - posFirstDigit + i);
s >> content[length ++];
}
memset(content + length, 0, (MAX - length) * sizeof(long long));
}
}
BigInt :: BigInt (const BigInt &n) {
length = n.length;
sign = n.sign;
memcpy(content, n.content, MAX * sizeof(long long));
}
/**
* BigInt::addLSBucket shifts the contents of BigInt::content array by numBucketsToBeAdded
* places. This is needed while computing the product of two BigInt instances.
* In case of multiplication of two integers:
* 6374 * 23 is computed as 6374 * 3 + 6374 * 2 * 10
* Multiplication by 10 just shifts the content. Same purpose is served by BigInt::addLSBucket
* in our context.
*/
void BigInt :: addLSBucket (int numBucketsToBeAdded) {
if (length + numBucketsToBeAdded > MAX) return;
for (int i = length + numBucketsToBeAdded -1; i >= 0; i --) {
content[i] = (i > numBucketsToBeAdded - 1) ? content[i - numBucketsToBeAdded] : 0;
}
length += numBucketsToBeAdded;
}
string BigInt :: toString(void) {
if (length == 0) return "0";
stringstream s;
if (sign == -1) s << "-";
s << content[length - 1];
for (int i = length - 2; i >= 0; i --) {
if (content[i] < 10) {
s << "00000000" << content[i];
}
else if (content[i] < 100) {
s << "0000000" << content[i];
}
else if (content[i] < 1000) {
s << "000000" << content[i];
}
else if (content[i] < 10000) {
s << "00000" << content[i];
}
else if (content[i] < 100000) {
s << "0000" << content[i];
}
else if (content[i] < 1000000) {
s << "000" << content[i];
}
else if (content[i] < 10000000) {
s << "00" << content[i];
}
else if (content[i] < 100000000) {
s << "0" << content[i];
}
else {
s << content[i];
}
}
return s.str();
}
BigInt BigInt :: operator = (BigInt n) {
sign = n.sign;
length = n.length;
memcpy(content, n.content, sizeof(content));
}
bool BigInt :: operator == (BigInt n) {
if (sign != n.sign) {
return false;
}
else if (length != n.length) {
return false;
}
else {
for (int i = 0; i < length; i ++) {
if (content[i] != n.content[i]) return false;
}
return true;
}
}
bool BigInt :: operator != (BigInt n) {
return !operator == (n);
}
bool BigInt :: operator < (BigInt n) {
if (sign < n.sign) {
return true;
}
else if (sign > n.sign) {
return false;
}
else if (sign == 0) {
return false;
}
else if (sign == 1 && length < n.length) {
return true;
}
else if (sign == 1 && length > n.length) {
return false;
}
else if (sign == 1 && length == n.length) {
for (int i = 0; i < length; i ++) {
if (content[i] < n.content[i]) {
return true;
}
else if (content[i] > n.content[i]) {
return false;
}
}
return false;
}
else if (sign == -1 && length < n.length) {
return false;
}
else if (sign == -1 && length > n.length) {
return true;
}
else if (sign == -1 && length == n.length) {
for (int i = 0; i < length; i ++) {
if (content[i] < n.content[i]) {
return false;
}
else if (content[i] > n.content[i]) {
return true;
}
}
return false;
}
}
bool BigInt :: operator <= (BigInt n) {
return (operator < (n) || operator == (n));
}
bool BigInt :: operator > (BigInt n) {
return !operator <= (n);
}
bool BigInt :: operator >= (BigInt n) {
return !operator < (n);
}
BigInt BigInt :: operator + (BigInt n) {
if (length == 0) {
return n;
}
else if (n.length == 0) {
BigInt num(*this);
return num;
}
else if (sign == n.sign) {
BigInt num;
num.length = (length > n.length) ? length : n.length;
num.sign = sign;
long long bucketSum, carry = 0;
for (int i = 0; i < num.length; i ++) {
bucketSum = content[i] + n.content[i] + carry;
num.content[i] = bucketSum % BUCKET_LIMIT;
carry = bucketSum / BUCKET_LIMIT;
}
if (carry > 0) {
num.content[length ++] = carry;
}
return num;
}
else {
BigInt num;
if (sign == -1) {
num = (*this);
num.sign = 1;
return n - num;
}
else {
num = n;
num.sign = 1;
return (*this) - num;
}
}
}
BigInt BigInt :: operator + (long long n) {
return (*this) + BigInt(n);
}
BigInt BigInt :: operator - (BigInt n) {
if (sign == n.sign) {
bool hasZeroValue = true;
if (length == 0) {
BigInt subtrahend(n);
subtrahend.sign *= -1;
}
else if (n.length == 0) {
BigInt num(*this);
return num;
}
if (*this > n) {
BigInt minuend(*this);
for (int i = 0; i < minuend.length; i ++) {
if (minuend.content[i] >= n.content[i]) {
minuend.content[i] -= n.content[i];
}
else {
minuend.content[i] = 10 * minuend.content[i] - n.content[i];
minuend.content[i + 1] --;
}
if (hasZeroValue && minuend.content[i] != 0) hasZeroValue = false;
}
return hasZeroValue ? BigInt(0) : minuend;
}
else {
BigInt minuend(n);
for (int i = 0; i < minuend.length; i ++) {
if (minuend.content[i] >= content[i]) {
minuend.content[i] -= content[i];
}
else {
minuend.content[i] = 10 * n.content[i] - content[i];
minuend.content[i + 1] --;
}
if (hasZeroValue && minuend.content[i] != 0) hasZeroValue = false;
}
if (hasZeroValue) {
return BigInt(0);
}
else {
minuend.sign *= -1;
return minuend;
}
}
}
else {
BigInt subtrahend(n);
if (n.sign = -1) {
subtrahend.sign = 1;
}
else {
subtrahend.sign = -1;
}
return operator + (subtrahend);
}
}
BigInt BigInt :: operator - (long long n) {
return (*this) - BigInt(n);
}
BigInt BigInt :: operator * (long long n) {
if (n == 0 || length == 0) return BigInt(0);
long long carry = 0, tempProduct;
BigInt num(*this);
num.sign = ((n > 0 && sign == 1) || (n < 0 && sign == -1)) ? 1 : -1;
if (n < 0) n *= -1;
for (int i = 0; i < length; i ++) {
tempProduct = num.content[i] * n;
num.content[i] = (tempProduct + carry) % BUCKET_LIMIT;
carry = (tempProduct + carry) / BUCKET_LIMIT;
}
if (carry > 0) num.content[num.length ++] = carry;
return num;
}
BigInt BigInt :: operator * (BigInt n) {
BigInt rs, temp;
rs = n * content[0];
for (int i = 1; i < length; i ++) {
temp = n * content[i];
temp.addLSBucket(i);
rs = rs + temp;
}
rs.sign = (sign == n.sign) ? 1 : -1;
return rs;
}
void BigInt :: debug (void) {
cout << endl << "--------------------------------------------------" << endl;
cout << "In debug mode" << endl;
cout << "Number: " << toString() << endl;
cout << "Sign: " << sign << " Length: " << length << endl;
cout << "Content: ";
for (int i = 0; i < MAX; i ++) {
cout << content[i] << " ";
}
cout << endl << "--------------------------------------------------" << endl;
}
int main ()
{
BigInt a("9999999999123456789123456"), b("12345678912"), c;
cout << (a - 12345678912).toString() << endl;
c = a + b;
cout << a.toString() + " + " + b.toString() + " = " + c.toString() << endl;
c = a - b;
cout << a.toString() + " - " + b.toString() + " = " + c.toString() << endl;
c = a * b;
cout << a.toString() + " * " + b.toString() + " = " + c.toString() << endl;
if (a == b) {
cout << a.toString() + " is equal to " + b.toString() << endl;
}
else {
cout << a.toString() + " is not equal to " + b.toString() << endl;
}
if (a > b) {
cout << a.toString() + " is greater than " + b.toString() << endl;
}
else {
cout << a.toString() + " is not greater than " + b.toString() << endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.