Implementing long-term arithmetic in C ++

In most modern languages, the programmer no longer needs to worry about numbers with which the processor cannot directly manipulate. Somewhere, like in Python or Haskell, support for long integer types is built right into the core of the language, somewhere, like in Java or C #, is implemented as separate classes. But in the standard library of C ++, long numbers are still not supported. So I decided to write it myself.

Class structure

The first thing to decide is how to store our number. I store it in the form of an array of numbers, in reverse order (this makes it easier to implement all operations), at once, 9 digits in one element of the array (which saves memory):

class big_integer { //    (1 000 000 000) static const int BASE = 1000000000; //    std::vector<int> _digits; //   bool _is_negative; }; 

In my implementation there will be two representations of zero at once - in the form of an empty vector and in the form of a vector with one and only zero.

Create number

The first thing you need to learn to do is create a number. This is how it is converted from a string containing numbers:

 big_integer::big_integer(std::string str) { if (str.length() == 0) { //      this->_is_negative = false; } else { if (str[0] == '-') { str = str.substr(1); this->_is_negative = true; } else { this->_is_negative = false; } // - i    size_t.      , //   int      ,   long long for (long long i = str.length(); i > 0; i -= 9) { if (i < 9) this->_digits.push_back(atoi(str.substr(0, i).c_str())); else this->_digits.push_back(atoi(str.substr(i - 9, 9).c_str())); } //     ,    this->_remove_leading_zeros(); } } 

The code of the procedure for removing leading zeros is simple to disgrace:

 void big_integer::_remove_leading_zeros() { while (this->_digits.size() > 1 && this->_digits.back() == 0) { this->_digits.pop_back(); } //   ,        if (this->_digits.size() == 1 && this->_digits[0] == 0) this->_is_negative = false; } 

We also need to be able to convert ordinary numbers to long:

 big_integer::big_integer(signed long long l) { if (l < 0) { this->_is_negative = true; l = -l; } else this->_is_negative = false; do { this->_digits.push_back(l % big_integer::BASE); l /= big_integer::BASE; } while (l != 0); } big_integer::big_integer(unsigned long long l) { this->_is_negative = false; do { this->_digits.push_back(l % big_integer::BASE); l /= big_integer::BASE; } while (l != 0); } 

The conversion code from the other types is even simpler, I did not mention it here.

Conclusion number

Now we need to learn how to print our number to a stream and convert it to a string:

 std::ostream& operator <<(std::ostream& os, const big_integer& bi) { if (bi._digits.empty()) os << 0; else { if (bi._is_negative) os << '-'; os << bi._digits.back(); //        9  //    -,     char old_fill = os.fill('0'); for (long long i = static_cast<long long>(bi._digits.size()) - 2; i >= 0; --i) { os << std::setw(9) << bi._digits[i]; } os.fill(old_fill); } return os; } big_integer::operator std::string() const { std::stringstream ss; ss << *this; return ss.str(); } 

')

Comparison of numbers

Now we need to learn how to compare two numbers with each other. The theory says that only two operations are enough for this, the rest can be derived from them. So, first learn to compare two numbers for equality:

 bool operator ==(const big_integer& left, const big_integer& right) { //       if (left._is_negative != right._is_negative) return false; //      ,     if (left._digits.empty()) { if (right._digits.empty() || (right._digits.size() == 1 && right._digits[0] == 0)) return true; else return false; } if (right._digits.empty()) { if (left._digits.size() == 1 && left._digits[0] == 0) return true; else return false; } //       ,         () if (left._digits.size() != right._digits.size()) return false; for (size_t i = 0; i < left._digits.size(); ++i) if (left._digits[i] != right._digits[i]) return false; return true; } 

Now check if one is smaller than the other:

 bool operator <(const big_integer& left, const big_integer& right) { if (left == right) return false; if (left._is_negative) { if (right._is_negative) return ((-right) < (-left)); else return true; } else if (right._is_negative) return false; else { if (left._digits.size() != right._digits.size()) { return left._digits.size() < right._digits.size(); } else { for (long long i = left._digits.size() - 1; i >= 0; --i) { if (left._digits[i] != right._digits[i]) return left._digits[i] < right._digits[i]; } return false; } } } 

Here we use unary negation to change the sign of a number. I also introduced a unary plus for symmetry:

 const big_integer big_integer::operator +() const { return big_integer(*this); } const big_integer big_integer::operator -() const { big_integer copy(*this); copy._is_negative = !copy._is_negative; return copy; } 

I learned from this article about why to return const big_integer, not just big_integer, and also about the rules for choosing between a friendly operator function and a member operator of a class.

Then everything is quite simple:

 bool operator !=(const big_integer& left, const big_integer& right) { return !(left == right); } bool operator <=(const big_integer& left, const big_integer& right) { return (left < right || left == right); } bool operator >(const big_integer& left, const big_integer& right) { return !(left <= right); } bool operator >=(const big_integer& left, const big_integer& right) { return !(left < right); } 

Arithmetic operations

Addition

I did not begin to subtilize with operations and realized normal school addition in a column. Since, in any case, we will need to create a new number as a result of the operation, I immediately copy the left operand by value onto the stack and add the numbers directly to it:

 const big_integer operator +(big_integer left, const big_integer& right) { //        //   ,      if (left._is_negative) { if (right._is_negative) return -(-left + (-right)); else return right - (-left); } else if (right._is_negative) return left - (-right); int carry = 0; //      for (size_t i = 0; i < std::max(left._digits.size(), right._digits.size()) || carry != 0; ++i) { if (i == left._digits.size()) left._digits.push_back(0); left._digits[i] += carry + (i < right._digits.size() ? right._digits[i] : 0); carry = left._digits[i] >= big_integer::BASE; if (carry != 0) left._digits[i] -= big_integer::BASE; } return left; } 

Here I avoided the “expensive” division operation in the case when the resulting “figure” is more than the basis on which I work, by simple comparison.

Subtraction

In principle, subtraction is similar to addition. It is only necessary to consider the case when the decrease is less than the deductible:

 const big_integer operator -(big_integer left, const big_integer& right) { if (right._is_negative) return left + (-right); else if (left._is_negative) return -(-left + right); else if (left < right) return -(right - left); int carry = 0; for (size_t i = 0; i < right._digits.size() || carry != 0; ++i) { left._digits[i] -= carry + (i < right._digits.size() ? right._digits[i] : 0); carry = left._digits[i] < 0; if (carry != 0) left._digits[i] += big_integer::BASE; } left._remove_leading_zeros(); return left; } 

Increment and decrement

Before implementing these two operations, we need to implement addition and subtraction with assignment:

 big_integer& big_integer::operator +=(const big_integer& value) { return *this = (*this + value); } big_integer& big_integer::operator -=(const big_integer& value) { return *this = (*this - value); } 

Then the prefix versions of the operations are implemented in one line, and the postfix versions are only slightly more complicated:

 const big_integer big_integer::operator++() { return (*this += 1); } const big_integer big_integer::operator ++(int) { *this += 1; return *this - 1; } const big_integer big_integer::operator --() { return *this -= 1; } const big_integer big_integer::operator --(int) { *this -= 1; return *this + 1; } 

Multiplication

I did not write the rapid multiplication of Karatsuba, but again I used “school” arithmetic:

 const big_integer operator *(const big_integer& left, const big_integer& right) { big_integer result; result._digits.resize(left._digits.size() + right._digits.size()); for (size_t i = 0; i < left._digits.size(); ++i) { int carry = 0; for (size_t j = 0; j < right._digits.size() || carry != 0; ++j) { long long cur = result._digits[i + j] + left._digits[i] * 1LL * (j < right._digits.size() ? right._digits[j] : 0) + carry; result._digits[i + j] = static_cast<int>(cur % big_integer::BASE); carry = static_cast<int>(cur / big_integer::BASE); } } //     result._is_negative = left._is_negative != right._is_negative; result._remove_leading_zeros(); return result; } 

Division

Since I have not found on the Internet fast ways to divide, we will use the school division corner. Let's start to share with the senior discharges. We need to reduce the current value of the dividend by the maximum possible number of dividends. We will search for this maximum value by binary search. But first we need to define the function of “shifting” the number to the right, which will allow us to iterate through the digits sequentially:

 void big_integer::_shift_right() { if (this->_digits.size() == 0) { this->_digits.push_back(0); return; } this->_digits.push_back(this->_digits[this->_digits.size() - 1]); //             , //  i  ""  size_t for (size_t i = this->_digits.size() - 2; i > 0; --i) this->_digits[i] = this->_digits[i - 1]; this->_digits[0] = 0; } 

Now we describe the division itself:

 const big_integer operator /(const big_integer& left, const big_integer& right) { //     if (right == 0) throw big_integer::divide_by_zero(); big_integer b = right; b._is_negative = false; big_integer result, current; result._digits.resize(left._digits.size()); for (long long i = static_cast<long long>(left._digits.size()) - 1; i >= 0; --i) { current._shift_right(); current._digits[0] = left._digits[i]; current._remove_leading_zeros(); int x = 0, l = 0, r = big_integer::BASE; while (l <= r) { int m = (l + r) / 2; big_integer t = b * m; if (t <= current) { x = m; l = m + 1; } else r = m - 1; } result._digits[i] = x; current = current - b * x; } result._is_negative = left._is_negative != right._is_negative; result._remove_leading_zeros(); return result; } 

Here, big_integer::divide_by_zero is an empty class inherited from std::exception .

Taking balance

In fact, in the previous operation, the remainder is actually stored in the variable current . But I wondered about the definition of the remainder sign. Wikipedia says that the remainder of the division is always positive. Therefore, I wrote this version of this operation:

 const big_integer operator %(const big_integer& left, const big_integer& right) { big_integer result = left - (left / right) * right; if (result._is_negative) result += right; return result; } 

Exponentiation

I used the quick exponentiation algorithm. It requires checking the number for odd. Since it would be expensive to calculate the remainder of division by 2, to put it mildly, we introduce the following operations:

 bool big_integer::odd() const { if (this->_digits.size() == 0) return false; return this->_digits[0] & 1; } bool big_integer::even() const { return !this->odd(); } 

Now we will write the construction itself:

 const big_integer big_integer::pow(big_integer n) const { big_integer a(*this), result(1); while (n != 0) { if (n.odd()) result *= a; a *= a; n /= 2; } return result; } 

Full class code: pastebin.com/MxQdP5s9

Everything! Now you can calculate, for example, 2 ¹⁰⁰⁰ , or factorial 100:

 #include <iostream> #include "big_integer.hpp" using namespace std; int main() { big_integer bi("2"), bi2 = 100; cout << bi.pow(1000) << endl; big_integer f = 1; for (big_integer i = 2; i <= bi2; ++i) f *= i; cout << f << endl; } 

Literature

1. e-maxx.ru - a site dedicated to olympiad algorithms
2. cppalgo.blogspot.ru/2010/05/blog-post.html - Igor Belyaev's blog