I'm trying to build a class, bigint, which represents large numbers in an array but I am having trouble creating a *=
member function which multiplies this bigint with another bigint. I know there are already classes which achieve this but I'm trying to build my own as a learning exercise.
The digits of a biguint are stored in the array std::size_t data[CAPACITY]
with the least significant digit stored in data[0]
and the most significant digit in data[CAPACITY-1]
(little endian). For example, if CAPACITY=5
, then 12345 would be represented as data[0]=5, data[1]=4, data[2]=3, data[3]=2, data[4]=1
.
I have successfully built constructors, addition functions, size functions, <<
operator functions, >>
operator functions, and []
operator functions. For example, the following code works.
int main()
{
biguint b(423);
biguint c(2363);
b += c;
cout << b << endl;
cout << b.size() << endl;
return 0;
}
That will output:
2786
4
Onto the multiplication problem, this is the closest function I've come up with. It can correctly calculate bigints like 400*2 but fails at bigints like 400*20 since it rewrites data[i]
.
void bigint::operator *= (const bigint &n)
{
int carryover = 0;
for (size_t i=0; i < size(); ++i)
{
for (size_t j=0; j < n.size(); ++j)
{
std::cout << data[i] << "*" << n[j] << "=";
data[i] *= n[j];
std::cout << data[i] << std::endl;
}
}
}
I'm trying to do long multiplication like this:
109
* 12
____
218
+1090
_____
1308
I think the right way to do this would be to create a new bigint but I'm getting the error, lvalue required as left operand of assignment
, when I try something like this:
void bigint::operator *= (const biguint &n)
{
int carryover = 0;
bigint ans(0);
for (size_t i=0; i < size(); ++i)
{
for (size_t j=0; j < n.size(); ++j)
{
ans[j] += data[i] * n[i];
ans[j] += carryover;
carryover = ans[j] / 10;
ans[j] = ans[j] % 10;
}
}
}
What am I doing wrong? Is my approach correct at least? What is the correct way of multiplying two numbers stored as an little endian array?
For reference, this is how I coded the +=
operator. I'm basically just doing elementary school addition by hand.
void bigint::operator += (const biguint &n)
{
int carryover = 0;
for (size_t i=0; i < CAPACITY; ++i)
{
data[i] += n[i];
data[i] += carryover;
carryover = data[i] / 10;
data[i] = data[i] % 10;
}
}