Problem: \"Big\" Integer Arithmetic This problem asks you to create a custom dat

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, respective 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

Explanation / Answer

BigInt code in c++ is given below :

#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

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.