Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

Attempting to automate basic mathematical operations (e.g., addition) for intege

ID: 3703579 • Letter: A

Question

Attempting to automate basic mathematical operations (e.g., addition) for integers is problematic when the integers involved have many digits, because the required numbers may not fit in the representational space available for data of type int or long. One solution to this problem is to represent large integers using a list data structure such that each node of a list corresponds to a single digit in some corresponding integer. This exercise asks you to develop a program (using linked lists) that is capable of computing a + b for any positive integers a and b. In particular, use the LList class as the foundation for your program (but make no changes to it). Your objective is to provide the ability to add two user specified integers of arbitrary length and return the result to the screen. You will use three lists for this purpose: two to hold the digits for the two addends and one to hold the digits of the sum. Although the user will input the two addends as strings, the objects that go into your list should be Integer objects (not ints!), one for each digit. Use the appropriate methods from the Integer class to create the objects and to convert them back to ints for processing. Permit the user to compute as many sums as desired without having to restart the program each time. Exit on a negative entry for either addend.

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;
struct node {
int dt;
struct node* next;
struct node* prev;
node(int);
};
node::node(int val)
{
dt = val;
next = prev = NULL;
}

class LargeInt {
public:
LargeInt();
~LargeInt();
void insertfrnt(int);
void insertend(int);
void disp();
int length();
void add(LargeInt*, LargeInt*);
void mul(LargeInt*, LargeInt*);
void dif(LargeInt*, LargeInt*);
void quo(LargeInt*, LargeInt*);
int cmp(LargeInt*, LargeInt*);
node* hd;
node* tl;
int sz;
};

LargeInt::LargeInt()
{
hd = tl = NULL;
sz = 0;
}
void LargeInt::insertfrnt(int value)
{
node* tem = new node(value);

if (hd == NULL)
hd = tl = tem;
else {
hd->prev = tem;
tem->next = hd;
hd = tem;
}
sz++;
}
void LargeInt::insertend(int value)
{
node* tem = new node(value);

if (tl == NULL)
hd = tl = tem;
else {
tl->next = tem;
tem->prev = tl;
tl = tem;
}
sz++;
}

void LargeInt::dif(LargeInt* a, LargeInt* b)
{
int c = 0, s;
LargeInt* a1 = new LargeInt(*a);
LargeInt* b1 = new LargeInt(*b);

this->hd = NULL;
this->tl = NULL;
this->sz = 0;

while (a1->tl != NULL || b1->tl != NULL) {
if (a1->tl != NULL && b1->tl != NULL) {
if ((a1->tl->dt) + c >= (b1->tl->dt)) {
s = ((a1->tl->dt) + c - (b1->tl->dt));
c = 0;
}
else {
s = ((a1->tl->dt) + c + 10 - (b1->tl->dt));
c = -1;
}
a1->tl = a1->tl->prev;
b1->tl = b1->tl->prev;
}
else if (a1->tl != NULL && b1->tl == NULL) {
if (a1->tl->dt >= 1) {
s = ((a1->tl->dt) + c);
c = 0;
}
else {
if (c != 0) {
s = ((a1->tl->dt) + 10 + c);
c = -1;
}
else
s = a1->tl->dt;
}
a1->tl = a1->tl->prev;
}
insertfrnt(s);
}
}

void LargeInt::disp()
{
node* tem = hd;

while (tem != NULL) {
cout << tem->dt;
tem = tem->next;
}
}

int LargeInt::length()
{
return sz;
}

void LargeInt::add(LargeInt* a, LargeInt* b)
{
int c = 0, s;
LargeInt* a1 = new LargeInt(*a);
LargeInt* b1 = new LargeInt(*b);


this->hd = NULL;
this->tl = NULL;
this->sz = 0;

while (a1->tl != NULL || b1->tl != NULL) {
if (a1->tl != NULL && b1->tl != NULL) {
s = ((a1->tl->dt) + (b1->tl->dt) + c) % 10;
c = ((a1->tl->dt) + (b1->tl->dt) + c) / 10;
a1->tl = a1->tl->prev;
b1->tl = b1->tl->prev;
}
else if (a1->tl == NULL && b1->tl != NULL) {
s = ((b1->tl->dt) + c) % 10;
c = ((b1->tl->dt) + c) / 10;
b1->tl = b1->tl->prev;
}
else if (a1->tl != NULL && b1->tl == NULL) {
s = ((a1->tl->dt) + c) % 10;
c = ((a1->tl->dt) + c) / 10;
a1->tl = a1->tl->prev;
}


insertfrnt(s);
}


if (c != 0)
insertfrnt(c);
}


int LargeInt::cmp(LargeInt* a, LargeInt* b)
{
if (a->sz != b->sz)
return ((a->sz > b->sz) ? 1 : 0);
else {
LargeInt* a1 = new LargeInt(*a);
LargeInt* b1 = new LargeInt(*b);
while (a1->hd != NULL && b1->hd != NULL) {
if (a1->hd->dt > b1->hd->dt)
return 1;
else if (a1->hd->dt < b1->hd->dt)
return 0;
else {
a1->hd = a1->hd->next;
b1->hd = b1->hd->next;
}
}
return 2;
}
}

void LargeInt::quo(LargeInt* a, LargeInt* b)
{
LargeInt* a1 = new LargeInt(*a);
LargeInt* b1 = new LargeInt(*b);
LargeInt* ex = new LargeInt();
LargeInt* mp = new LargeInt();
LargeInt* pr = new LargeInt();
int i = 0;
for (i = 0; i < b1->sz; i++) {
ex->insertend(a1->hd->dt);
a1->hd = a1->hd->next;
}

for (i = 0; i < 10; i++) {
LargeInt* b2 = new LargeInt(*b);
mp->insertend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;
}

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

mp->insertend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);
insertend(i - 1);
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

while (a1->hd != NULL) {
ex->insertend(a1->hd->dt);
while (ex->hd->dt == 0) {
ex->hd = ex->hd->next;
ex->sz--;
}
for (i = 0; i < 10; i++) {
LargeInt* b2 = new LargeInt(*b);
mp->insertend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;
}

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

mp->insertend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);

insertend(i - 1);

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

a1->hd = a1->hd->next;
}

cout << endl
<< " Modulus :" << endl;
ex->disp();
}

void LargeInt::mul(LargeInt* a, LargeInt* b)
{
int k = 0, i;
LargeInt* tpr = new LargeInt();
while (b->tl != NULL) {
int c = 0, s = 0;
LargeInt* tem = new LargeInt(*a);
LargeInt* pr = new LargeInt();
while (tem->tl != NULL) {
s = ((tem->tl->dt) * (b->tl->dt) + c) % 10;
c = ((tem->tl->dt) * (b->tl->dt) + c) / 10;
pr->insertfrnt(s);
tem->tl = tem->tl->prev;
}
if (c != 0)
pr->insertfrnt(c);

for (i = 0; i < k; i++)
pr->insertend(0);

add(this, pr);
k++;
b->tl = b->tl->prev;
pr->hd = pr->tl = NULL;
pr->sz = 0;
}
}

#include <bits/stdc++.h>
using namespace std;

struct Node
{

int dt;


struct Node* next;
struct Node* prev;
Node(int);
};

Node::Node(int val)
{
dt = val;
next = prev = NULL;
}

class LargeIntLL
{
public:
LargeIntLL();
~LargeIntLL();


void insertfrnt(int);

void insertend(int);

void disp();

int length();
void add(LargeIntLL*, LargeIntLL*);
void mul(LargeIntLL*, LargeIntLL*);
void dif(LargeIntLL*, LargeIntLL*);
void quo(LargeIntLL*, LargeIntLL*);
int cmp(LargeIntLL*, LargeIntLL*);
Node* hd;
Node* tl;
int sz;
};

LargeIntLL::LargeIntLL()
{
hd = tl = NULL;
sz = 0;
}

void LargeIntLL::insertfrnt(int value)
{
Node* tem = new Node(value);

if (hd == NULL)
hd = tl = tem;
else
{
hd->prev = tem;
tem->next = hd;
hd = tem;
}
sz++;
}

void LargeIntLL::insertend(int value)
{
Node* tem = new Node(value);

if (tl == NULL)
hd = tl = tem;
else
{
tl->next = tem;
tem->prev = tl;
tl = tem;
}
sz++;
}

void LargeIntLL::disp()
{
Node* tem = hd;

while (tem != NULL)
{
cout << tem->dt;
tem = tem->next;
}
}

int LargeIntLL::length()
{
return sz;
}

void LargeIntLL::add(LargeIntLL* a, LargeIntLL* b)
{
int c = 0, s;
LargeIntLL* a1 = new LargeIntLL(*a);
LargeIntLL* b1 = new LargeIntLL(*b);

  
this->hd = NULL;
this->tl = NULL;
this->sz = 0;

while (a1->tl != NULL || b1->tl != NULL)
{
if (a1->tl != NULL && b1->tl != NULL)
{
s = ((a1->tl->dt) + (b1->tl->dt) + c) % 10;
c = ((a1->tl->dt) + (b1->tl->dt) + c) / 10;
a1->tl = a1->tl->prev;
b1->tl = b1->tl->prev;
}
else if (a1->tl == NULL && b1->tl != NULL)
{
s = ((b1->tl->dt) + c) % 10;
c = ((b1->tl->dt) + c) / 10;
b1->tl = b1->tl->prev;
}
else if (a1->tl != NULL && b1->tl == NULL)
{
s = ((a1->tl->dt) + c) % 10;
c = ((a1->tl->dt) + c) / 10;
a1->tl = a1->tl->prev;
}

  
insertfrnt(s);
}

if (c != 0)
insertfrnt(c);
}

void LargeIntLL::dif(LargeIntLL* a, LargeIntLL* b)
{
int c = 0, s;
LargeIntLL* a1 = new LargeIntLL(*a);
LargeIntLL* b1 = new LargeIntLL(*b);

this->hd = NULL;
this->tl = NULL;
this->sz = 0;

while (a1->tl != NULL || b1->tl != NULL)
{
if (a1->tl != NULL && b1->tl != NULL)
{
if ((a1->tl->dt) + c >= (b1->tl->dt))
{
s = ((a1->tl->dt) + c - (b1->tl->dt));
c = 0;
}
else
{
s = ((a1->tl->dt) + c + 10 - (b1->tl->dt));
c = -1;
}
a1->tl = a1->tl->prev;
b1->tl = b1->tl->prev;
}
else if (a1->tl != NULL && b1->tl == NULL)
{
if (a1->tl->dt >= 1)
{
s = ((a1->tl->dt) + c);
c = 0;
}
else
{
if (c != 0)
{
s = ((a1->tl->dt) + 10 + c);
c = -1;
}
else
s = a1->tl->dt;
}
a1->tl = a1->tl->prev;
}
insertfrnt(s);
}
}

int LargeIntLL::cmp(LargeIntLL* a, LargeIntLL* b)
{
if (a->sz != b->sz)
return ((a->sz > b->sz) ? 1 : 0);

LargeIntLL* a1 = new LargeIntLL(*a);
LargeIntLL* b1 = new LargeIntLL(*b);
while (a1->hd != NULL && b1->hd != NULL)
{
if (a1->hd->dt > b1->hd->dt)
return 1;
else if (a1->hd->dt < b1->hd->dt)
return 0;
else
{
a1->hd = a1->hd->next;
b1->hd = b1->hd->next;
}
}
return 2;
}

void LargeIntLL::quo(LargeIntLL* a, LargeIntLL* b)
{
LargeIntLL* a1 = new LargeIntLL(*a);
LargeIntLL* b1 = new LargeIntLL(*b);
LargeIntLL* ex = new LargeIntLL();
LargeIntLL* mp = new LargeIntLL();
LargeIntLL* pr = new LargeIntLL();
int i = 0;
for (i = 0; i < b1->sz; i++)
{
ex->insertend(a1->hd->dt);
a1->hd = a1->hd->next;
}

for (i = 0; i < 10; i++)
{
LargeIntLL* b2 = new LargeIntLL(*b);
mp->insertend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;
}

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

mp->insertend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);
insertend(i - 1);
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

while (a1->hd != NULL)
{
ex->insertend(a1->hd->dt);
while (ex->hd->dt == 0)
{
ex->hd = ex->hd->next;
ex->sz--;
}
for (i = 0; i < 10; i++)
{
LargeIntLL* b2 = new LargeIntLL(*b);
mp->insertend(i);
pr->mul(b2, mp);
if (!cmp(ex, pr))
break;
mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;
}

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

mp->insertend(i - 1);
pr->mul(b1, mp);
ex->dif(ex, pr);

insertend(i - 1);

mp->hd = mp->tl = NULL;
pr->hd = pr->tl = NULL;
mp->sz = pr->sz = 0;

a1->hd = a1->hd->next;
}

cout << endl
<< " Modulus :" << endl;
ex->disp();
}

void LargeIntLL::mul(LargeIntLL* a, LargeIntLL* b)
{
int k = 0, i;
LargeIntLL* tpr = new LargeIntLL();
while (b->tl != NULL)
{
int c = 0, s = 0;
LargeIntLL* tem = new LargeIntLL(*a);
LargeIntLL* pr = new LargeIntLL();
while (tem->tl != NULL)
{
s = ((tem->tl->dt) * (b->tl->dt) + c) % 10;
c = ((tem->tl->dt) * (b->tl->dt) + c) / 10;
pr->insertfrnt(s);
tem->tl = tem->tl->prev;
}
if (c != 0)
pr->insertfrnt(c);

for (i = 0; i < k; i++)
pr->insertend(0);

add(this, pr);
k++;
b->tl = b->tl->prev;
pr->hd = pr->tl = NULL;
pr->sz = 0;
}
}

int main()
{
LargeIntLL* m = new LargeIntLL();
LargeIntLL* n = new LargeIntLL();
LargeIntLL* s = new LargeIntLL();
LargeIntLL* p = new LargeIntLL();
LargeIntLL* d = new LargeIntLL();
LargeIntLL* q = new LargeIntLL();

string s1 = "12345678912345678912345678"
"9123456789123456789123456789";
string s2 = "45678913456789123456789123456"
"789123456789123456789";

for (int i = 0; i < s1.length(); i++)
m->insertend(s1.at(i) - '0');

for (int i = 0; i < s2.length(); i++)
n->insertend(s2.at(i) - '0');

  
LargeIntLL* m1 = new LargeIntLL(*m);
LargeIntLL* n1 = new LargeIntLL(*n);
LargeIntLL* m2 = new LargeIntLL(*m);
LargeIntLL* n2 = new LargeIntLL(*n);
LargeIntLL* m3 = new LargeIntLL(*m);
LargeIntLL* n3 = new LargeIntLL(*n);

cout << "prduct :" << endl;
s->mul(m, n);
s->disp();
cout << endl;

cout << "Sum :" << endl;
p->add(m1, n1);
p->disp();
cout << endl;

cout << "Difference (m-n) : m>n:" << endl;

d->dif(m2, n2);
d->disp();
q->quo(m3, n3);
cout << endl;

cout << "Quotient :" << endl;
q->disp();
return 0;
}

Related Questions

Attached is the Question. Please help, worth a lot of points! Suppose x(t) repre
Question #2983945
Attached is the code used for case Study Exercise 8.1 and an example output of t
Question #3698156
Attached is the picture of the essential components of a Mass Spectrometer. Samp
Question #1341203
Attached is the picture of the essential components of a Mass Spectrometer. Samp
Question #1361419
Attached is the problem, please show step by step work with formula and some exp
Question #2108784
Attached is the sensitivity report for the loan portfolio problem. Looking at th
Question #3239450
Attached is the sensitivity report for the loan portfolio problem. Looking at th
Question #3254169
Attached is the sensitivity report for the loan portfolio problem. Why do none o
Question #421450

Navigate

Previous
Attempted this but stuck on the missing boxes. EXAMPLE 3 Sketch the graph of f(x
Next
Attempting to make a bank account program. Here is the beginning of the program

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