### 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 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* 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;
}

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;
}
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 :)

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120`` ``````#include #include #include #include struct NaturalNumber { std::vector digits; NaturalNumber() = default; NaturalNumber(int n) { digits.push_back(n%10); n = n / 10; while(n > 0) { digits.push_back(n%10); n = n / 10; } } int64_t toInt() const { int64_t result = 0; int64_t multiplicator = 1; for(auto digit : digits) { result += digit*multiplicator; multiplicator *= 10; } return result; } NaturalNumber add(const NaturalNumber& rhs) const { NaturalNumber result; int carry = 0; // add common part auto commonLength = std::min(digits.size(), rhs.digits.size()); for(size_t i=0; i < commonLength; ++i) { auto sum = digits[i] + rhs.digits[i] + carry; result.digits.push_back(sum%10); if(sum > 9) { carry = 1; } else { carry = 0; } } // add rest of this number for(size_t i=commonLength; i < digits.size(); ++i) { auto sum = digits[i] + carry; result.digits.push_back(sum%10); if(sum > 9) { carry = 1; } else { carry = 0; } } // or add rest of rhs number for(size_t i=commonLength; i < rhs.digits.size(); ++i) { auto sum = rhs.digits[i] + carry; result.digits.push_back(sum%10); if(sum > 9) { carry = 1; } else { carry = 0; } } if(carry == 1) { result.digits.push_back(carry); } return result; } NaturalNumber mult(const NaturalNumber& rhs) const { // 0*x = 0 // x*0 = 0 if(toInt() == 0 or rhs.toInt() == 0) { return NaturalNumber(0); } NaturalNumber result; for(int64_t i=0; i < rhs.toInt(); ++i) { result = result.add(*this); } return result; } }; std::ostream& operator<<(std::ostream& s, const NaturalNumber& n) { // digits are stored in reverse for(size_t i=0; i < n.digits.size(); ++i) { s << char(n.digits[n.digits.size()-i-1]+'0'); } return s; } int main() { // conversion assert(NaturalNumber(1).toInt() == 1); assert(NaturalNumber(123).toInt() == 123); // addition assert(NaturalNumber(1).add(NaturalNumber(2)).toInt() == 3); assert(NaturalNumber(12).add(NaturalNumber(3)).toInt() == 15); assert(NaturalNumber(3).add(NaturalNumber(45)).toInt() == 48); assert(NaturalNumber(90).add(NaturalNumber(10)).toInt() == 100); assert(NaturalNumber(153).add(NaturalNumber(456)).toInt() == 609); // multiplication assert(NaturalNumber(0).mult(NaturalNumber(0)).toInt() == 0); assert(NaturalNumber(0).mult(NaturalNumber(1)).toInt() == 0); assert(NaturalNumber(1).mult(NaturalNumber(0)).toInt() == 0); assert(NaturalNumber(1).mult(NaturalNumber(1)).toInt() == 1); assert(NaturalNumber(10).mult(NaturalNumber(9)).toInt() == 90); assert(NaturalNumber(10).mult(NaturalNumber(12)).toInt() == 120); NaturalNumber x(153), y(456); std::cout << x << " + " << y << " = " << x.add(y) << '\n'; return 0; } ``````
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; } }``````