Как стать автором
Обновить

Работа с очень длинными числами на C++

C++ *Алгоритмы *
Из песочницы
Tutorial

Недавно я решил написать свою собственную реализацию длинной арифметики для C++. Делал просто для себя, ибо эта тема мне кажется довольно интересной. Поставил перед собой следующие задачи:

  1. Реализация должна быть шустрой. Я, к сожалению, пока не обладаю знаниями высшей математики, но пользоваться интернетом умею и постарался интегрировать в программу все, что только смог найти.

  2. Реализация должна быть экономна к памяти. Понятное дело, что многопоточность и алгоритмы умножения вроде Карацубы подъедают память, но все-таки должен быть разумный предел.

  3. Код должен быть относительно чистым, а то, как пользоваться классом - должно быть понятно и похоже на способы работы с обычными int-овыми числами.

  4. Код должен содержать необходимый набор функций, чтобы используя его можно было спокойно проводить проверки на простоту и выполнять некоторые другие необходимые и популярные операции.

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

Реализовывать буду знаковую целочисленную арифметику. Запаситесь провизией, поскольку рассказ будет долгий.

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

../examples/main.cpp (некий демонстрационный калькулятор, демонстрирующий функционал)
../src/LongInt.hpp (заголовок класса)
../src/Conversation.cpp (объекты класса, отвечающие за конвертацию типов)
../src/Compare.cpp (объекты класса, отвечающие за сравнение)
../src/Primitive.cpp (объекты класса, отвечающие за примитивные операции)
../src/Sum.cpp (объекты класса, отвечающие за сложение)
../src/Subtraction.cpp (объекты класса, отвечающие за вычитание)
../src/Multiply.cpp (объекты класса, отвечающие за умножение)
../src/Division.cpp (объекты класса, отвечающие за деление)
../src/Pow.cpp (объекты класса, отвечающие за возведение в степень)
../src/Factorial.cpp (объекты класса, отвечающие за подсчет факториала)
../src/Gcd.cpp (объекты класса, отвечающие за подсчет НОД)
../src/Lcm.cpp (объекты класса, отвечающие за подсчет НОК)
../src/Isqrt.cpp (объекты класса, отвечающие за извлечение целого квадратного корня)
../src/Icbrt.cpp (объекты класса, отвечающие за извлечение целого кубического корня)
../src/Random.cpp (объекты класса, отвечающие за генерацию длинных псевдослучайных чисел заданной длины)
../CMakeLists.txt (инструкции компиляции)

Файл с инструкциями компиляции напишем сразу.

Во-первых, подключим потоки. Это понадобится, ибо некоторые попытки что-либо распараллелить тут будут задействованы.

Во-вторых, активируем флаг Werror дабы код был чище (флаг Werror отвечает за то, чтобы все предупреждения компилятора прерывали процесс компиляции, это помогает заранее устранять зоопарк в коде).

cmake_minimum_required(VERSION 3.20)
project(LongInt)
set(CMAKE_CXX_STANDARD 14)
add_executable(LongInt ../examples/main.cpp ../src/LongInt.hpp ../src/Conversation.cpp ../src/Compare.cpp ../src/Primitive.cpp ../src/Sum.cpp ../src/Subtraction.cpp ../src/Multiply.cpp ../src/Division.cpp ../src/Pow.cpp ../src/Factorial.cpp ../src/Gcd.cpp ../src/Lcm.cpp ../src/Isqrt.cpp ../src/Icbrt.cpp ../src/Random.cpp)
add_definitions(-Werror)
find_package(Threads REQUIRED)
target_link_libraries(LongInt Threads::Threads)

Файл с демонстрационным калькулятором пока пропустим, ибо сначала надо реализовать сам класс.

Делаем файл с заголовком класса:

#include <iostream>
#include <vector>


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);
    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);
    static LongInt abs(LongInt number_first);
    static bool even(LongInt number);
    static bool odd(LongInt number);
    static long long size(LongInt number);
    static LongInt max(LongInt number_first, LongInt number_second);
    static LongInt min(LongInt number_first, 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 isqrt(const LongInt& number);
    static LongInt icbrt(LongInt number);
    static LongInt random(long long number_length);
private:
    std::vector<int> _digits;
    bool _sign;
    static const int _base = 1000000000;
    static const int _base_length = 9;
    static const int _length_maximum_for_default_multiply = 256;
    static std::vector<int> _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, bool iteration_thirst);
    static LongInt _factorial_tree(LongInt number_first, const LongInt& number_second);
};

Тут, надо обратить внимание на несколько моментов. Сами разряды числа будут храниться в векторе _digits с указанной системой счисления.

В переменной _sign будет храниться знак числа. True - если знак + (иными словами >= 0), false - если знак - (иными словами < 0).

В переменной _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 будет храниться значение до которого используется стандартное умножение в столбик, а не более быстрый алгоритм Анатолия Алексеевича Карацубы, но к этому мы еще вернемся.

Теперь приступим к самой тяжелой части кода - написания самих исходников объектов класса. Для начала, напишем файл с исходниками конвертации типов.

#include "LongInt.hpp"


std::vector<int> LongInt::_string_convert_to_vector(const std::string& string) {
    std::vector<int> 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 - _base_length + 1, _base_length));
        }
    }
    return result;
}
LongInt::LongInt() {
    _digits.resize(1);
    _sign = true;
}
LongInt::LongInt(std::string string) {
    if (string.empty() or (string.size() == 1 and string[0] == '-')) {
        throw "Fatal error. Cannot create type. String does not contain a number.";
    }
    if (string.front() == '-') {
        string.erase(string.begin());
        _sign = false;
    }
    else {
        _sign = true;
    }
    for (long long i = 0; i < string.size(); i = i + 1) {
        if (string[i] < 48 or string[i] > 57) {
            throw "Fatal error. Cannot create type. String contains unknown characters.";
        }
    }
    while (string.size() != 1 and string.front() == '0') {
        string.erase(string.begin());
    }
    _digits = LongInt::_string_convert_to_vector(string);
}
LongInt::LongInt(signed int number) {
    std::string string = std::to_string(number);
    if (string.front() == '-') {
        string.erase(string.begin());
        _sign = false;
    }
    else {
        _sign = true;
    }
    _digits = LongInt::_string_convert_to_vector(string);
}
LongInt::LongInt(unsigned int number) {
    _sign = true;
    _digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(signed long number) {
    std::string string = std::to_string(number);
    if (string.front() == '-') {
        string.erase(string.begin());
        _sign = false;
    }
    else {
        _sign = true;
    }
    _digits = LongInt::_string_convert_to_vector(string);
}
LongInt::LongInt(unsigned long number) {
    _sign = true;
    _digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
LongInt::LongInt(signed long long number) {
    std::string string = std::to_string(number);
    if (string.front() == '-') {
        string.erase(string.begin());
        _sign = false;
    }
    else {
        _sign = true;
    }
    _digits = LongInt::_string_convert_to_vector(string);
}
LongInt::LongInt(unsigned long long number) {
    _sign = true;
    _digits = LongInt::_string_convert_to_vector(std::to_string(number));
}
std::string LongInt::to_string(LongInt number) {
    if (number._digits.size() == 1 and number._digits.front() == 0) {
        return "0";
    }
    std::string result;
    if (!number._sign) {
        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');
        }
        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;
}

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

Единственное, что важно подчеркнуть в конвертации в строку, что дополнение нулями до текущей базы не происходит на первом разряде числа. Как это объяснить - не знаю, но на опытах было выявленно, что дополнять нулями надо все разряды кроме первого.

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

#include <algorithm>
#include "LongInt.hpp"


bool operator ==(LongInt number_first, LongInt number_second) {
    if (number_first._sign != number_second._sign) {
        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 !(std::move(number_first) == std::move(number_second));
}
bool operator >(LongInt number_first, LongInt number_second) {
    if (number_first == number_second) {
        return false;
    }
    if (number_first._sign and !number_second._sign) {
        return true;
    }
    if (!number_first._sign and number_second._sign) {
        return false;
    }
    if (!number_first._sign and !number_second._sign) {
        number_first._sign = true;
        number_second._sign = true;
        return !(number_first > number_second);
    }
    if (number_first._digits.size() > number_second._digits.size()) {
        return true;
    }
    if (number_first._digits.size() < number_second._digits.size()) {
        return false;
    }
    return !(std::lexicographical_compare(number_first._digits.begin(), number_first._digits.end(), number_second._digits.begin(), number_second._digits.end()));
}
bool operator <(const LongInt& number_first, const LongInt& number_second) {
    if (number_first != number_second and !(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;
}
bool operator <=(const LongInt& number_first, const LongInt& number_second) {
    if (number_first < number_second or number_first == number_second) {
        return true;
    }
    return false;
}

Теперь напишем файл с примитивными функциями. Эти функции понадобятся при реализации более сложных операций. Функции очень простые и в пояснении, надеюсь, не нуждаются.

#include "LongInt.hpp"


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(), 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);
    }
    return number;
}
LongInt LongInt::_shift_left(LongInt number, long long shift_power) {
    if (number == 0) {
        return number;
    }
    number._digits.resize(number._digits.size() + shift_power);
    return number;
}
LongInt LongInt::abs(LongInt number_first) {
    number_first._sign = true;
    return number_first;
}
bool LongInt::even(LongInt number) {
    if (number._digits.back() % 2 == 0) {
        return true;
    }
    return false;
}
bool LongInt::odd(LongInt number) {
    return !LongInt::even(std::move(number));
}
long long LongInt::size(LongInt number) {
    return (((long long)number._digits.size() - (long long)1) * (long long)_base_length) + (long long)std::to_string(number._digits.front()).size();
}
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;
}

Теперь напишем файл со сложением.

#include "LongInt.hpp"


LongInt operator +(LongInt number_first, LongInt number_second) {
    if (number_first._sign and !number_second._sign) {
        number_second._sign = true;
        return number_first - number_second;
    }
    if (!number_first._sign and number_second._sign) {
        number_first._sign = true;
        return number_second - number_first;
    }
    if (!number_first._sign and !number_second._sign) {
        number_second._sign = 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(), 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;
}

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

Теперь время файла с вычитанием.

#include "LongInt.hpp"


LongInt operator -(LongInt number_first, LongInt number_second) {
    if (number_first._sign and !number_second._sign) {
        number_second._sign = true;
        return number_first + number_second;
    }
    if (!number_first._sign and number_second._sign) {
        number_first._sign = true;
        LongInt tmp = number_first + number_second;
        tmp._sign = false;
        return tmp;
    }
    if (!number_first._sign and !number_second._sign) {
        number_first._sign = true;
        number_second._sign = 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._sign = 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;
}

Вычитание работает немного труднее, но в целом это то же примитивное вычитание в столбик.

Теперь настало время одной из самых интересных частей статьи. А именно - умножения. Будет использоваться алгоритм Анатолия Алексеевича Карацубы (см. Алгоритм Карацубы). Это не очень сложный алгоритм, он основан на парадигме "разделяй и влавствуй". Обратите внимание, что из-за рекурсии алгоритм необходимо разделить на две части. Вот файл с умножением:

#include <future>
#include "LongInt.hpp"


LongInt LongInt::_multiply_karatsuba(LongInt number_first, LongInt number_second, bool iteration_thirst) {
    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] = result._digits[number_first_position + number_second_position] + (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);
    }
    if (number_second._digits.size() % 2 != 0) {
        number_second._digits.insert(number_second._digits.begin(), 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(numbers_part_size);
    number_first_part_right._digits.resize(numbers_part_size);
    number_second_part_left._digits.resize(numbers_part_size);
    number_second_part_right._digits.resize(numbers_part_size);
    std::copy(number_first._digits.begin(), number_first._digits.begin() + numbers_part_size, number_first_part_left._digits.begin());
    std::copy(number_second._digits.begin(), number_second._digits.begin() + numbers_part_size, number_second_part_left._digits.begin());
    std::copy(number_first._digits.begin() + numbers_part_size, number_first._digits.begin() + numbers_size, number_first_part_right._digits.begin());
    std::copy(number_second._digits.begin() + numbers_part_size, number_second._digits.begin() + numbers_size, number_second_part_right._digits.begin());
    LongInt product_first;
    LongInt product_second;
    LongInt product_third;
    if (iteration_thirst and std::thread::hardware_concurrency() >= 3) {
        auto thread_first = std::async(LongInt::_multiply_karatsuba, number_first_part_left, number_second_part_left, false);
        auto thread_second = std::async(LongInt::_multiply_karatsuba, number_first_part_right, number_second_part_right, false);
        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), false);
        product_first = thread_first.get();
        product_second = thread_second.get();
    }
    else if (iteration_thirst and std::thread::hardware_concurrency() == 2) {
        auto thread_first = std::async(LongInt::_multiply_karatsuba, number_first_part_left, number_second_part_left, false);
        product_second = LongInt::_multiply_karatsuba(number_first_part_right, number_second_part_right, false);
        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), false);
        product_first = thread_first.get();
    }
    else {
        product_first = LongInt::_multiply_karatsuba(number_first_part_left, number_second_part_left, false);
        product_second = LongInt::_multiply_karatsuba(number_first_part_right, number_second_part_right, false);
        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), false);
    }
    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, true);
    result._sign = (number_first._sign == number_second._sign);
    return result;
}
LongInt LongInt::operator *=(const LongInt& number) {
    return *this = *this * number;
}

Теперь предлагаю разобрать, что именно мы написали. После вызова оператора умножения мы сразу запускаем рекурсивный алгоритм, а после рекурсии определяем знак числа. Далее просто возвращаем результат. Но самое интересное в этом блоке кода именно рекурсивный алгоритм, перейдем к нему. Сразу после запуска функции мы проверяем минимальную длину входных чисел. Если она меньше или равна 256 (такое значение по умолчанию, на своем железе я протестировал и 256 оказалось оптимальным вариантом), то удаляем лидирующие нули (ибо такие могут быть и скоро вы поймете почему) и умножаем банально в столбик. Однако почему мы используем алгоритм умножения в столбик? А потому, что алгоритм Карацубы дает преимущество только на больших числах из-за лишних затрат на сложение, вычитание, сдвиги и так далее. Далее, если код продолжается, то очевидно, что числа здоровенные. Дополняем их длину до четной, после чего равняем. Нам это понадобится. Делим два числа на равные части (именно для этого нужны были дополнения нолями), после чего рекурсивно, согласно алгоритму Карацубы, перемножаем. Тут надо обратить внимание на один момент. Если это первый рекурсивный вызов, то рекурсивные умножения делаются не последовательно, а параллельно. Многопоточные вычисления накладывают дополнительные расходы, но возможность использовать три потока вместо одного эти расходы с лихвой компенсирует. Так же стоит заметить, что выполнение параллельных вычислений зависит от потоков CPU.

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

#include "LongInt.hpp"


LongInt operator /(LongInt number_first, LongInt number_second) {
    if (number_second == 0) {
        throw "Fatal error. Whole division is not possible. Zero is specified as the divisor.";
    }
    if (number_second._digits.size() == 1) {
        int number_second_integer = number_second._digits.front();
        int in_mind = 0;
        long long composition;
        for (long long i = 0; i < number_first._digits.size(); i = i + 1) {
            composition = (long long)number_first._digits[i] + (long long)in_mind * (long long)LongInt::_base;
            number_first._digits[i] = composition / number_second_integer;
            in_mind = composition % number_second_integer;
        }
        number_first._sign = (number_first._sign == number_second._sign);
        return LongInt::_zeroes_leading_remove(number_first);
    }
    LongInt result;
    result._sign = (number_first._sign == number_second._sign);
    LongInt number_first_part;
    number_first._sign = true;
    number_second._sign = true;
    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) {
    if (number_second == 0) {
        throw "Fatal error. It is not possible to get the remainder of the division. Zero is specified as the divisor.";
    }
    if (number_second._digits.size() == 1) {
        int number_second_integer = number_second._digits.front();
        int in_mind = 0;
        long long composition;
        for (long long i = 0; i < number_first._digits.size(); i = i + 1) {
            composition = (long long)number_first._digits[i] + (long long)in_mind * (long long)LongInt::_base;
            number_first._digits[i] = composition / number_second_integer;
            in_mind = composition % number_second_integer;
        }
        return in_mind;
    }
    LongInt number_first_part;
    number_first._sign = true;
    number_second._sign = true;
    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);
}

Теперь на очереди более простые вещи. Файл с возведением в степень. Использываться будет один из алгоритмов быстрого возведения в степень. Алгоритм основан на том, что почти все умножения на основание степени можно заменить на возведение в квадрат. Рассмотрим этот вопрос чуть подробнее. Допустим нам надо возвести 2 в 13 степень. Бесппорно, по определению степени, для это достаточно выполнить следующие действия:

2^{13}=2*2*2*2*2*2*2*2*2*2*2*2*2=8192

Мы обошлись 13 умножениями. Однако, возвести 2 в 13 степень можно всего за 5 операций умножения:

2^{13}=2*2^{12}=2*4^6=2*16^3=2*16*16^2=2*16*256=8192

Бесспорно, операции умножения во втором способее тяжелее, но их становится куда меньше, что снижает время возведения в десятки, или даже сотни раз. Помимо этого стоит учитывать, что умножение приблизительно одинаковых чисел работает быстрее, чем умножение большого числа на маленькое, а тут мы как раз большую часть времени считаем квадраты чисел, а не умножаем разжиревшее число на двойки кучу раз, как это было бы с примитивным алгоритмом. Преимущество такого способа на 13 степени заметно не сильно, но если выполнить подобное преобразование, скажем, для тысячной степени, то преимущество будет заметно сразу. Обращаю внимание, что ноль нельзя возвести в нулевую степень.

#include "LongInt.hpp"


LongInt LongInt::pow(LongInt number_first, LongInt number_second) {
    if (number_first == 0 and number_second == 0) {
        throw "Fatal error. Exponentiation is not possible. Cannot raise zero to zero degree.";
    }
    if (number_second < 0) {
        throw "Fatal error. Exponentiation is not possible. Specified number is less than zero.";
    }
    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! это работает примерно так:

Теперь, реализация. Обратите внимание, что алгоритм разделен на две части из-за рекурсии, а также на то, что функция факториала определена только для натуральных чисел.

#include "LongInt.hpp"


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. The factorial calculation from the specified number is not possible. The specified number is less than or equal to zero.";
    }
    if (number == 1 or number == 2) {
        return number;
    }
    return _factorial_tree(2, number);
}

Далее у нас файл с функцией подсчета НОД. Использовать мы будем алгоритм Евклида (см. Алгоритм Евклида). Обратите внимание, что результат этой операции всегда натурален, а также, что нельзя подсчитать НОД если оба числа нули.

#include "LongInt.hpp"


LongInt LongInt::gcd(LongInt number_first, LongInt number_second) {
    if (number_first == 0 and number_second == 0) {
        throw "Fatal error. Counting the greatest common divisor is not possible. Both numbers are zero.";
    }
    number_first._sign = true;
    number_second._sign = true;
    if (number_first == 0) {
        return number_second;
    }
    if (number_second == 0) {
        return number_first;
    }
    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;
}

Далее файл с функцией подсчета НОК. Зная НОД числа найти НОК не составляет труда. Обратите внимание, что нельзя найти НОК если одно из чисел ноль, а также, что НОК всегда натурально.

#include "LongInt.hpp"


LongInt LongInt::lcm(LongInt number_first, LongInt number_second) {
    if (number_first == 0 or number_second == 0) {
        throw "Fatal error. Calculating the least common multiple is not possible. One of the numbers is zero.";
    }
    number_first._sign = true;
    number_second._sign = true;
    return number_first * number_second / LongInt::gcd(number_first, number_second);
}

Теперь файл с функцией извлечения целого квадратного корня. Использоваться будет тот же бинарный поиск. Обратите внимание, что квадратного корня из отрицательного числа не существует.

#include "LongInt.hpp"


LongInt LongInt::isqrt(const LongInt& number) {
    if (!number._sign) {
        throw "Fatal error. Calculating an integer square root is not possible. The square root of the specified number does not exist.";
    }
    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 * middle <= number) {
            left = middle + 1;
            result = middle;
        }
        else {
            right = middle - 1;
        }
    }
    return result;
}

Далее файл с функцией извлечения целого кубического корня. Целый кубический корень находит свое применение в ряде формлул, поэтому, его так же стоит написать. Извлечение целого кубического корня почти не отличается от извлечения целого квадратного корня, единственное, что стоит заметить, что кубический корень от отрицательного числа имеет решение, в отличие от квадратного.

#include "LongInt.hpp"


LongInt LongInt::icbrt(LongInt number) {
    if (number == 0) {
        return number;
    }
    bool result_natural = number._sign;
    number._sign = true;
    LongInt left = 1;
    LongInt right = number / 2 + 1;
    LongInt middle;
    LongInt result;
    while (left <= right) {
        middle = left + (right - left) / 2;
        if (middle * middle * middle <= number) {
            left = middle + 1;
            result = middle;
        }
        else {
            right = middle - 1;
        }
    }
    result._sign = result_natural;
    return result;
}

Теперь напишем файл с генератором псевдослучайных чисел заданной длины. Выглядеть это будет вот так:

#include <random>
#include <cmath>
#include "LongInt.hpp"


LongInt LongInt::random(long long number_length) {
    if (number_length < 1) {
        throw "Fatal error. Random number generation is not possible. Specified length is less than or equal to zero.";
    }
    LongInt result;
    result._digits.resize(0);
    std::random_device random_device;
    std::mt19937 mersenne(random_device());
    int tmp = 0;
    if (number_length % _base_length == 0) {
        while (tmp == 0 or std::to_string(tmp).size() != _base_length) {
            tmp = mersenne() % _base;
        }
        result._digits.push_back(tmp);
        number_length = number_length - _base_length;
    }
    else {
        while (tmp == 0 or std::to_string(tmp).size() != number_length % _base_length) {
            tmp = mersenne() % (unsigned int)std::pow(10, number_length % _base_length);
        }
        result._digits.push_back(tmp);
        number_length = number_length - (number_length % _base_length);
    }
    result._digits.reserve(number_length / _base_length);
    while (number_length != 0) {
        result._digits.push_back(mersenne() % _base);
        number_length = number_length - _base_length;
    }
    return result;
}

На этом реализация функций подошла к концу, осталось лишь накидать демонстрационную программу и замерить производительность.

Вот файл демонстрационной программы. Ничего объяснять, думаю, тут не надо - программа элементарна.

#include <iostream>
#include <chrono>
#include "../src/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;
    std::cout << "19| Выход." << 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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            number_second = number_second_string;
            result_longint = number_first + number_second;
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "2") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            number_second = number_second_string;
            result_longint = number_first - number_second;
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "3") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            number_second = number_second_string;
            result_longint = number_first * number_second;
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "4") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            number_second = number_second_string;
            result_longint = number_first / number_second;
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "5") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            number_second = number_second_string;
            result_longint = number_first % number_second;
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "6") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "7") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_longint = LongInt::factorial(number_first);
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "8") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "9") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "10") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_longint = LongInt::abs(number_first);
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "11") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_bool = LongInt::even(number_first);
            std::cout << "Результат: " << result_bool << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "12") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_bool = LongInt::odd(number_first);
            std::cout << "Результат: " << result_bool << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "13") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "14") {
            std::cout << "Введите первое число: ";
            getline(std::cin, number_first_string);
            std::cout << "Введите второе число: ";
            getline(std::cin, number_second_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            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 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "15") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_longint = LongInt::isqrt(number_first);
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "16") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            result_longint = LongInt::icbrt(number_first);
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "17") {
            std::cout << "Введите число [оно должно помещаться в стандартные целочисленные типы]: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            result_longint = LongInt::random(std::stoi(number_first_string));
            std::cout << "Результат: " << result_longint << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "18") {
            std::cout << "Введите число: ";
            getline(std::cin, number_first_string);
            time_start = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            number_first = number_first_string;
            std::cout << "Результат: " << LongInt::size(number_first) << "." << std::endl;
            time_end = std::chrono::high_resolution_clock::now().time_since_epoch().count();
            std::cout << "Затрачено времени [с учетом затрат на конвертацию типов и вывод]: " << (time_end - time_start) / 1000000000 << " секунд(а/ы)." << std::endl;
        }
        else if (action == "19") {
            break;
        }
        else {
            std::cout << "Неизвестный номер команды. Введите число от 1 до 19." << std::endl;
        }
    }
    return 0;
}

Все файлы готовы - теперь можно со спокойной душой компилировать. Компилируется на моем ноутбуке довольно шустро - пару секунд. Теперь, предлагаю замерить время выполнения самых "долгих" операций и сравнить ее с временем выполнения, скажем, в Python 3.9, где реализация длинных чисел уже выполнена из коробки. Обращаю внимание, что тесты производятся с учетом затрат на конвертацию типов и печать в консоль. Тесты будут проводиться на моем ноутбуке, вот информация о системе:

Операционная система

Debian GNU/Linux 11 Bullseye

Компилятор

gcc 10.2.1

Процессор

Intel Core i5-8250U

Оперативная память

8GB

А вот сами тесты производительности:

Название операции

Время выполнения в Python 3.9 (в сек.)

Время выполнения в данной реализации (в сек.)

Возведение 2 в 1 000 000 степень (в Python 3.9 используется оператор "**", в данной реализации - функция LongInt::pow())

1.22

0.62

Возведение 2 в 10 000 000 степень (в Python 3.9 используется оператор "**", в данной реализации - функция LongInt::pow())

121.81

58.66

Подсчет факториала от 100 000Python 3.9 используется функция math.factorial(), в данной реализации - LongInt::factorial())

2.91

2.79

Подсчет факториала от 1 000 000Python 3.9 используется функция math.factorial(), в данной реализации - LongInt::factorial())

421.93

184.81

Исходя из тестов видно, что Python проигрывает в скорости все сильнее и сильнее с ростом сложности задачи, но справедливости ради стоит заметить, что тест этих двух функций затрагивает далеко не весь функционал реализаций.

Спасибо за чтение. Библиотека доступна в репозитории на Github.

P.S. Статья была в последний раз отредактирована 9 октября 2021 года.

Теги:
Хабы:
Всего голосов 41: ↑33 и ↓8 +25
Просмотры 12K
Комментарии Комментарии 68