Multiplication with linked list hw I'm trying to finish a hw where one of the requirement is a method that takes in two linked lists, multiply them, and return the result in another list. This is my implementation so far:

longint.h:
#include <iostream>

using namespace std;

struct ListNode {
char digit;
ListNode* next;
ListNode* prev;
};

class NaturalNumber {
private:
ListNode* msd; // first
ListNode* lsd; // last
int length;

public:
NaturalNumber (int n);

NaturalNumber add (const NaturalNumber &x);
NaturalNumber mult (NaturalNumber& x);
NaturalNumber multi (const char d);

friend ostream& operator<< (ostream& outs, const NaturalNumber& x);
};

longint.cpp:

#include <iostream>
#include "longint.h"
#include <cmath>

using namespace std;

NaturalNumber::NaturalNumber (int n)
{
ListNode* p = new ListNode;
p->digit = n % 10;
p->next = NULL;
p->prev = NULL;
msd = p;
lsd = p;
length = 1;

n = n / 10;
while (n > 0)
{
ListNode* p = new ListNode;
p->digit = n%10;
p->next = msd;
p->prev = NULL;
msd->prev = p;
msd = p;
length++;
n = n / 10;
}
}

ostream& operator<< (ostream& outs, const NaturalNumber& x)
{
for (ListNode* p=x.msd; p!=NULL; p=p->next)
{
char c = p->digit + '0';
outs << c;
}

return outs;
}

NaturalNumber NaturalNumber::add (const NaturalNumber& x)
{
NaturalNumber* result = new NaturalNumber (0);
ListNode* temporary1 = lsd;
ListNode* temporary2 = x.lsd;
ListNode* p = new ListNode;
int sum;
int length_holder = x.length;

int carry = 0;
sum = temporary1->digit + temporary2->digit + carry;
p->digit = sum%10;
p->next = NULL;
p->prev = NULL;
result->msd = p;
result->lsd = p;
carry = (sum - sum%10)/10;

temporary1 = temporary1->prev;

temporary2 = temporary2->prev;

while (length != 1 && length_holder != 1)
{
ListNode* p = new ListNode;
sum = temporary1->digit + temporary2->digit + carry;

p->digit = sum%10;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;

carry = 0;
if (sum >= 10)
{
carry = (sum - sum%10)/10;
}
temporary1 = temporary1->prev;
temporary2 = temporary2->prev;
length = length-1;
length_holder = length_holder-1;
}

if (temporary1 != NULL)
{
while (length != 1)
{
ListNode* p = new ListNode;
sum = temporary1->digit + carry;
p->digit = sum%10;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;

carry = 0;
if (sum >= 10)
{
carry = (sum - sum%10)/10;
}
temporary1 = temporary1->prev;
length = length-1;
}
}

if (temporary2 != NULL)
{
while (length_holder != 1)
{
ListNode* p = new ListNode;
sum = temporary2->digit + carry;
p->digit = sum%10;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;

carry = 0;
if (sum >= 10)
{
carry = (sum - sum%10)/10;
}
temporary2 = temporary2->prev;
length_holder = length_holder-1;
}
}
if (carry !=0)
{
ListNode* p = new ListNode;
p->digit = carry;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;
}
// Your implementation here

return *result;
}

NaturalNumber NaturalNumber::multi (const char d)
{
NaturalNumber* result = new NaturalNumber (0);
ListNode* temporary = lsd;
ListNode* p = new ListNode;

int product;
int carry = 0;
product = (temporary->digit)*d + carry;

p->digit = product%10;
p->next = NULL;
p->prev = NULL;
result->msd = p;
result->lsd = p;
carry = (product - product%10) /10;

temporary = temporary->prev;
length = length-1;
while (temporary != NULL)
{
ListNode* p = new ListNode;
product = (temporary->digit)*d + carry;

p->digit = product%10;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;

carry = 0;
if (product >= 10)
{
carry = (product - product%10) /10;
}
temporary = temporary->prev;
length = length-1;
}

if (carry !=0)
{
ListNode* p = new ListNode;
p->digit = carry;
p->next = result->msd;
p->prev = NULL;
result->msd->prev = p;
result->msd = p;
}
return *result;
}

NaturalNumber NaturalNumber::mult (NaturalNumber& x)
{
NaturalNumber* result = new NaturalNumber (0);
NaturalNumber* placeholder = new NaturalNumber(0);

ListNode* p = new ListNode;
ListNode* temporary1 = lsd;
ListNode* temporary2 = x.lsd;
int length_holder = x.length;
int num_zeros = x.length;
char digit_holder;
int nums_zeros = 1;

int carry = 0;
digit_holder = temporary1->digit;

*result = x.multi(digit_holder);
temporary1 = temporary1->prev;
NaturalNumber w(*result);

while (temporary1 != NULL)
{
digit_holder = temporary1->digit;
*placeholder = x.multi(digit_holder);

for (int i = 0; i < nums_zeros; i++)
{
*placeholder = placeholder->multi(10);
}
nums_zeros = nums_zeros+1;

temporary1 = temporary1->prev;
}
// your implementation here
return *result;
}

main.cpp:
#include <iostream>
#include <string>
#include "longint.h"

using namespace std;
int main()
{
char cmd;
cout << "Available commands: a (add), m (multiply), f (factorial), and q (quit).\n";
cout << "command: ";
cin >> cmd;
while (cmd != 'q' && cmd != 'Q')
{
if (cmd == 'a' || cmd == 'A')
{
int left, right;
cout << "left operand = ";
cin >> left;
cout << "right operand = ";
cin >> right;

NaturalNumber x(left), y(right);
cout << x << " + " << y << " = " << x.add(y) << '\n';
}

else if (cmd == 'm' || cmd == 'M')
{
int left, right;
cout << "left operand = ";
cin >> left;
cout << "right operand = ";
cin >> right;

NaturalNumber x(left), y(right);
cout << x << " * " << y << " = " << x.mult(y) << '\n';
}

cout << "command: ";
cin >> cmd;
}
}

The code works fine if I call the addition method. However, whenever I call the multiplication method, it only spits back at me the last digit of the right result. After some testing and debugging, I think the problem is that when I call the add method in my multiplication method, only the last digits of my two lists are passed, not the entire list. How do I fix this? what is multiply doing again?
5*3 is
5+5+5.
multiply should just be
product = 0;
for(i = 0; i < number of times; i++) //number of times is 3
product = product+number //number is 5 here, of course

so you need to loop, calling add over and over.
your multiply is doing something weird. I can't make much sense of it.
just make product a list, and call add N times. Its that simple (assuming add works right).
Remember you have to convert N to a normal int if it is a list, or find a way to loop that many times if it a big-int (more than 64 bits or whatever). If its more than 64 bits, you are going to be waiting on your answer for a while.

it is woefully inefficient to multiply via adds this way: there are probably slick algorithms to do this with less work. But crude and simple is fine to start with.
Last edited on Are you required to use a linked list? It would be infinitely easier to use vectors instead. First you have to split the logic to add/mutli numbers and the container (linked list) to store digits. Then use std::vector than a self implementation of a linked list.
The rest was fun to code :) Your carry calculations are too complex. carry = value / 10;

Use -- to decrement a variable. e.g., length--;

 The code works fine if I call the addition method.
Are you sure? Try printing x.length() inside operator<<. You'll find that it's wrong and that this is one reason that mult() fails.

Don't modify length inside add(). You actually don't need to use it, just check whether temporary1 and temporary2 are non-null.

There are at least SEVEN different places where you add a digit to a NaturalNumber. There should be only ONE - inside a function. Then you'd only have to adjust the length in one place.

You'll probably find that your code doesn't work well with zero. I prefer to represent 0 as an empty list, rather than a 1-digit value. Add special code in operator<< to handle this.

You leak memory everywhere. For now, I'd just live with it since fixing it is a bunch of work.

Pulling together all the advice above and putting it in one file (just for my convenience):
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 #include using namespace std; struct ListNode { char digit; ListNode *next; ListNode *prev; }; class NaturalNumber { private: ListNode * msd; // first ListNode *lsd; // last int length; public: NaturalNumber(int n); void prepend(int value); NaturalNumber add(const NaturalNumber & x); NaturalNumber mult(NaturalNumber & x); NaturalNumber multi(const char d); friend ostream & operator<<(ostream & outs, const NaturalNumber & x); }; // longint.cpp: #include // #include "longint.h" #include using namespace std; NaturalNumber::NaturalNumber(int n) { lsd = msd = NULL; length = 0; while (n > 0) { prepend(n%10); n /= 10; } } void NaturalNumber::prepend(int digit) { ListNode *p = new ListNode; // Comment out this check once the code works if (digit < 0 || digit > 9) { cout << "error: prepending " << digit << '\n'; } p->digit = digit; p->next = msd; p->prev = NULL; if (msd) { msd->prev = p; } else { lsd = p; } msd = p; ++length; } ostream & operator<<(ostream & outs, const NaturalNumber & x) { int digits = 0; if (x.msd == NULL) { cout << '0'; } else { for (ListNode * p = x.msd; p != NULL; p = p->next) { char c = p->digit + '0'; outs << c; ++digits; } } // Debugging check for proper length if (digits != x.length) outs << " length = " << x.length; return outs; } NaturalNumber NaturalNumber::add(const NaturalNumber & x) { NaturalNumber *result = new NaturalNumber(0); ListNode *temporary1 = lsd; ListNode *temporary2 = x.lsd; int sum; int carry = 0; while (temporary1 && temporary2) { sum = temporary1->digit + temporary2->digit + carry; result->prepend (sum%10); carry = sum/10; temporary1 = temporary1->prev; temporary2 = temporary2->prev; } // One or the other, but not both, of temporary1 and temporary2 // Might be non-null so you need to add the remaining digits for // that one into result. while (temporary1 != NULL) { sum = temporary1->digit + carry; result->prepend(sum % 10); carry = sum/10; temporary1 = temporary1->prev; } while (temporary2 != NULL) { sum = temporary2->digit + carry; result->prepend(sum % 10); carry = sum/10; temporary2 = temporary2->prev; } // Finally, there might be one last carry digit if (carry != 0) { result->prepend(carry); } // Your implementation here return *result; } NaturalNumber NaturalNumber::multi(const char d) { NaturalNumber *result = new NaturalNumber(0); ListNode *temporary = lsd; int product; int carry = 0; while (temporary != NULL) { product = (temporary->digit) * d + carry; result->prepend(product % 10); carry = product / 10; temporary = temporary->prev; } // Add the carry digit if (carry != 0) { result->prepend(carry); } return *result; } NaturalNumber NaturalNumber::mult(NaturalNumber & x) { NaturalNumber *result = new NaturalNumber(0); NaturalNumber *placeholder = new NaturalNumber(0); ListNode *temporary1 = lsd; char digit_holder; int nums_zeros = 0; while (temporary1 != NULL) { digit_holder = temporary1->digit; *placeholder = x.multi(digit_holder); for (int i = 0; i < nums_zeros; i++) { *placeholder = placeholder->multi(10); } nums_zeros = nums_zeros + 1; *result = result->add(*placeholder); temporary1 = temporary1->prev; } // your implementation here return *result; } // main.cpp: #include #include // #include "longint.h" using namespace std; int main() { char cmd; cout << "Available commands: a (add), m (multiply), f (factorial), and q (quit).\n"; cout << "command: "; cin >> cmd; while (cmd != 'q' && cmd != 'Q') { if (cmd == 'a' || cmd == 'A') { int left, right; cout << "left operand = "; cin >> left; cout << "right operand = "; cin >> right; NaturalNumber x(left), y(right); cout << x << " + " << y << " = " << x.add(y) << '\n'; } else if (cmd == 'm' || cmd == 'M') { int left, right; cout << "left operand = "; cin >> left; cout << "right operand = "; cin >> right; NaturalNumber x(left), y(right); cout << x << " * " << y << " = " << x.mult(y) << '\n'; } cout << "command: "; cin >> cmd; } }
Registered users can post here. Sign in or register to post.