C++

Forum

 
Multiplication with linked list hw

wisely1300 (1)
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;

*result= result->add(*placeholder);
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?
jonnin (11437)
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
dhayden (5798)
Are you required to use a linked list? It would be infinitely easier to use vectors instead.
Thomas Huxhorn (61)
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 :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
#include <iostream>
#include <iostream>
#include <vector>
#include <cassert>

struct NaturalNumber {
    std::vector<int> 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;
}
dhayden (5798)
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):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
 
#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);

    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 <iostream>
// #include "longint.h"
#include <cmath>

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 <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;
    }
}
Topic archived. No new replies allowed.