I had to create a class in C++ - BigInteger - that works with very large numbers that are written in the form of strings. As part of the assignment, I also had to predefine multiplication, and here's what I did:
BigInteger& BigInteger::operator*(const BigInteger& rhs)
{
string tmp(num.length() + rhs.num.length(), '0');
//a string in which I'll be temporarily storing the result
char carry = '0';
int d = 0;
//I'll use this to move with one index to the left in the result
for (int i = num.length() - 1; i >= 0; --i)
//start with the multiplying from the end of the first number
{
carry = '0';
for (int j = rhs.num.length() - 1, z = tmp.length() - 1 - d; j >= 0; --j, --z)
//start with the multiplying from the end of the second number and begin filling the result string (again from the end)
{
tmp[z] = ((tmp[z] - '0') + (num[i] - '0') * (rhs.num[j] - '0') + (carry - '0')) + '0';
//basically add to the current number in the result the multiplication of the respective digits in the two original numbers, plus the carry from the previous mutiplication
carry = ((tmp[z] - '0') / 10) + '0';
tmp[z] = ((tmp[z] - '0') % 10) + '0';
if (j == 0 && carry != '0')
{
tmp[z - 1] = carry;
}
}
++d;
}
if (carry != '0')
{
tmp[0] = carry;
}
else
{
tmp.erase(0, 1);
}
num = tmp;
return *this;
}
Everything works fine even with large numbers like 123456788*887654321, but once I try multiplying numbers containing a 9 in them (including smaller ones like 6789*9876), not only are the middle digits off, but there are differences between 6789*9876 and 9876*6789, including signs like "+" and apostrophe appearing roughly in the center in the latter case.
Has anyone here encountered such a problem or has any idea what might be causing it?
EDIT: Here's the predefined << operator:
ostream& operator<<(ostream& out, const BigInteger& rhs)
{
out << rhs.num;
return out;
}
and my "main":
#include "BigInteger.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
BigInteger num3("123456788");
BigInteger num4("887654321");
cout << num3 * num4 << endl;
//cout << num4 * num3 << endl;
}
and my class:
#ifndef H_BIGINTEGER
#define H_BIGINTEGER
#include <iostream>
#include <string>
using namespace std;
//I know I shouldn't have defined a namespace in the headers file, but left it for brevity's sake
class BigInteger
{
friend ostream& operator<<(ostream&, const BigInteger&);
public:
BigInteger();
BigInteger(string);
~BigInteger();
BigInteger(const BigInteger&);
BigInteger& operator=(const BigInteger&);
BigInteger& operator+(BigInteger&);
BigInteger& operator-(BigInteger&);
BigInteger& operator*(const BigInteger&);
private:
string num;
};
the constructor I'm using is just:
BigInteger::BigInteger(string num)
:num(num)
{}
The std::string char is signed and it gets negative when you add '0' and use it later for the carry and tmp[z] so its better to store it in a temporary ìnt
6789*9876
---------
int(char(res + '0'))
-------------------------------
0+9*6+0=54 102
0+9*7+5=68 116
0+9*8+6=78 126
0+9*9+7=88 -120
8+8*6+0=56 104
8+8*7+5=69 117
8+8*8+6=78 126
8+8*9+7=87 -121
9+7*6+0=51 99
8+7*7+5=62 110
7+7*8+6=69 117
8+7*9+6=77 125
2+6*6+0=38 86
9+6*7+3=54 102
7+6*8+5=60 108
7+6*9+6=67 115
So you can change your code like this:
int res = ((tmp[z] - '0') + (num[i] - '0') * (rhs.num[j] - '0') + (carry - '0'));
carry = (res / 10) + '0';
tmp[z] = (res % 10) + '0';
if (j == 0)
{
tmp[z - 1] = carry;
}