/* Q/A Answer: Multiply big numbers (up to 10^10000) https://www.sololearn.com/Discuss/796837/how-can-i-multiply-2-numbers-they-are-less-than-or-equal-10-10000 */ #include #include using namespace std; // ASCII character '0' #define ZERO 48 class BigNum { // NOTE: Only natural numbers // TODO: Store the numbers in base 255 or something. Storing a base10 disit in char is too wasteful public: BigNum() : _number("0") {} BigNum(const char *s) { // TODO: Check validity and stuff _number = s; } friend BigNum operator+(const BigNum &a, const BigNum &b) { BigNum c; int carry = 0; // +1 for possible carry c._number.resize(max(a._number.length(), b._number.length()) + 1); for (int i = 0; i < c._number.length(); i++) { int aDigit = (i < a._number.length() ? a._number[a._number.length()-i-1]-ZERO : 0); int bDigit = (i < b._number.length() ? b._number[b._number.length()-i-1]-ZERO : 0); int sum = aDigit + bDigit + carry; carry = sum / 10; c._number[c._number.length()-i-1] = sum % 10 + ZERO; } // Remove leading zeros int i = -1; while (c._number[++i] == '0') {} if (i > 0) c._number.erase(0, i); return c; } friend BigNum operator*(const BigNum &a, const BigNum &b) { BigNum c; for (int i = 0; i < a._number.length(); i++) { BigNum tmp; int m = a._number[a._number.length()-i-1] - ZERO; while (m--) tmp = tmp + b; c = c + (tmp << i); } return c; } friend BigNum operator<<(const BigNum &a, int n) { BigNum c = a; while (n--) c._number.push_back('0'); return c; } friend ostream &operator<<(ostream &os, const BigNum &a) { return (os << a._number); } friend istream &operator>>(istream &is, BigNum &a) { return (getline(is, a._number)); } private: string _number; }; int main() { BigNum a, b; cin >> a; cin >> b; //ifstream reader("numbers"); // one per line //reader >> a; //reader >> b; //reader.close(); cout << "a + b = " << a + b << endl; cout << "a * b = " << a * b << endl; return 0; }

Q/A: Multiply huge numbers