hatred1993 March 16, 2013 at 18:41

Implementation of lengthy arithmetic in C ++

From the sandbox

In most modern languages, the programmer no longer needs to worry about numbers that 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 #, it is implemented as separate classes. But in the C ++ standard library, 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), 9 digits in one element of the array at once (which saves memory):

class big_integer {
	// основание системы счисления (1 000 000 000)
	static const int BASE = 1000000000;
	// внутреннее хранилище числа
	std::vector _digits;
	// знак числа
	bool _is_negative;
};

In my implementation, there will be two immediately representations of zero - in the form of an empty vector and in the form of a vector with one single zero.

Number creation

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 regular numbers to long ones:

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 cite it here.

Number output

Now we need to learn how to print our number into 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(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 for this, only two operations are enough, the rest can be derived based on them. So, first we learn how 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 number is less 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;
}

The knowledge about why const big_integer should be returned, and not just big_integer, as well as about the rules for choosing between a friendly operator function and a member operator of a class, I have learned from this article .

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 become wise with operations and realized the usual 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 to 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 where the resulting “figure” is larger than the basis for which I work, by a simple comparison.

Subtraction

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

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 prefix versions of operations are implemented in one line, and postfix versions are only a little 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 fast multiplication of Karatsuba, and again 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(cur % big_integer::BASE);
                        carry = static_cast(cur / big_integer::BASE);
                }
        }
        // не забудем про знак
        result._is_negative = left._is_negative != right._is_negative;
        result._remove_leading_zeros();
        return result;
}

Division

Since I did not find fast ways to divide on the Internet, we will use the school division corner. Let's start sharing with the higher ranks. We need to reduce the current value of the dividend by the maximum possible number of the dividend. This maximum value will be searched by binary search. But first, we need to determine the function of “shifting” the number to the right, which will allow us to iterate over the digits in sequence:

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 will 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(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_zeroit is an empty class inherited from std::exception.

Taking the remainder

In fact, in the previous operation, the remainder is actually stored in a variable current. But I wondered the definition of the sign of the remainder. Wikipedia says the remainder of a 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 oddness. Since it would be expensive to calculate the remainder of dividing 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 write the erection 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

That's it! Now you can calculate, for example, 2 ¹⁰⁰⁰ , or factorial 100:

#include 
#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

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

Tags: