bigint multiplication

Here I've got a sad multiplication function that is part of a large bigint calculator class. the arr is a pointer to a resizable array class(get and set are members of that class). When I use this I can mulitply large numbers only by one digit, if more digits )example 12*214 i get 428 cause its only multiplying 214 by the 2 in twelve. I understand why that is happening, I'm just not sure that I can fix it before the assignment is due tomorrow. Any help? Thanks!


void multiply(const bigint &A)
{

int carry=0;
for(int i=size-1;i>=0;i--)
{

int result = arr->get(i)*A.arr->get(size-1)+carry;
arr->set(i,result%10);
carry=result/10;


}

}

int main()
{
a.assign("214");
b.assign("12");
a.multiply(b);
a.print();

return 0;
}
Last edited on
Do you have an add method?

if yes, you could do:
214 * 2 + 2140 * 1 (just add a 0 after the last digit)

It would be nice to know a bit more about what you allready have so we can help you
I do have an ann method

void add_pos(const bigint &A) //add big ints
{
int carry=0;
for(int i=size-1;i>=0;i--)
{
int result = arr->get(i)+A.arr->get(i)+carry;
arr->set(i,result%10);
carry=result/10;
}
}
I understand what you are saying but I'm just not sure how to code it.
thanks
What else do you have?
Could you please post the Function declerations of all methods?

Also, you might want to copy a bit of data.
And you have to resize your data a little bit. a multiplication of 999*999 results in a 6-digit value, not a 3-digit one.

And please use the code Tag! :D

I mean like this
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void multiply(const bigint &A)
{
    bigint temp1; // bigint with value 0

    int carry = 0;
    int shift = 0;

    for(int j = a.size-1; j >= 0; j--)
    {
        for(int i=size-1; i>=0; i--)
        {
            bigint temp2; // bigint with value 0 and size: size + A.size
            int result = (arr->get(i)*A.arr->get(j)+carry);
            temp2->set(temp2.size - shift - (i - size-1), result%10);
            carry=result/10;
        }
        shift++;
        temp1 += temp2;
    } 
    *this = temp1;
}
Not sure what all you would like so I heres the whole thing. the first class is a SafeArray and the second is the calculator

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
#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;
    }
    void set_default(Element d)        //set_default
    {
        def=d;
    }
        int get_size()                       //get size
    {
        return size;
    }
};

int size = 100;

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(const bigint &A)                             //
    {
        for(int i=0;i<arr->get_size();i++)
        {                                                            //Ways to initialize stuff
            arr->set(i,A.arr->get(i));
        }
    
    }
    
void assign(int num)                                     //
    {
        for(int i = arr->get_size()- 1; i >= 0; i--)
        {
            arr->set(i,num%10);
            num /=10;
        }
       
        
    }
    
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 add_pos(const bigint &A)                                //add big ints
    {
        int carry=0;
        for(int i=size-1;i>=0;i--)
           {
               int result = arr->get(i)+A.arr->get(i)+carry;
               arr->set(i,result%10);
               carry=result/10;
           }
    }
    void multiply(const bigint &A)
{

int carry=0;
for(int i=size-1;i>=0;i--)
{

int result = arr->get(i)*A.arr->get(size-1)+carry;
arr->set(i,result%10);
carry=result/10;


}

}
};
first off, Did my multiply method work?
No I got alot of errors with the referencing of the methods of the other class for temp 1 and 2.My fault though, I should have sent you the full code first
could you please post those errors?
Here are the errors, I commented them


void multiply(const bigint &A)
{
bigint temp1; // bigint with value 0

int carry = 0;
int shift = 0;

for(int j = A.size-1; j >= 0; j--) //no member size in bigint
{
for(int i=size-1; i>=0; i--)
{
bigint temp2; // bigint with value 0 and size: size + A.size
int result = (arr->get(i)*A.arr->get(j)+carry);
temp2->set(temp2.size - shift - (i - size-1), result%10); //no member size or set in bigint
carry=result/10;
}
shift++;
temp1 += temp2; //no viable overloaded+=
}
*this = temp1;
}
Use the code-tag! (on the right under Format the top left symbol)

well, all of them are quite obvious
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void multiply(const bigint &A)
{  
  bigint temp1; // bigint with value 0

  int carry = 0;
  int shift = 0;

  for(int j = size-1; j >= 0; j--) //no member size in bigint
  {  
    for(int i=size-1; i>=0; i--)
    {
      bigint temp2; // bigint with value 0 and size: size + A.size
      int result = (arr->get(i)*A.arr->get(j)+carry);
      temp2->set(size - shift - (i - size-1), result%10);
      carry=result/10;
    }
    shift++;
    temp1.add_pos(temp2);
  }
  *this.assign(temp1);
}


changed all *.size to size
and the operator+ to add_pos
and *this = temp1 to *this assign
Sorry, I'll use it from now on.
I'm still getting errors on lines 14,18, and 20
14 says ( member reference type bigint is not a pointer)
18 says ( use of undeclared identifier temp2)
20 says ( member reference type bigint is a pointer
These are up to you to clear up, they are all quite obvious :)
I changed it to this in order to get rid of the errors but it doesnt run so I may have just screwed it up haha.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 void multiply(const bigint &A)
    {
        bigint temp1; // bigint with value 0
        
        int carry = 0;
        int shift = 0;
         bigint temp2;
        for(int j = size-1; j >= 0; j--) //no member size in bigint
        {
            for(int i=size-1; i>=0; i--)
            {
                // bigint with value 0 and size: size + A.size
                int result = (arr->get(i)*A.arr->get(j)+carry);
                temp2.arr->set(size - shift - (i - size-1), result%10);
                carry=result/10;
            }
            shift++;
            temp1.add_pos(temp2);
        }
        this->assign(temp1);
    }
Well, looks fine to me now ^^
Seems like my algorithm does not work.

I have a question.
Why is your arr a pointer?
I'm doing this for a class, and our teacher showed us how to get started and he made it a pointer, so I just went with it.
Well, it makes sense if you want to assign data... but did he also write the rest of the SaveArray class?
Do you have to use that SaveArray class?
I wrote the safe array class (he checked it and said it'll work fine for my bigint class) yeah we have to use it for the bigint.
I added that range check:
1
2
3
4
if(size - shift - (i - size-1) >= 0)
    temp2.arr->set(size - shift - (i - size-1), result%10);
else
    break;

It looks like this now...
I have a hard time using your SaveArray class for that example because we loop from the end to the beginning and so the resizing mechanism does not work
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
void multiply(const bigint &A)
{  
  bigint temp1; // bigint with value 0

  int carry = 0;
  int shift = 0;

  for(int j = size-1; j >= 0; j--) //no member size in bigint
  {  
    for(int i=size-1; i>=0; i--)
    {
      bigint temp2; // bigint with value 0 and size: size + A.size
      int result = (arr->get(i)*A.arr->get(j)+carry);

void multiply(const bigint &A)
    {
        bigint temp1; // bigint with value 0
        
        int carry = 0;
        int shift = 0;
         bigint temp2;
        for(int j = size-1; j >= 0; j--) //no member size in bigint
        {
            for(int i=size-1; i>=0; i--)
            {
                // bigint with value 0 and size: size + A.size
                int result = (arr->get(i)*A.arr->get(j)+carry);
                
                if(size - shift - (i - size-1) >= 0)
                    temp2.arr->set(size - shift - (i - size-1), result%10);
                else
                    break;

                carry=result/10;
            }
            shift++;
            temp1.add_pos(temp2);
        }
        this->assign(temp1);
    }
Last edited on
Topic archived. No new replies allowed.