Длинная арифметика. Как оперировать числами, не помещающимися ни в один из числовых типов

В языках C и C++ есть два основных целых числовых типа (вещественный и символьный типы сейчас не рассматриваются): int и long, обычно имеющие размеры соответственно 32 и 64 байта. То есть int может содержать в себе числа от -2147483648 до 2147483647, а long от -9223372036854775808 до 9223372036854775807. Для повседневных вычислений, не требующих большого числа цифр в числах эти типы отлично подходят. С помощью типа long факториал двадцати (20! = 2432902008176640000) легко вычисляется, а вот факториал двадцати одного (21! = 1090942171709440000) в него уже не влезет. Что же делать, если нужно получить значения превышающие ограничение типов данных?

На помощь приходит так называемая длинная арифметика, реализуемая не аппаратно, а программно. Числа хранятся в другом виде, например в массиве цифр или строке, а операции над числами реализуются при помощи алгоритмов, применяющихся к самим цифрам.

Длинная арифметика позволяет считать сколь угодно большие числа (при хранении цифр в строке (std::string) можно оперировать числами с 9223372036854775807 цифрами). Однако есть довольно существенный минус: по сравнению с обычными типами данных этот способ является довольно медленным, так как все операции выполняются для всех цифр программно. Впрочем, 1000! (2568 цифр) посчитается всего за 30 мс. Так что это того стоит!

Реализация длинной арифметики - очень интересное занятие как с точки зрения алгоритмики, так и практики в программировании. Было решено реализовать длинную арифметику на C++ и создать класс BigInt, хранящий в себе числа и поддерживающий следующие операции:

• сложение (+);
• вычитание (-);
• умножение (*);
• деление (/);
• получение остатка от деления (%);
• унарные плюс (+) и минус (-);
• постфиксный и префиксный инкремент (++);
• постфиксный и префиксный декремент (--);
• краткие записи арифметических операций (+=, -=, *=, /=, %=);
• операции сравнения (==, !=, <, >, <=, >=).

А также следующие методы:

• получение знака sign();
• проверка на чётность isEven();
• возведение в степень pow(long);
• получение абсолютной величины числа abs;
• получение корня n-ой степени из числа sqrt(long));
• ввод объекта из стандартного потока ввода;
• вывод объекта в стандартный поток вывода.

#ifndef BIG_INT_H
#define BIG_INT_H

#include <iostream>
#include <string>

class BigInt {
	std::string value; // значение числа
	bool isNeg; // флаг отрицательности

	static BigInt karatsuba_mul(const BigInt &a, const BigInt &b); // умножение методом Карацубы

public:
	BigInt(); // конструктор умолчания (число равно нулю)
	BigInt(long x); // конструктор преобразования из обычного целого числа
	BigInt(const std::string &value); // конструктор преобразования из строки
	BigInt(const BigInt& bigInt); // конструктор копирования

	const std::string &getValue() const; // получение содержимого строки (строка модуля числа)

	const bool getIsNeg() const; // получение флага отрицательности числа
	void setIsNeg(bool isNeg); // установка флага отрицательности числа

	int sign() const; // получение знака числа
	const bool isEven() const; // проверка на чётность

	BigInt abs() const; // получение модуля числа
	BigInt pow(long n) const; // получение числа в степени n
	BigInt sqrt(long n = 2) const; // вычисление корня n-ой степени из числа

	// операции сравнения
	const bool operator==(const BigInt &bigInt) const;
	const bool operator!=(const BigInt &bigInt) const;

	const bool operator<(const BigInt &bigInt) const;
	const bool operator>(const BigInt &bigInt) const;
	const bool operator<=(const BigInt &bigInt) const;
	const bool operator>=(const BigInt &bigInt) const;

	// операция присваивания
	BigInt &operator=(const BigInt &bigInt);

	// унарные плюс и минус
	BigInt operator+() const &&;
	BigInt operator-() const &&;

	// арифметические операции
	BigInt operator+(const BigInt &bigInt) const;
	BigInt operator-(const BigInt &bigInt) const;
	BigInt operator*(const BigInt &bigInt) const;
	BigInt operator/(const BigInt &bigInt) const;
	BigInt operator%(const BigInt &bigInt) const;
	BigInt operator<<(size_t n) const;
	BigInt operator>>(size_t n) const;

	// краткая форма операций
	BigInt &operator+=(const BigInt &bigInt);
	BigInt &operator-=(const BigInt &bigInt);
	BigInt &operator*=(const BigInt &bigInt);
	BigInt &operator/=(const BigInt &bigInt);
	BigInt &operator%=(const BigInt &bigInt);
	BigInt &operator<<=(size_t n);
	BigInt &operator>>=(size_t n);

	// префиксная форма
	BigInt &operator++(); // ++v
	BigInt &operator--(); // --v

	// постфиксная форма
	BigInt operator++(int); // v++
	BigInt operator--(int); // v--


	friend std::ostream &operator<<(std::ostream &stream, const BigInt &bigInt); // вывод числа в выходной поток
	friend std::istream &operator>>(std::istream &stream, BigInt &bigInt); // ввод числа из входного потока
};

#endif

Для проверки корректности и скорости реализованных алгоритмов были написаны тесты, прогоняющие арифметические операции с числами различной длины. По итогам этих тестов получилось следующее:

Тест скорости длинной арифметики

• Операции сложения, вычитания и умножения в среднем выполняются за 0.3 - 0.4 мкс;
• Операции деления и получения остатка - за 0.8 - 1.1 мкс.

На скриншотах показаны вычисление факториала и большой степени двойки.

Пример вычисления факториала

Пример вычисления большой степени двойки

Для того чтобы начать работу с длинной арифметикой, Вам нужно скачать нашу библиотеку BigInt, разместить оба файла (BigInt.h и BigInt.cpp) в папку с проектом и в основной программе подключить её с помощью директивы #include "BigInt.h".

Использованить библиотеку очень просто: чтобы создать объект класса BigInt просто воспользуйтесь одним из конструкторов:

• Конструктор по умолчанию: BigInt var; или BigInt var(); - создаст объект класса BigInt с нулевым значением;
• Конструктор из типа long: BigInt var(123); или long v = 123; BigInt var(v); - создаст объект класса BigInt со значением из уже имеющейся переменной целого типа, который можно преобразовать к long;
• Конструктор из строки: BigInt var("12345678"); - создаст объект класса BigInt со значением, указанном в строке (в случае наличия в строке любых других символов помимо цифр, выбросится исключение типа std::string).

В случае обнаружения каких-либо ошибок или предложений по оптимизации алгоритмов вы можете написать нам на почту или найти нас в разделе контакты.