В большинстве современных языков программисту уже не нужно заботиться о числах, с которыми процессор непосредственно манипулировать не может. Где-то, как в Python или Haskell, поддержка длинных целочисленных типов встроена прямо в ядро языка, где-то, как в Java или C#, реализована в виде отдельных классов. Но в стандартной библиотеке языка C++ длинные числа до сих пор не поддерживаются. Поэтому я решил написать её сам.
Структура класса
Первое, что нужно решить — это то, как хранить наше число. Я храню его в виде массива цифр, в обратном порядке (это позволяет проще реализовывать все операции), сразу по 9 цифр в одном элементе массива (что позволяет сэкономить память):
class big_integer {
// основание системы счисления (1 000 000 000)
static const int BASE = 1000000000;
// внутреннее хранилище числа
std::vector<int> _digits;
// знак числа
bool _is_negative;
};
В моей реализации будет сразу два представления нуля — в виде пустого вектора и в виде вектора с одним-единственным нулём.
Создание числа
Первое, что нужно научиться делать — это создавать число. Вот так оно преобразуется из строки, содержащей цифры:
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();
}
}
Код процедуры удаления ведущих нулей прост до безобразия:
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;
}
Также нам нужно уметь преобразовывать обычные числа в длинные:
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);
}
Код преобразования из остальных типов еще проще, я не стал приводить его здесь.
Вывод числа
Теперь нам нужно научиться печатать наше число в поток и преобразовывать его в строку:
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();
}
Сравнение чисел
Теперь нам нужно научиться сравнивать два числа друг с другом. Теория говорит, что для этого достаточно всего двух операций, остальные могут быть выведены на их основе. Итак, сначала научимся сравнивать два числа на равенство:
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;
}
Теперь проверим, меньше ли одно число другого:
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;
}
}
}
Здесь мы используем унарное отрицание, чтобы сменить знак числа. Также я для симметрии ввел унарный плюс:
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;
}
Знания о том, почему нужно возвращать const big_integer, а не просто big_integer, а также о правилах выбора между дружественной функцией-оператором и оператором-членом класса, я подчерпнул из этой статьи.
Дальше все совсем просто:
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);
}
Арифметические операции
Сложение
Я не стал мудрить с операциями и реализовал обычное школьное сложение в столбик. Поскольку нам в любом случае нужно будет создать новое число как результат операции, я сразу копирую в стек левый операнд по значению и прибавляю числа непосредственно к нему:
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;
}
Здесь я избежал «дорогой» операции деления в случае, когда получившаяся «цифра» больше основания, по которому я работаю, путем простого сравнения.
Вычитание
В принципе, вычитание аналогично сложению. Нужно лишь рассмотреть случай, когда уменьшаемое меньше вычитаемого:
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;
}
Инкремент и декремент
Перед реализацией этих двух операций нам нужно реализовать сложение и вычитание с присвоением:
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);
}
Тогда префиксные версии операций реализуются в одну строчку, а постфиксные — лишь немногим сложнее:
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;
}
Умножение
Я не стал писать быстрое умножение Карацубы, а снова использовал «школьную» арифметику:
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;
}
Деление
Поскольку я не нашел в Интернете быстрых способов деления, воспользуемся школьным делением уголком. Начнем делить со старших разрядов. Нам нужно уменьшить текущее значение делимого на максимально возможное число делимым. Это максимальное значение будем искать двоичным поиском. Но сначала нам нужно определить функцию «сдвига» числа вправо, которая позволит нам перебирать разряды последовательно:
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;
}
Теперь опишем само деление:
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;
}
Здесь big_integer::divide_by_zero это пустой класс, унаследованный от std::exception.
Взятие остатка
Вообще-то в предыдущей операции остаток фактически хранится в переменной current. Но я задался вопросом определения знака остатка. Википедия говорит, что остаток от деления всегда положителен. Поэтому я написал такую версию этой операции:
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;
}
Возведение в степень
Я использовал алгоритм быстрого возведения в степень. Он требует проверки числа на нечетность. Поскольку вычислять остаток от деления на 2, мягко говоря, было бы затратно, введем такие операции:
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();
}
Теперь напишем само возведение:
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;
}
Полный код класса: pastebin.com/MxQdP5s9
Всё! Теперь можно вычислить, к примеру, 21000, либо факториал 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;
}
Литература
- e-maxx.ru — сайт, посвященный олимпиадным алгоритмам
- cppalgo.blogspot.ru/2010/05/blog-post.html — блог Игоря Беляева
Автор: hatred1993
Большое Вам спасибо! Отличная реализация!