C++

Forum

 
Bigint Multiplication Help C++

dudicus14 (22)
Here I've got a SafeArray(not that safe but my teacher said it's fine) class and a bigint class. My bigint class can add and subtract just fine but when I try the multiply function it doesn't print anything at all, i've tried debugging and stepping through it but I can't seem to figure it out, been working on it for a while and am hopelessly stuck. Any help would be appreciated. Thanks

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
 
  #include <iostream>
using namespace std;


template<typename Element>
class SafeArray
{
    int size;
    Element*Array;
    Element def;

public:
    SafeArray()                         //default constructor(with no parameter)
    {
                size = 10;
        Array = new Element[size];


    }
    SafeArray(int value)         //constructor with one int
    {
        size = value;
        Array = new Element[value];

    }
    ~SafeArray() {
        delete [] Array;
    }                                       //destructor
    Element get(int pos)                    //get method
        { if (pos<0)
        {cout<<"error";}

            if(pos>=size)
            { set_default(def);}
            return Array[pos]; }

    void set(int pos, Element val)
    {
        if (pos<0)
        {
            cout<<"error";
            return;
        }
        if(pos>=size)
        {
            resize(pos+1);
        }
        Array[pos] = val;
    }
    void resize(int new_size)
    {
        Element*temp=new Element[new_size];
        for(int i = 0; i<size;i++)
        {temp[i]=Array[i];}
        delete[]Array;
        Array = temp;
        size=new_size;
    }
};

int size = 100; //for testing

class bigint
{
    SafeArray<int> *arr;
public:
    bool sign;
bigint()                                                   //initializes to zero
    {
        arr = new SafeArray<int>;
        for(int i =0;i < size; i++)
            arr->set(i,0);
    }

void print()                                               //prints numbers without zeroes in front
    {
        bool start_num=false;
        for(int i = 0;i <arr->get_size() ;i++)
        {
            if(arr->get(i)!=0 && start_num==false )
            {start_num=true;
                cout << arr->get(i);}
         else if(start_num==true)
             cout<<arr->get(i);

        }

       cout<<endl;
    }

void assign(string num)                                  
    {
        long len = num.length();
        int j=arr->get_size()-1;
        for(long i=len-1;i>=0;i--)
        {
            arr->set(j,num[i]-48);
            j--;
        }
    }
void multiply(const bigint &A)
    {
        for(int i=size-1;i>=0;i--)
            {
              int carry=0;

           for(int j=size-1;j>=0;j--)
             {
               int product=((arr->get(i)*A.arr->get(j))+carry);
               arr->set(i,product%10);
               carry=product/10;
             }
        }
}

}

int main()
{
 bigint a,b;
a.assign("1234");
b.assign("5678");
a.multiply(b);
a.print();

return 0;
}
Last edited on
fg109 (709)
Ignoring the problems with everything else, this is what is causing your multiply function to do nothing:

for(int i=size-1;i<=0;i--)

It should be:

for(int i=size-1;i>=0;i--)
dudicus14 (22)
yeah sorry that was just a typo, i fixed it. as for the problems with everything else. My Saferray kinda sucks but it should work because it works for my addition and subtraction. right? Unless you're referring to problems in the bigint class(aside from the obvious problems with the multiply function.
Last edited on
fg109 (709)
OK, another problem with your multiply function. Have you thought about what you're doing on line 110?
dudicus14 (22)
yeah not sure what i was thinking there, should just be i ,not i+j right?
fg109 (709)
No, your approach is all wrong. You're changing one of the numbers you're using to multiply while you're multiplying. Say I'm trying to multiply 12 by 34, after multiplying the first digit, suddenly I'm trying to multiply something like 18 by 34.

That's if you changed it to just i. If not, you have the different problem of trying to multiply 1208 by 34 (or something like that) except that you don't use the new digits you added for multiplication.
dudicus14 (22)
dang, Is it so completely wrong that i should do a whole different algorithm?could you help me fix it?
fg109 (709)
What you need is to create some bigint variables inside the function, initialized to zero, to hold the product as you're computing it. Then at the end of the function, set *this = product;.

This is a simple example of what I'm talking about:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void multiply(const bigint &A)
{
    bigint product, multiplicand, zero, one;
    product.assign("0");
    mulitplicand = A;
    zero.assign("0");
    one.assign("1");
    while (multiplicand > zero)
    {
        product = product + *this;
        multiplicand = multiplicand - one;
    }
    *this = product;
}

If you're looking for something more along the lines of what you were trying to do, I wrote this code for a BigInt class implemented as a doubly linked list before:

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
 
BigInt& BigInt::operator*=(const BigInt &rhs)
{
	BigInt sum; //default constructor pushes 0 into list
	unsigned int shift = 0;
	for (Digit *temp1 = tail; temp1; temp1 = temp1->prev)
	{
		BigInt product;
		unsigned int carry = 0;
		product.pop_back(); //empty out the list by removing the 0
		for (Digit *temp2 = rhs.tail; temp2; temp2 = temp2->prev)
		{
			unsigned int p = temp1->value * temp2->value + carry;
			carry = p / 10;
			product.push_front(p % 10);
		}
		while (carry)
		{
			product.push_front(carry % 10);
			carry /= 10;
		}
		for (unsigned int i = 0; i < shift; ++i)
			product.push_back(0);
		sum += product;
		++shift;
	}
	sum.positive = (positive == rhs.positive);
	*this = sum;
	return *this;
}
dudicus14 (22)
when I try the method on top i get errors on lines 8,10,11 that all say "invalid operands to binary expression (bigint and bigint) in xcode. In unix it says "no match for operator>" in line 8, "no match for operator+" in line 10,and "no match for operator-" in line 11,
fg109 (709)
You can't just copy and paste code and expect it to work. Think about what I'm trying to do in the code and how to change it to make it work with your code.
closed account (D80DSL3A)
I think a big difficulty for you is caused by storing the most significant digits first in the array.
Doing so may make displaying the number a little easier, but it makes all the arithmetic operations harder to work out. You seem to have made it work for addition, where only one more digit can result, but for multiplication the number of digits add, making your backwards approach harder to manage. If you store the ones digit in Array[0], the 10s digit in Array[1] and so on then the digits remain aligned as to element number and also more digits can be added to the end of the array as your safearray grows.
Use a temp. instance of a bigInt in your multiply function to place the products into so as not to overwrite the very values you're multiplying by.

Why the global int size = 100; at line 61? You're using it in places where arr->get_size() should be. Was this necessary to make addition work?
It causes other issues too. Your safearray has a default 10 elements, but your bigInt constructor uses the size=100 figure.
Every time arr->set(i,0); is called on line 72 after i=9 a new array is allocated.
This bigInt constructor is causing a new array allocation and copy operation 90 times!

That said,
@fg109 In case you're interested...
I too have written a bigInt class based on a doubly linked list.
I was able to make operators += and -= work without using a temp bigInt because I can overwrite the digit values right away. They aren't needed for further addition calcs.

Not so with multiplication. When doing it the grammar school by hand method each digit is used multiple times.
Since a temp instance was needed I wrote the primary code in operator* and returned the temp instance, then wrote operator*= in terms of operator*.
Most unsatisfactory!

I found I could avoid the temp instance and multiply 2 bigInts in place if I start with the most significant digit of *this and work backwards. I can finish with each digit value in one shot.
I have my digits stored with the least significant in the head node, though it isn't necessary in a doubly linked list. It's just leftover from my treatment in a singly linked list, which I changed from because reverse iteration is useful for display(), compare() and divide().
That's why you'll see push_back() where you push_front().
I'm using int32_t and int64_t types because I'm storing 8 digits per node (base = 100,000,000). Gotta be careful about overflow when multiplying!
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
 
// multiply in place. No temp instance
bigInt& bigInt::operator*=( const bigInt& B )
{
    if( B.numNodes == 1 )
    {
        this->operator*=(B.head->x);// use simpler *= int operation
        return *this;
    }

    // B is multinodal
    int64_t product = tail->x;
    product *= B.head->x;
    int32_t carry = product/base;
    int32_t Aval = tail->x;// save
    tail->x = product%base;
    dnode* itA = tail;
    const dnode* itB = nullptr;

    // allocate all new nodes on 1st pass
    for( itB = B.head->next; itB; itB = itB->next )
    {
        product = Aval;
        product *= itB->x;
        product += carry;
        push_back( product%base );
        carry = product/base;
    }
    if( carry ) push_back( carry );

    // *this is now populated. Carry out remaining passes
    for( itA = itA->prev; itA; itA = itA->prev )
    {
        carry = 0;
        Aval = itA->x;// save
        itA->x = 0;
        dnode* it = itA;
        for( itB = B.head; itB; itB = itB->next, it = it->next )
        {
            product = Aval;
            product *= itB->x;
            product += carry;
            product += it->x;
            it->x = product%base;
            carry = product/base;
        }
        if( carry && it ) it->x += carry;
    }

    isPositive = isPositive ? B.isPositive : !B.isPositive;// !XOR

    return *this;
}

Now operator* can be what it should:
1
2
3
4
5
6
 
bigInt operator*( const bigInt& a, const bigInt& b )
{
    bigInt temp(a);
    temp *= b;
    return temp;
}

Have you tried operators / or % yet?
I based mine on the "by hand" long division method. It was tricky, but it seems to be working.
Last edited on
fg109 (709)
@fun2code

I was going to suggest we take this to PM, but then I realized both of us have that function disabled. Not sure that this would still be considered on topic.

Have you tried operators / or % yet?
I based mine on the "by hand" long division method. It was tricky, but it seems to be working.

I've done the division operator, but haven't tried doing the modulo operator. I imagine the code would be quite similar.

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
 
BigInt& BigInt::operator/=(const BigInt &rhs)
{
    // skipped a bunch of code where I checked if abs(rhs) > abs(*this)
    // and returned *this = BigInt() if true
    BigInt divisor(rhs);
    BigInt dividend;
    BigInt quotient;
    Digit *d = head;
    dividend.pop_back();
    divisor.positive = true;
    do
    {
        int carry = 0;
        dividend.push_back(d->value);
        d = d->next;
        while (divisor <= dividend)
        {
            dividend -= divisor;
            ++carry;
        }
        quotient.push_back(carry);
    } while (d);
    while (quotient.head->next && quotient.head->value == 0)
        quotient.pop_front();
    quotient.positive = (positive == rhs.positive);
    *this = quotient;
    return *this;
}


I found your code very confusing at first. I had thought that it doesn't even work until I looked more closely at your second loop and noticed what you were doing with it.
closed account (D80DSL3A)
@fg109 I've enabled PMs. I actually had them enabled until recently.
Continued discussion here may amount to thread hijacking since our methods differ so much from OPs. Your /= method is much simpler than mine. I took an opposite tack by building up a copy of rhs (divisor) until it's just less than lhs (dividend). I then subtract multiples of the divisor from the dividend at a time. To estimate this multiple I consider the 2 most significant "digit" values from each. Somewhat simplified here:
int term = (lhs->tail->x*base + lhs->tail->next->x)/ (rhs->tail->x*base + rhs->tail->next->x); then dividend -= term*divisor;. This estimate is always within +- one multiple of correct. One corrective addition (because now dividend<0) or subtraction (because still dividend >= divisor ) does the job.

Modulo is easy. It's what's left of the dividend when division is complete. ie. the function actually gives both results.

@dudicus14. Did our comments in previous posts help? Sorry, if our bigInts were based on std::vector<int> instead of a linked list, the *= functions would be quite similar to what you're trying for! Still translatable though. Where you see stuff like it = it->next; it's the same as increasing an array index by one. it = it->prev; means decrease the index by one. In fact, here's a translation from fg109's code for *= (a multiply function).
His line 5: for (Digit *temp1 = tail; temp1; temp1 = temp1->prev)
translation:for ( int i = arr->get_size()-1; i>=0; --i)
Last edited on
Topic archived. No new replies allowed.