Работа с очень длинными числами на C++
Недавно я решил написать свою собственную реализацию длинной арифметики для C++. Делал просто для себя, ибо эта тема мне кажется довольно интересной. Поставил перед собой следующие задачи:
Реализация должна быть шустрой. Я, к сожалению, пока не обладаю знаниями высшей математики, но пользоваться интернетом умею и постарался интегрировать в программу все, что только смог найти.
Реализация должны быть экономна к памяти. Даже по-настоящему большие числа должны влезать в разумные пределы памяти.
Код должен быть относительно чистым, а то, как пользоваться классом — должно быть понятно и похоже на способы работы с обычными числами.
Код должен содержать необходимый набор функций, чтобы используя его можно было спокойно проводить проверки на простоту и выполнять некоторые другие необходимые и популярные операции.
Сразу предупрежу, что статья не претендует на звание лучшей реализации длинных чисел, а просто является (смею предположить) достаточно достойной реализацией, которая подойдет для тех, кто хочет получить доступную и задокументированную реализацию простых, но достаточно эффективных алгоритмов. Однако, в тоже время, я буду рад прислушаться к адекватной критике в комментариях.
Реализовывать буду знаковую целочисленную арифметику. Запаситесь провизией, поскольку рассказ будет долгий.
Для начала нам надо определиться, из чего будет состоять наш будущий проект. Нам понадобятся четыре файла: CMakeLists.txt (тут будут храниться инструкции компиляции), main.cpp (тут будет храниться некий примитивный консольный калькулятор, демонстрирующий функционал), LongInt.hpp (тут будет храниться сам заголовок класса) и LongInt.cpp (тут будут храниться сами исходники объектов класса).
Файл с инструкциями компиляции напишем сразу, в написании нет ничего сложного:
cmake_minimum_required(VERSION 3.20)
project(LongInt)
set(CMAKE_CXX_STANDARD 14)
add_executable(LongInt main.cpp LongInt.hpp LongInt.cpp)Файл с демонстрационным калькулятором пока пропустим, ибо сначала надо реализовать сам класс.
Делаем файл с заголовком класса:
#include
#include
class LongInt {
public:
LongInt();
LongInt(std::string string);
LongInt(signed int number);
LongInt(unsigned int number);
LongInt(signed long number);
LongInt(unsigned long number);
LongInt(signed long long number);
LongInt(unsigned long long number);
static std::string to_string(LongInt number);
friend std::ostream& operator <<(std::ostream& ostream, const LongInt& number);
static LongInt abs(LongInt number_first);
static bool even(LongInt number);
static bool odd(LongInt number);
static char sign(const LongInt& number);
static LongInt max(LongInt number_first, LongInt number_second);
static LongInt min(LongInt number_first, LongInt number_second);
friend bool operator ==(LongInt number_first, LongInt number_second);
friend bool operator !=(LongInt number_first, LongInt number_second);
friend bool operator >(LongInt number_first, LongInt number_second);
friend bool operator <(const LongInt& number_first, const LongInt& number_second);
friend bool operator >=(const LongInt& number_first, const LongInt& number_second);
friend bool operator <=(const LongInt& number_first, const LongInt& number_second);
friend LongInt operator +(LongInt number_first, LongInt number_second);
LongInt operator +=(LongInt number);
LongInt operator ++();
LongInt operator ++(int);
friend LongInt operator -(LongInt number_first, LongInt number_second);
LongInt operator -=(LongInt number);
LongInt operator --();
LongInt operator --(int);
friend LongInt operator *(const LongInt& number_first, const LongInt& number_second);
LongInt operator *=(const LongInt& number);
friend LongInt operator /(LongInt number_first, LongInt number_second);
LongInt operator /=(LongInt number);
friend LongInt operator %(LongInt number_first, LongInt number_second);
LongInt operator %=(LongInt number);
static LongInt pow(LongInt number_first, LongInt number_second);
static LongInt factorial(LongInt number);
static LongInt gcd(LongInt number_first, LongInt number_second);
static LongInt lcm(LongInt number_first, LongInt number_second);
static LongInt sqrt(const LongInt& number);
static LongInt cbrt(LongInt number);
private:
std::vector _digits;
bool _natural;
static const int _base = 1000000000;
static const int _base_length = 9;
static const int _length_maximum_for_default_multiply = 256;
static std::vector _string_convert_to_vector(const std::string& string);
static LongInt _zeroes_leading_remove(LongInt number);
static LongInt _shift_right(LongInt number, long long shift_power);
static LongInt _shift_left(LongInt number, long long shift_power);
static LongInt _multiply_karatsuba(LongInt number_first, LongInt number_second);
static LongInt _factorial_tree(LongInt number_first, const LongInt& number_second);
}; Тут, надо обратить внимание на несколько моментов. Сами разряды числа будут храниться в векторе _digits с указанной системой счисления.
В переменной _natural будет храниться натурально ли число. Тут надо сделать некоторую оговорку. Хоть и по математическим правилам ноль — не является натуральным числом, в этой реализации ноль будет рассматриваться как натуральное число, просто потому что так удобнее.
В переменной _base будет храниться база текущего числа. Сейчас поясню, почему выбрана именно 10^9. Во-первых, база должна быть натуральной степенью десятки, чтобы можно было легко переводить числа из нашей системы счисления в привычную для людей систему счисления, то есть десятичную. Во-вторых, база должна быть меньше типа int, то есть быть меньше 2^31–1. Это связано не только с тем, что вектор у нас типа int, а еще с тем, что конвертируя строку в вектор будет использоваться функция std: stoi, но об этом позже. В-третьих, при возведении в квадрат база должна быть меньше 2^63–1, чтобы избежать переполнение при операциях вроде умножения. Под эти условия подходят только 9 систем счисления: по основанию 10^1, по основанию 10^2, по основанию 10^3, по основанию 10^4, по основанию 10^5, по основанию 10^6, по основанию 10^7, по основанию 10^8 и по основанию 10^9. Мы выбираем наибольшую, ибо так мы значительно сэкономим память и уменьшим количество операций.
В переменной _base_length будет храниться количество нулей в текущей базе. У нас выбрана система счисления по основанию миллиард, следовательно, количество нулей — 9. Эта константа нужна для конвертации между системами счисления.
В переменной _length_maximum_for_default_multiply будет храниться значение до которого используется стандартное умножение в столбик, а не более быстрый алгоритм Анатолия Алексеевича Карацубы, но к этому мы еще вернемся.
Теперь приступим к самой тяжелой части кода — написания самих исходников объекта класса. Исходники класса будут куда сложнее, чем предыдущие файлы и будут нуждаться в куда большем количестве объяснений, поэтому, показывать файл я буду по кускам.
Добавим нужные нам заголовки. Iostream нужен для работы с std, vector — для работы с векторами, а LongArithmetic.hpp — заголовок текущего класса.
#include
#include
#include "LongInt.hpp" После того как мы добавили заголовки нам надо научиться преобразовывать строки, а также целочисленные типы в длинное число. Для этого напишем следующий кусок кода:
std::vector LongInt::_string_convert_to_vector(const std::string& string) {
std::vector result;
if (string.size() % _base_length == 0) {
result.resize(string.size() / _base_length);
}
else {
result.resize(string.size() / _base_length + 1);
}
for (long long string_position = string.size() - 1, result_position = result.size() - 1; string_position >= 0; string_position = string_position - _base_length, result_position = result_position - 1) {
if ((string_position + 1) - _base_length <= 0) {
result[result_position] = std::stoi(string.substr(0, (string_position + 1)));
}
else {
result[result_position] = std::stoi(string.substr((string_position + 1) - _base_length, _base_length));
}
}
return result;
}
LongInt::LongInt() {
_digits.resize(1);
_digits[0] = 0;
_natural = true;
}
LongInt::LongInt(std::string string) {
if (string.empty() or (string.size() == 1 and string[0] == '-')) {
throw "Fatal error. Type creation is impossible. String does not contain number.";
}
if (string[0] == '-') {
string.erase(string.begin() + 0);
_natural = false;
}
else {
_natural = true;
}
for (long long i = 0; i < string.size(); i = i + 1) {
if (string[i] < 48 or string[i] > 57) {
throw "Fatal error. Type creation is impossible. String contain unknown characters.";
}
}
while (string.size() != 1 and string[0] == '0') {
string.erase(string.begin() + 0);
}
_digits = LongInt::_string_convert_to_vector(string);
}
LongInt::LongInt(signed int number) {
if (number < 0) {
number = number * -1;
_natural = false;
}
else {
_natural = true;
}
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(unsigned int number) {
_natural = true;
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(signed long number) {
if (number < 0) {
number = number * -1;
_natural = false;
}
else {
_natural = true;
}
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(unsigned long number) {
_natural = true;
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(signed long long number) {
if (number < 0) {
number = number * -1;
_natural = false;
}
else {
_natural = true;
}
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(unsigned long long number) {
_natural = true;
_digits = LongInt::_string_convert_to_vector(std::to_string(number));
} Функция _string_convert_to_vector принимает натуральную строку без лидирующих нулей и без неизвестных символов и приводит ее к вектору базы, указанной в константе. Пустой конструктор просто кладет в вектор ноль и устанавливает в переменную _natural истинное значение (вы же помните, что ноль мы считаем натуральным числом). Конструктор из строки обрабатывает возможные исключения, после чего конвертирует отшлифованную строку в нужный нам вектор, а конструкторы из целочисленных типов вовсе пишутся элементарно.
Теперь нужно научиться конвертировать число в строку и печатать его в поток вывода.
std::string LongInt::to_string(LongInt number) {
if (number._digits.size() == 1 and number._digits[0] == 0) {
return "0";
}
std::string result;
if (number._natural == false) {
result.append("-");
}
result.reserve(number._digits.size() * (_base_length - 1));
std::string tmp;
result.append(std::to_string(number._digits[0]));
for (long long i = 1; i < number._digits.size(); i = i + 1) {
tmp = std::to_string(number._digits[i]);
tmp.reserve(_base_length - tmp.size());
while (tmp.size() < _base_length) {
tmp.insert(tmp.begin() + 0, '0');
}
result.append(tmp);
}
return result;
}
std::ostream& operator <<(std::ostream& ostream, const LongInt& number) {
std::string string = LongInt::to_string(number);
for (long long i = 0; i < string.size(); i = i + 1) {
ostream.put(string[i]);
}
return ostream;
}Единственное, что важно подчеркнуть в этом куске кода, что дополнение нулями до текущей базы не происходит на первом разряде числа. Как это объяснить — не знаю, но на опытах было выявленно, что дополнять нулями надо все разряды кроме первого.
Теперь напишем ряд простых, но нужных функций для того, чтобы перейти к реализации уже полноценных операций.
LongInt LongInt::_zeroes_leading_remove(LongInt number) {
long long zeroes_leading_border = number._digits.size() - 1;
for (long long i = 0; i < number._digits.size() - 1; i = i + 1) {
if (number._digits[i] != 0) {
zeroes_leading_border = i;
break;
}
}
number._digits.erase(number._digits.begin() + 0, number._digits.begin() + zeroes_leading_border);
return number;
}
LongInt LongInt::_shift_right(LongInt number, long long shift_power) {
number._digits.reserve(shift_power);
for (long long i = 0; i < shift_power; i = i + 1) {
number._digits.insert(number._digits.begin() + 0, 0);
}
return number;
}
LongInt LongInt::_shift_left(LongInt number, long long shift_power) {
if (number == 0) {
return number;
}
number._digits.reserve(shift_power);
for (long long i = 0; i < shift_power; i = i + 1) {
number._digits.push_back(0);
}
return number;
}
LongInt LongInt::abs(LongInt number_first) {
number_first._natural = true;
return number_first;
}
bool LongInt::even(LongInt number) {
if (number._digits[number._digits.size() - 1] % 2 == 0) {
return true;
}
return false;
}
bool LongInt::odd(LongInt number) {
return (LongInt::even(number) == false);
}
char LongInt::sign(const LongInt& number) {
if (number._natural == true) {
return '+';
}
return '-';
}
LongInt LongInt::max(LongInt number_first, LongInt number_second) {
if (number_first > number_second) {
return number_first;
}
return number_second;
}
LongInt LongInt::min(LongInt number_first, LongInt number_second) {
if (number_first < number_second) {
return number_first;
}
return number_second;
}Функции очень просты и в пояснении, надеюсь, не нуждаются.
Теперь перейдем уже к более интересной вещи: к сравнению. Основная идея сравнения. Сначала пытаемся определить какое число больше по знаку, потом — по разрядности, а уже потом если ничего из первых двух проверок не дало однозначного результата — проходим по разрядам. Полноценно реализовано будет только два оператора сравнения, остальные будут выведены на их основе.
bool operator ==(LongInt number_first, LongInt number_second) {
if (number_first._natural != number_second._natural) {
return false;
}
if (number_first._digits.size() != number_second._digits.size()) {
return false;
}
for (long long numbers_position = 0; numbers_position < number_first._digits.size(); numbers_position = numbers_position + 1) {
if (number_first._digits[numbers_position] != number_second._digits[numbers_position]) {
return false;
}
}
return true;
}
bool operator !=(LongInt number_first, LongInt number_second) {
return (number_first == number_second == false);
}
bool operator >(LongInt number_first, LongInt number_second) {
if (number_first == number_second) {
return false;
}
if (number_first._natural == true and number_second._natural == false) {
return true;
}
if (number_first._natural == false and number_second._natural == true) {
return false;
}
if (number_first._natural == false and number_second._natural == false) {
number_first._natural = true;
number_second._natural = true;
return (number_first > number_second == false);
}
if (number_first._digits.size() > number_second._digits.size()) {
return true;
}
if (number_first._digits.size() < number_second._digits.size()) {
return false;
}
for (long long numbers_position = 0; numbers_position < number_first._digits.size(); numbers_position = numbers_position + 1) {
if (number_first._digits[numbers_position] > number_second._digits[numbers_position]) {
return true;
}
if (number_first._digits[numbers_position] < number_second._digits[numbers_position]) {
return false;
}
}
return false;
}
bool operator <(const LongInt& number_first, const LongInt& number_second) {
if (number_first != number_second and (number_first > number_second == false)) {
return true;
}
return false;
}
bool operator >=(const LongInt& number_first, const LongInt& number_second) {
if (number_first > number_second or number_first == number_second) {
return true;
}
return false;
}
bool operator <=(const LongInt& number_first, const LongInt& number_second) {
if (number_first < number_second or number_first == number_second) {
return true;
}
return false;
}Теперь напишем оператор сложения ну и соотвественно операторы +=, ++ и так далее.
LongInt operator +(LongInt number_first, LongInt number_second) {
if (number_first._natural == true and number_second._natural == false) {
number_second._natural = true;
return number_first - number_second;
}
if (number_first._natural == false and number_second._natural == true) {
number_first._natural = true;
return number_second - number_first;
}
if (number_first._natural == false and number_second._natural == false) {
number_second._natural = true;
}
if (number_first._digits.size() > number_second._digits.size()) {
number_second = LongInt::_shift_right(number_second, number_first._digits.size() - number_second._digits.size());
}
else {
number_first = LongInt::_shift_right(number_first, number_second._digits.size() - number_first._digits.size());
}
int sum;
int in_mind = 0;
for (long long numbers_position = number_first._digits.size() - 1; numbers_position >= 0; numbers_position = numbers_position - 1) {
sum = number_first._digits[numbers_position] + number_second._digits[numbers_position] + in_mind;
in_mind = sum / LongInt::_base;
number_first._digits[numbers_position] = sum % LongInt::_base;
}
if (in_mind != 0) {
number_first._digits.insert(number_first._digits.begin() + 0, in_mind);
}
return number_first;
}
LongInt LongInt::operator +=(LongInt number) {
return *this = *this + std::move(number);
}
LongInt LongInt::operator ++() {
return *this = *this + 1;
}
LongInt LongInt::operator ++(int) {
*this = *this + 1;
return *this = *this - 1;
}Из-за большого количества сценариев, зависящих от знака входных чисел, пришлось писать много кода. Для сложения используется обычный алгоритм сложения в столбик, с которым все, смею предположить, знакомы.
Теперь время операторов вычитания и его подобных.
LongInt operator -(LongInt number_first, LongInt number_second) {
if (number_first._natural == true and number_second._natural == false) {
number_second._natural = true;
return number_first + number_second;
}
if (number_first._natural == false and number_second._natural == true) {
number_first._natural = true;
LongInt tmp = number_first + number_second;
tmp._natural = false;
return tmp;
}
if (number_first._natural == false and number_second._natural == false) {
number_first._natural = true;
number_second._natural = true;
LongInt tmp;
tmp = number_first;
number_first = number_second;
number_second = tmp;
}
if (number_first < number_second) {
LongInt tmp = number_first;
number_first = number_second;
number_second = tmp;
number_first._natural = false;
}
number_second = LongInt::_shift_right(number_second, number_first._digits.size() - number_second._digits.size());
int different;
for (long long numbers_position1 = number_first._digits.size() - 1; numbers_position1 >= 0; numbers_position1 = numbers_position1 - 1) {
different = number_first._digits[numbers_position1] - number_second._digits[numbers_position1];
if (different >= 0) {
number_first._digits[numbers_position1] = different;
}
else {
number_first._digits[numbers_position1] = different + LongInt::_base;
for (long long numbers_position2 = numbers_position1 - 1; true; numbers_position2 = numbers_position2 - 1) {
if (number_first._digits[numbers_position2] == 0) {
number_first._digits[numbers_position2] = LongInt::_base - 1;
}
else {
number_first._digits[numbers_position2] = number_first._digits[numbers_position2] - 1;
break;
}
}
}
}
return LongInt::_zeroes_leading_remove(number_first);
}
LongInt LongInt::operator -=(LongInt number) {
return *this = *this - std::move(number);
}
LongInt LongInt::operator --() {
return *this = *this - 1;
}
LongInt LongInt::operator --(int) {
*this = *this - 1;
return *this = *this + 1;
}Вычитание работает немного труднее, но в целом это то же примитивное вычитание в столбик.
Теперь настало время одной из самых интересных частей статьи. А именно — умножения. Будет использоваться алгоритм Анатолия Алексеевича Карацубы. Это не очень сложный алгоритм, он основан на парадигме «разделяй и влавствуй». Если кто не знаком с этим алгоритмом, то можете ознакомиться со статьей на Википедии. Обратите внимание, что из-за рекурсии алгоритм необходимо разделить на две части.
LongInt LongInt::_multiply_karatsuba(LongInt number_first, LongInt number_second) {
if (std::min(number_first._digits.size(), number_second._digits.size()) <= _length_maximum_for_default_multiply) {
number_first = LongInt::_zeroes_leading_remove(number_first);
number_second = LongInt::_zeroes_leading_remove(number_second);
LongInt result;
result._digits.resize(number_first._digits.size() + number_second._digits.size());
long long composition;
for (long long number_first_position = number_first._digits.size() - 1; number_first_position >= 0; number_first_position = number_first_position - 1) {
for (long long number_second_position = number_second._digits.size() - 1; number_second_position >= 0; number_second_position = number_second_position - 1) {
composition = (long long)number_first._digits[number_first_position] * (long long)number_second._digits[number_second_position] + result._digits[number_first_position + number_second_position + 1];
result._digits[number_first_position + number_second_position + 1] = composition % LongInt::_base;
result._digits[number_first_position + number_second_position + 1 - 1] = result._digits[number_first_position + number_second_position + 1 - 1] + (composition / LongInt::_base);
}
}
return LongInt::_zeroes_leading_remove(result);
}
if (number_first._digits.size() % 2 != 0) {
number_first._digits.insert(number_first._digits.begin() + 0, 0);
}
if (number_second._digits.size() % 2 != 0) {
number_second._digits.insert(number_second._digits.begin() + 0, 0);
}
if (number_first._digits.size() > number_second._digits.size()) {
number_second = LongInt::_shift_right(number_second, number_first._digits.size() - number_second._digits.size());
}
else {
number_first = LongInt::_shift_right(number_first, number_second._digits.size() - number_first._digits.size());
}
long long numbers_size = number_first._digits.size();
long long numbers_part_size = numbers_size / 2;
LongInt number_first_part_left;
LongInt number_first_part_right;
LongInt number_second_part_left;
LongInt number_second_part_right;
number_first_part_left._digits.resize(0);
number_first_part_right._digits.resize(0);
number_second_part_left._digits.resize(0);
number_second_part_right._digits.resize(0);
number_first_part_left._digits.reserve(numbers_part_size);
number_first_part_right._digits.reserve(numbers_part_size);
number_second_part_left._digits.reserve(numbers_part_size);
number_second_part_right._digits.reserve(numbers_part_size);
for (long long i = 0; i < numbers_part_size; i = i + 1) {
number_first_part_left._digits.push_back(number_first._digits[i]);
number_second_part_left._digits.push_back(number_second._digits[i]);
}
for (long long i = numbers_part_size; i < numbers_size; i = i + 1) {
number_first_part_right._digits.push_back(number_first._digits[i]);
number_second_part_right._digits.push_back(number_second._digits[i]);
}
LongInt product_first = LongInt::_multiply_karatsuba(number_first_part_left, number_second_part_left);
LongInt product_second = LongInt::_multiply_karatsuba(number_first_part_right, number_second_part_right);
LongInt product_third = LongInt::_multiply_karatsuba(LongInt::_zeroes_leading_remove(number_first_part_left) + LongInt::_zeroes_leading_remove(number_first_part_right), LongInt::_zeroes_leading_remove(number_second_part_left) + LongInt::_zeroes_leading_remove(number_second_part_right));
return LongInt::_shift_left(product_first, numbers_size) + LongInt::_shift_left(product_third - product_first - product_second, numbers_part_size) + product_second;
}
LongInt operator *(const LongInt& number_first, const LongInt& number_second) {
LongInt result = LongInt::_multiply_karatsuba(number_first, number_second);
result._natural = (number_first._natural == number_second._natural);
return result;
}
LongInt LongInt::operator *=(const LongInt& number) {
return *this = *this * number;
}Теперь предлагаю разобрать, что именно мы написали. После вызова оператора умножения мы сразу запускаем рекурсивный алгоритм, а после рекурсии определяем знак числа. Далее просто возвращаем результат. Но самое интересное в этом блоке кода именно рекурсивный алгоритм, перейдем к нему. Сразу после запуска функции мы проверяем минимальную длину входных чисел. Если она меньше или равна 256 (такое значение по умолчанию, на своем железе я протестировал и 256 оказалось оптимальным вариантом), то удаляем лидирующие нули (ибо такие могут быть и скоро вы поймете почему) и умножаем банально в столбик. Однако почему мы используем алгоритм умножения в столбик? А потому, что алгоритм Карацубы дает преимущество только на больших числах из-за лишних затрат на сложение, вычитание, сдвиги и так далее. Далее, если код продолжается, то очевидно, что числа здоровенные. Дополняем их длину до четной, после чего равняем. Нам это понадобится. Делим два числа на равные части (именно для этого нужны были дополнения нолями), после чего рекурсивно согласно алгоритму Карацубы перемножаем. Далее возвращаем результат.
Далее у нас на очереди деление нацело. В этом алгоритме ничего примечательного нет, стандартное деление уголком. Единственное, что хочется отметить — так это то, что для поиска некоторого «промежуточного делимого» будет использоваться бинарный поиск. Кто не знает, что такое бинарный поиск — можете мельком глянуть статью на Википедии.
LongInt operator /(LongInt number_first, LongInt number_second) {
LongInt result;
result._natural = (number_first._natural == number_second._natural);
LongInt number_first_part;
number_first_part._natural = true;
number_first._natural = true;
number_second._natural = true;
if (number_second == 0) {
throw "Fatal error. Division whole is impossible. Attempt to divide by zero.";
}
if (number_first < number_second) {
return 0;
}
result._digits.resize(0);
number_first_part._digits.resize(0);
int quotient;
int left;
int middle;
int right;
LongInt tmp;
for (long long number_first_position = 0; number_first_position < number_first._digits.size(); number_first_position = number_first_position + 1) {
number_first_part._digits.push_back(number_first._digits[number_first_position]);
quotient = 0;
left = 0;
right = LongInt::_base;
while (left <= right) {
middle = (left + right) / 2;
tmp = number_second * middle;
if (tmp <= number_first_part) {
quotient = middle;
left = middle + 1;
}
else {
right = middle - 1;
}
}
number_first_part = number_first_part - (number_second * quotient);
if (!result._digits.empty() or quotient != 0) {
result._digits.push_back(quotient);
}
if (number_first_part == 0) {
number_first_part._digits.resize(0);
}
}
return result;
}
LongInt LongInt::operator /=(LongInt number) {
return *this = *this / std::move(number);
}Получение остатка от деления почти не отличается от деления нацело. Единственное, что стоит заметить, так это то, что остаток, согласно математическим правилам всегда натурален.
LongInt operator %(LongInt number_first, LongInt number_second) {
LongInt number_first_part;
number_first_part._natural = true;
number_first._natural = true;
number_second._natural = true;
if (number_second == 0) {
throw "Fatal error. Division remainder calculation is impossible. Attempt to divide by zero.";
}
if (number_first < number_second) {
return number_first;
}
number_first_part._digits.resize(0);
int quotient;
int left;
int middle;
int right;
LongInt tmp;
for (long long number_first_position = 0; number_first_position < number_first._digits.size(); number_first_position = number_first_position + 1) {
number_first_part._digits.push_back(number_first._digits[number_first_position]);
quotient = 0;
left = 0;
right = LongInt::_base;
while (left <= right) {
middle = (left + right) / 2;
tmp = number_second * middle;
if (tmp <= number_first_part) {
quotient = middle;
left = middle + 1;
}
else {
right = middle - 1;
}
}
number_first_part = number_first_part - (number_second * quotient);
if (number_first_part == 0) {
number_first_part._digits.resize(0);
}
}
if (number_first_part._digits.empty()) {
return 0;
}
return number_first_part;
}
LongInt LongInt::operator %=(LongInt number) {
return *this = *this % std::move(number);
}Теперь на очереди более приятные и простые вещи. Возведение в степень. Использываться будет один из алгоритмов быстрого возведения в степень. Наверняка вы с ними знакомы, но если нет — их описание можно также найти на Википедии. Обращаю внимание, что ноль нельзя возвести в нулевую степень.
LongInt LongInt::pow(LongInt number_first, LongInt number_second) {
if (number_first == 0 and number_second == 0) {
throw "Fatal error. Pow calculation is impossible. It is impossible to raise zero to zero degree.";
}
if (number_second < 0) {
throw "Fatal error. Pow calculation is impossible. This class only support whole numbers, so erection to negative degree is impossible.";
}
LongInt result = 1;
while (number_second != 0) {
if (even(number_second)) {
number_second = number_second / 2;
number_first = number_first * number_first;
}
else {
number_second = number_second - 1;
result = result * number_first;
}
}
return result;
}Теперь расчет факториала. Казалось бы: все просто. Нужно только перемножить числа от 1 до n. Но все-таки не так все и просто. Дело в том, что просто перемножая числа от 1 до n мы будем работать с числами резко отличающейся длины, а это режет производительность. Поэтому, мы будем использовать алгоритм поиска факториала «деревом». Он основан на том, что мы добиваемся того, что умножаем числа всегда приблизительно равной длины. Статьи на Википедии по этой теме нет, но для 10! это работает примерно так:
Теперь, реализация. Обратите внимание, что алгоритм разделен на две части из-за рекурсии, а также на то, что функция факториала определена только для натуральных чисел.
LongInt LongInt::_factorial_tree(LongInt number_first, const LongInt& number_second) {
if (number_first > number_second) {
return 1;
}
if (number_first == number_second) {
return number_first;
}
if (number_second - number_first == 1) {
return number_first * number_second;
}
LongInt tmp = (number_first + number_second) / 2;
return LongInt::_factorial_tree(number_first, tmp) * LongInt::_factorial_tree(tmp + 1, number_second);
}
LongInt LongInt::factorial(LongInt number) {
if (number < 1) {
throw "Fatal error. Factorial calculation is impossible. Factorial is defined only for _natural numbers.";
}
if (number == 1 or number == 2) {
return number;
}
return _factorial_tree(2, number);
}Далее у нас функции подсчета НОД и НОК. Использовать мы будем алгоритм Евклида. Информацию об алгоритме Евклида также можно найти в Википедии. Обратите внимание, что результат НОД и НОК всегда положительный, а также, что нельзя посчитать НОД или НОК, если одно или несколько чисел — ноль.
LongInt LongInt::gcd(LongInt number_first, LongInt number_second) {
if (number_first == 0 or number_second == 0) {
throw "Fatal error. Gcd calculation is impossible. One of the numbers is zero.";
}
number_first._natural = true;
number_second._natural = true;
while (number_first != 0 and number_second != 0) {
if (number_first > number_second) {
number_first = number_first % number_second;
}
else {
number_second = number_second % number_first;
}
}
return number_first + number_second;
}
LongInt LongInt::lcm(LongInt number_first, LongInt number_second) {
if (number_first == 0 or number_second == 0) {
throw "Fatal error. Lcm calculation is impossible. One of the numbers is zero.";
}
number_first._natural = true;
number_second._natural = true;
return number_first * number_second / LongInt::gcd(number_first, number_second);
}Теперь, последняя пара функций. Извлечение целого квадратного и целого кубического корня. Для целого квадратного корня можно посмотреть ту же Википедию, а для кубического статьи нет, но он очень похож на целый квадратный корень. Данные операции могут понадобиться, например, при проверке на простоту. Для того и того мы будем использовать бинарный поиск. Так же, стоит заметить, что квадратный корень от отрицательных чисел не имеет решения.
LongInt LongInt::sqrt(const LongInt& number) {
if (number._natural == false) {
throw "Fatal error. Sqrt calculation is impossible. Sqrt operation over negative numbers has no result.";
}
if (number == 0) {
return number;
}
LongInt left = 1;
LongInt right = number / 2 + 1;
LongInt middle;
LongInt result;
while (left <= right) {
middle = left + (right - left) / 2;
if (middle <= number / middle) {
left = middle + 1;
result = middle;
}
else {
right = middle - 1;
}
}
return result;
}
LongInt LongInt::cbrt(LongInt number) {
if (number == 0) {
return number;
}
bool result_natural = number._natural;
number._natural = true;
LongInt left = 1;
LongInt right = number / 2 + 1;
LongInt middle;
LongInt result;
while (left <= right) {
middle = left + (right - left) / 2;
if (middle <= number / (middle * middle)) {
left = middle + 1;
result = middle;
}
else {
right = middle - 1;
}
}
result._natural = result_natural;
return result;
}На этом реализация функций подошла к концу, осталось лишь накидать демонстрационную программу и замерить производительность.
Вот файл демонстрационной программы. Ничего объяснять, думаю, тут не надо — программа элементарна.
#include
#include "LongInt.hpp"
int main() {
std::string number_first_string;
std::string number_second_string;
std::string action;
LongInt number_first;
LongInt number_second;
long double time_start;
long double time_end;
LongInt result_longint;
bool result_bool;
char result_char;
std::cout << "1| Сложение двух целых чисел." << std::endl;
std::cout << "2| Вычитание из целого числа целое число." << std::endl;
std::cout << "3| Умножение двух целых чисел." << std::endl;
std::cout << "4| Деление нацело двух целых чисел." << std::endl;
std::cout << "5| Получения остатка от деления двух целых чисел." << std::endl;
std::cout << "6| Возведение целого числа в целую неотрицательную степень." << std::endl;
std::cout << "7| Подсчет факториала от натурального числа." << std::endl;
std::cout << "8| Подсчет НОД двух целых чисел." << std::endl;
std::cout << "9| Подсчет НОК двух целых чисел." << std::endl;
std::cout << "10| Получение модуля целого числа." << std::endl;
std::cout << "11| Получение знака целого числа." << std::endl;
std::cout << "12| Быстрая проверка целого числа на четность." << std::endl;
std::cout << "13| Быстрая проверка целого числа на нечетность." << std::endl;
std::cout << "14| Получение максимального из двух целых чисел." << std::endl;
std::cout << "15| Получение минимального из двух целых чисел." << std::endl;
std::cout << "16| Извлечение целого квадратного корня из целого неотрицательного числа." << std::endl;
std::cout << "17| Извлечение целого кубического корня из целого числа." << std::endl;
std::cout << "18| Выход." << std::endl;
for (; ;) {
std::cout << std::endl;
std::cout << std::endl;
std::cout << "Выберите операцию: ";
getline(std::cin, action);
if (action == "1") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = number_first + number_second;
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "2") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = number_first - number_second;
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "3") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = number_first * number_second;
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "4") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = number_first / number_second;
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "5") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = number_first % number_second;
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "6") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = LongInt::pow(number_first, number_second);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "7") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_longint = LongInt::factorial(number_first);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "8") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = LongInt::gcd(number_first, number_second);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "9") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = LongInt::lcm(number_first, number_second);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "10") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_longint = LongInt::abs(number_first);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "11") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_char = LongInt::sign(number_first);
std::cout << "Результат: " << result_char << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "12") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_bool = LongInt::even(number_first);
std::cout << "Результат: " << result_bool << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "13") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_bool = LongInt::odd(number_first);
std::cout << "Результат: " << result_bool << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "14") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = LongInt::max(number_first, number_second);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "15") {
std::cout << "Введите первое число: ";
getline(std::cin, number_first_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = clock();
number_first = number_first_string;
number_second = number_second_string;
result_longint = LongInt::min(number_first, number_second);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "16") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_longint = LongInt::sqrt(number_first);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "17") {
std::cout << "Введите число: ";
getline(std::cin, number_first_string);
time_start = clock();
number_first = number_first_string;
result_longint = LongInt::cbrt(number_first);
std::cout << "Результат: " << result_longint << "." << std::endl;
time_end = clock();
std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / CLOCKS_PER_SEC << " секунд(а/ы)." << std::endl;
}
else if (action == "18") {
break;
}
else {
std::cout << "Неизвестный номер команды. Введите число от 1 до 18." << std::endl;
}
}
return 0;
} Все файлы готовы — теперь можно со спокойной душой компилировать. Теперь надо протестировать скорость работы полученного нами творения. Тесты будут проводиться на моем ноутбуке, вот подробная информация:
Операционная система: | Debian GNU/Linux 11 Bullseye |
Компилятор: | gcc 10.2.1 |
Процессор: | Intel Core i5–8250U |
Оперативная память: | 8GB |
Время затраченное на возведение 2 в 1000000 степень (в секундах): | 1.63 |
Время затраченное на подсчет факториала от 100000 (в секундах): | 14.91 |
Производительность не такая уж и плохая. Естественно, мы не перегнали какую-нибудь професиональную библиотеку вроде GNU Multi-Precision Library в 1000000 раз, не устроили революцию в области математики, но в то же время получилась (на мой вгляд) относительно неплохая и задокументированная (как никак) реализация.
Спасибо за чтение. Полный код можно
