再会。
我实现了 AES 128 CBC 加密。网上有很多专门介绍这种模式的资料，所以在这里提个问题。
我需要将初始化向量存储在安全位置吗？如果初始化向量可供攻击者使用，攻击者会获得优势吗？是否可以在明文加密文件的末尾放心地推它？
再会。我遇到了一个相当不寻常且在我看来很有趣的问题。我正在做长算术。直到最近，所有的操作都是以10为底的数字系统进行的，但由于速度慢和内存消耗不合理，这个实现不得不将数字系统更改为以10^9为底的数字系统。更改，解决了溢出和其他问题，但最近出现了一个与除法有关的问题，因此，从除法中获取余数。
假设我们有两个数字：999999999999999999(18 个九)和1000000000(一个和九个零)，它们分别存储在向量中，分别为{999999999, 999999999}和{1, 0}。我们用经典的划分将它们划分为列算法。我们取零位并将其连接到一些“中间股息”的预先创建的变量。中间被除数小于第二个数字，所以我们去掉零并将第一个数字的第一位连接到中间被除数。现在中间股息大于第二个数字。结果，我们需要将第二个数字放入中间被除数的次数相加。但是，我们仍然没有除法的实现，因此，除法必须用减法代替，但是减去999999999次的任务，说白了，不是很快。我将存储基数的常数更改为10- 一切正常。有必要了解可以做什么，这样程序才不会因为这些不方便的数字而陷入很长的周期。欢迎任何建议。
文件long_arithmetic.hpp（这里是类本身的源码，除法函数调用inf::division_whole()）：
#include <iostream>
#include <vector>
class inf {
public:
static std::string to_string(const inf& number);
inf();
inf(std::string string);
inf(signed int number);
inf(unsigned int number);
inf(signed long number);
inf(unsigned long number);
inf(signed long long number);
inf(unsigned long long number);
static inf pow(inf number_thirst, inf number_second);
static inf factorial(const inf& number);
static inf gcd(inf number_thirst, inf number_second);
static inf lcm(inf number_thirst, inf number_second);
static inf abs(inf number_thirst);
static bool even(const inf& number);
friend std::ostream& operator <<(std::ostream& ostream, const inf& number);
friend bool operator >(const inf& number_thirst, const inf& number_second);
friend bool operator >=(const inf& number_thirst, const inf& number_second);
friend bool operator <(const inf& number_thirst, const inf& number_second);
friend bool operator <=(const inf& number_thirst, const inf& number_second);
friend bool operator ==(const inf& number_thirst, const inf& number_second);
friend bool operator !=(const inf& number_thirst, const inf& number_second);
friend inf operator +(const inf& number_thirst, const inf& number_second);
friend inf operator -(const inf& number_thirst, const inf& number_second);
friend inf operator *(const inf& number_thirst, const inf& number_second);
friend inf operator /(const inf& number_thirst, const inf& number_second);
friend inf operator %(const inf& number_thirst, const inf& number_second);
inf operator +=(const inf& number);
inf operator -=(const inf& number);
inf operator *=(const inf& number);
inf operator /=(const inf& number);
inf operator %=(const inf& number);
inf operator ++();
inf operator --();
inf operator ++(int);
inf operator --(int);
private:
std::vector<int> digits;
bool natural;
static const int base = 1000000000;
static const int base_length = 9;
static std::vector<int> string_convert_to_vector(const std::string& string);
static inf zeroes_leading_remove(inf number);
static inf shift_right(inf number, int shift_power);
static char compare(inf number_thirst, inf number_second);
static inf subtraction_natural(inf number_thirst, inf number_second);
static inf sum(inf number_thirst, inf number_second);
static inf subtraction(inf number_thirst, inf number_second);
static inf multiply(inf number_thirst, inf number_second);
static inf division_whole(inf number_thirst, inf number_second);
static inf division_remainder(inf number_thirst, inf number_second);
static inf factorial_tree(inf number_thirst, const inf& number_second);
};
std::vector<int> inf::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 (int 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;
}
std::string inf::to_string(const inf& number) {
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 (int 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;
}
inf inf::zeroes_leading_remove(inf number) {
while (number.digits.size() != 1 and number.digits[0] == 0) {
number.digits.erase(number.digits.begin() + 0);
}
return number;
}
inf inf::shift_right(inf number, int shift_power) {
number.digits.reserve(shift_power);
for (int i = 0; i < shift_power; i = i + 1) {
number.digits.insert(number.digits.begin() + 0, 0);
}
return number;
}
inf::inf() {
digits.resize(1);
digits[0] = 0;
natural = true;
}
inf::inf(std::string string) {
if (string.size() == 0 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 (int 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 = inf::string_convert_to_vector(string);
}
inf::inf(signed int number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned int number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(signed long number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned long number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(signed long long number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned long long number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
char inf::compare(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
return '>';
}
if (number_thirst.natural == false and number_second.natural == true) {
return '<';
}
if (number_thirst.natural == false and number_second.natural == false) {
number_thirst.natural = true;
number_second.natural = true;
char tmp = inf::compare(number_thirst, number_thirst);
if (tmp == '>') {
return '<';
}
if (tmp == '<') {
return '>';
}
return '=';
}
if (number_thirst.digits.size() > number_second.digits.size()) {
return '>';
}
if (number_thirst.digits.size() < number_second.digits.size()) {
return '<';
}
for (int numbers_position = 0; numbers_position < number_thirst.digits.size(); numbers_position = numbers_position + 1) {
if (number_thirst.digits[numbers_position] > number_second.digits[numbers_position]) {
return '>';
}
if (number_thirst.digits[numbers_position] < number_second.digits[numbers_position]) {
return '<';
}
}
return '=';
}
inf inf::subtraction_natural(inf number_thirst, inf number_second) {
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_thirst, number_second) == '<') {
inf tmp = number_thirst;
number_thirst = number_second;
number_second = tmp;
number_thirst.natural = false;
}
number_second = inf::shift_right(number_second, number_thirst.digits.size() - number_second.digits.size());
int different;
for (int numbers_position1 = number_thirst.digits.size() - 1; numbers_position1 >= 0; numbers_position1 = numbers_position1 - 1) {
different = number_thirst.digits[numbers_position1] - number_second.digits[numbers_position1];
if (different >= 0) {
number_thirst.digits[numbers_position1] = different;
}
else {
number_thirst.digits[numbers_position1] = different + base;
for (int numbers_position2 = numbers_position1 - 1; true; numbers_position2 = numbers_position2 - 1) {
if (number_thirst.digits[numbers_position2] == 0) {
number_thirst.digits[numbers_position2] = base - 1;
}
else {
number_thirst.digits[numbers_position2] = number_thirst.digits[numbers_position2] - 1;
break;
}
}
}
}
return inf::zeroes_leading_remove(number_thirst);
}
inf inf::sum(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
return inf::subtraction_natural(number_thirst, number_second);
}
if (number_thirst.natural == false and number_second.natural == true) {
return inf::subtraction_natural(number_second, number_thirst);
}
if (number_thirst.natural == false and number_second.natural == false) {
number_second.natural = true;
}
if (number_thirst.digits.size() > number_second.digits.size()) {
number_second = inf::shift_right(number_second, number_thirst.digits.size() - number_second.digits.size());
}
else {
number_thirst = inf::shift_right(number_thirst, number_second.digits.size() - number_thirst.digits.size());
}
int sum;
int in_mind = 0;
for (int numbers_position = number_thirst.digits.size() - 1; numbers_position >= 0; numbers_position = numbers_position - 1) {
sum = number_thirst.digits[numbers_position] + number_second.digits[numbers_position] + in_mind;
in_mind = sum / base;
number_thirst.digits[numbers_position] = sum % base;
}
if (in_mind != 0) {
number_thirst.digits.insert(number_thirst.digits.begin() + 0, in_mind);
}
return number_thirst;
}
inf inf::subtraction(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
number_second.natural = true;
return inf::sum(number_thirst, number_second);
}
if (number_thirst.natural == false and number_second.natural == true) {
number_thirst.natural = true;
inf tmp = inf::sum(number_thirst, number_second);
tmp.natural = false;
return tmp;
}
if (number_thirst.natural == false and number_second.natural == false) {
return inf::subtraction_natural(number_second, number_thirst);
}
return inf::subtraction_natural(number_thirst, number_second);
}
inf inf::multiply(inf number_thirst, inf number_second) {
inf result;
result.digits.resize(number_thirst.digits.size() + number_second.digits.size());
long long composition;
for (int number_thirst_position = number_thirst.digits.size() - 1; number_thirst_position >= 0; number_thirst_position = number_thirst_position - 1) {
for (int number_second_position = number_second.digits.size() - 1; number_second_position >= 0; number_second_position = number_second_position - 1) {
composition = (long long)number_thirst.digits[number_thirst_position] * (long long)number_second.digits[number_second_position] + result.digits[number_thirst_position + number_second_position + 1];
result.digits[number_thirst_position + number_second_position + 1] = composition % base;
result.digits[number_thirst_position + number_second_position + 1 - 1] = result.digits[number_thirst_position + number_second_position + 1 - 1] + (composition / base);
}
}
result.natural = (number_thirst.natural == number_second.natural);
return inf::zeroes_leading_remove(result);
}
inf inf::division_whole(inf number_thirst, inf number_second) {
inf zero = 0;
inf result;
result.natural = (number_thirst.natural == number_second.natural);
inf number_thirst_part;
number_thirst_part.natural = true;
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_second, zero) == '=') {
throw "Fatal error. Division is impossible. Attempt to divide by zero.";
}
if (inf::compare(number_thirst, number_second) == '<') {
return zero;
}
result.digits.resize(0);
number_thirst_part.digits.resize(0);
int quotient;
for (int number_thirst_position = 0; number_thirst_position < number_thirst.digits.size(); number_thirst_position = number_thirst_position + 1) {
number_thirst_part.digits.push_back(number_thirst.digits[number_thirst_position]);
quotient = 0;
if (number_second.digits.size() == 1) {
quotient = std::stoi(inf::to_string(number_thirst_part)) / std::stoi(inf::to_string(number_second));
number_thirst_part = std::stoi(inf::to_string(number_thirst_part)) % std::stoi(inf::to_string(number_second));
}
else {
while (inf::compare(number_thirst_part, number_second) != '<') {
number_thirst_part = inf::subtraction_natural(number_thirst_part, number_second);
quotient = quotient + 1;
}
}
if (result.digits.size() != 0 or quotient != 0) {
result.digits.push_back(quotient);
}
if (inf::compare(number_thirst_part, zero) == '=') {
number_thirst_part.digits.resize(0);
}
}
return result;
}
inf inf::division_remainder(inf number_thirst, inf number_second) {
inf zero = 0;
inf number_thirst_part;
number_thirst_part.natural = true;
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_second, zero) == '=') {
throw "Fatal error. Division is impossible. Attempt to divide by zero.";
}
if (inf::compare(number_thirst, number_second) == '<') {
return number_thirst;
}
number_thirst_part.digits.resize(0);
for (int number_thirst_position = 0; number_thirst_position < number_thirst.digits.size(); number_thirst_position = number_thirst_position + 1) {
number_thirst_part.digits.push_back(number_thirst.digits[number_thirst_position]);
if (number_second.digits.size() == 1) {
number_thirst_part = std::stoi(inf::to_string(number_thirst_part)) % std::stoi(inf::to_string(number_second));
}
else {
while (inf::compare(number_thirst_part, number_second) != '<') {
number_thirst_part = inf::subtraction_natural(number_thirst_part, number_second);
}
}
if (inf::compare(number_thirst_part, zero) == '=') {
number_thirst_part.digits.resize(0);
}
}
if (number_thirst_part.digits.size() == 0) {
return zero;
}
return number_thirst_part;
}
inf inf::pow(inf number_thirst, inf number_second) {
inf zero = 0;
inf one = 1;
inf two = 2;
if (inf::compare(number_thirst, zero) == '=' and inf::compare(number_second, zero) == '=') {
throw "Fatal error. Pow calculation is impossible. It is impossible to raise zero to zero degree.";
}
if (inf::compare(number_second, zero) == '<') {
throw "Fatal error. Pow calculation is impossible. This class only support whole numbers, so erection to negative degree is impossible.";
}
inf result = one;
while (inf::compare(number_second, zero) != '=') {
if (inf::compare(inf::division_remainder(number_second, two), zero) == '=') {
number_second = inf::division_whole(number_second, two);
number_thirst = inf::multiply(number_thirst, number_thirst);
}
else {
number_second = inf::subtraction_natural(number_second, one);
result = inf::multiply(result, number_thirst);
}
}
return result;
}
inf inf::factorial_tree(inf number_thirst, const inf& number_second) {
inf one = 1;
inf two = 2;
if (inf::compare(number_thirst, number_second) == '>') {
return one;
}
if (inf::compare(number_thirst, number_second) == '=') {
return number_thirst;
}
if (inf::compare(inf::subtraction_natural(number_second, number_thirst), one) == '=') {
return inf::multiply(number_thirst, number_second);
}
inf tmp = inf::division_whole(inf::sum(number_thirst, number_second), two);
return inf::multiply(inf::factorial_tree(number_thirst, tmp), inf::factorial_tree(inf::sum(tmp, one), number_second));
}
inf inf::factorial(const inf& number) {
inf one = 1;
inf two = 2;
if (inf::compare(number, one) == '<') {
throw "Fatal error. Factorial calculation is impossible. Factorial is defined only for natural numbers.";
}
if (inf::compare(number, one) == '=') {
return one;
}
if (inf::compare(number, two) == '=') {
return two;
}
return factorial_tree(two, number);
}
inf inf::gcd(inf number_thirst, inf number_second) {
inf zero = 0;
if (inf::compare(number_thirst, zero) == '=' or inf::compare(number_second, zero) == '=') {
throw "Fatal error. GCD calculation is impossible. One of the numbers is zero.";
}
number_thirst.natural = true;
number_second.natural = true;
while (inf::compare(number_thirst, zero) != '=' and inf::compare(number_second, zero) != '=') {
if (inf::compare(number_thirst, number_second) == '>') {
number_thirst = inf::division_remainder(number_thirst, number_second);
}
else {
number_second = inf::division_remainder(number_second, number_thirst);
}
}
return inf::sum(number_thirst, number_second);
}
inf inf::lcm(inf number_thirst, inf number_second) {
inf zero = 0;
if (inf::compare(number_thirst, zero) == '=' or inf::compare(number_second, zero) == '=') {
throw "Fatal error. LCM calculation is impossible. One of the numbers is zero.";
}
number_thirst.natural = true;
number_second.natural = true;
return inf::division_whole(inf::multiply(number_thirst, number_second), inf::gcd(number_thirst, number_second));
}
inf inf::abs(inf number) {
number.natural = true;
return number;
}
bool inf::even(const inf& number) {
if (number.digits[number.digits.size() - 1] % 2 == 0) {
return true;
}
return false;
}
std::ostream &operator <<(std::ostream& ostream, const inf& number) {
std::string string = inf::to_string(number);
for (int i = 0; i < string.size(); i = i + 1) {
ostream.put(string[i]);
}
return ostream;
}
bool operator >(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '>') {
return true;
}
return false;
}
bool operator >=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '<') {
return true;
}
return false;
}
bool operator <(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '<') {
return true;
}
return false;
}
bool operator <=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '>') {
return true;
}
return false;
}
bool operator ==(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '=') {
return true;
}
return false;
}
bool operator !=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '=') {
return true;
}
return false;
}
inf operator +(const inf& number_thirst, const inf& number_second) {
return inf::sum(number_thirst, number_second);
}
inf operator -(const inf& number_thirst, const inf& number_second) {
return inf::subtraction(number_thirst, number_second);
}
inf operator *(const inf& number_thirst, const inf& number_second) {
return inf::multiply(number_thirst, number_second);
}
inf operator /(const inf& number_thirst, const inf& number_second) {
return inf::division_whole(number_thirst, number_second);
}
inf operator %(const inf& number_thirst, const inf& number_second) {
return inf::division_remainder(number_thirst, number_second);
}
inf inf::operator +=(const inf& number) {
return *this = *this + number;
}
inf inf::operator -=(const inf& number) {
return *this = *this - number;
}
inf inf::operator *=(const inf& number) {
return *this = *this * number;
}
inf inf::operator /=(const inf& number) {
return *this = *this / number;
}
inf inf::operator %=(const inf& number) {
return *this = *this % number;
}
inf inf::operator ++() {
return *this = *this + 1;
}
inf inf::operator --() {
return *this = *this - 1;
}
inf inf::operator ++(int) {
*this = *this + 1;
return *this = *this - 1;
}
inf inf::operator --(int) {
*this = *this - 1;
return *this = *this + 1;
}
出现了以下情况。实现我自己的长算术库。需要编写一个函数来计算阶乘。在网络上搜索了一些快速计算阶乘的算法后，我找到了一个简单且同时快速的算法来计算“树”，这是它的代码：
#include <iostream>
int factorial_tree(int number_thirst, int number_second) {
if (number_thirst > number_second)
return 1;
if (number_thirst == number_second)
return number_thirst;
if (number_second - number_thirst == 1)
return number_thirst * number_second;
int tmp = (number_thirst + number_second) / 2;
return factorial_tree(number_thirst, tmp) * factorial_tree(tmp + 1, number_second);
}
int factorial(int number) {
if (number < 0)
return 0;
if (number == 0)
return 1;
if (number == 1 || number == 2)
return number;
return factorial_tree(2, number);
}
int main() {
int number;
std::cin >> number;
std::cout << factorial(number) << std::endl;
return 0;
}
我学习了这个算法并将其构建到我的库中。一切正常，一切正常。然而，这个算法使用递归，我假设阶乘（> 1000000）的值很大，堆栈溢出是可能的。我看到的唯一明智的解决方案是用循环替换递归。我试着去做——它没有用。简而言之，我需要帮助在这个算法中用循环替换递归。
我最近决定用 C++ 编写一个长算法的实现。只是为了好玩和发展一些技能。写了，结果证明，它有效。但是，如果您将性能与 Python、Java 和其他语言的标准实现进行比较，您会注意到性能上有明显的差异。我想获得一些关于可以做些什么来显着提高生产力的建议。长数字本身存储在两个变量中：一个数据类型为 int 的向量，用于存储数字的位数（数制为 10，数字按正确的顺序存储）和一个布尔变量，用于存储是否数字是自然的）。main.cpp 文件：
#include <iostream>
#include "long_arithmetic.hpp"
int main() {
std::string number_thirst_string;
std::string number_second_string;
std::string action;
inf number_thirst;
inf number_second;
inf result;
int time_start;
int time_end;
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;
for (; ;) {
std::cout << std::endl;
std::cout << std::endl;
std::cout << "Выберите операцию: ";
getline(std::cin, action);
if (action == "1") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = number_thirst + number_second;
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "2") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = number_thirst - number_second;
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "3") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = number_thirst * number_second;
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "4") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = number_thirst / number_second;
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "5") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = number_thirst % number_second;
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "6") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = inf::pow(number_thirst, number_second);
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "7") {
std::cout << "Введите число: ";
getline(std::cin, number_thirst_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
result = inf::factorial(number_thirst);
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "8") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = inf::gcd(number_thirst, number_second);
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "9") {
std::cout << "Введите первое число: ";
getline(std::cin, number_thirst_string);
std::cout << "Введите второе число: ";
getline(std::cin, number_second_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
number_second = number_second_string;
result = inf::lcm(number_thirst, number_second);
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "10") {
std::cout << "Введите число: ";
getline(std::cin, number_thirst_string);
time_start = time(nullptr);
number_thirst = number_thirst_string;
result = inf::abs(number_thirst);
time_end = time(nullptr);
std::cout << "Результат: " << result << "." << std::endl;
std::cout << "Затрачено [с учетом затрат на конвертацию типов]: " << (time_end - time_start) / 60 << " минут(а/ы) и " << (time_end - time_start) % 60 << " секунд(а/ы)." << std::endl;
}
else if (action == "11") {
break;
}
else {
std::cout << "Неизвестный номер команды. Введите число от 1 до 11." << std::endl;
}
}
return 0;
}
文件 long_arithmetic.hpp：
#include <iostream>
#include <vector>
class inf {
public:
static std::string to_string(const inf& number);
inf();
inf(std::string string);
inf(signed int number);
inf(unsigned int number);
inf(signed long number);
inf(unsigned long number);
inf(signed long long number);
inf(unsigned long long number);
static inf pow(inf number_thirst, inf number_second);
static inf factorial(const inf& number);
static inf gcd(inf number_thirst, inf number_second);
static inf lcm(inf number_thirst, inf number_second);
static inf abs(inf number_thirst);
friend std::ostream& operator <<(std::ostream& ostream, const inf& number);
friend bool operator >(const inf& number_thirst, const inf& number_second);
friend bool operator >=(const inf& number_thirst, const inf& number_second);
friend bool operator <(const inf& number_thirst, const inf& number_second);
friend bool operator <=(const inf& number_thirst, const inf& number_second);
friend bool operator ==(const inf& number_thirst, const inf& number_second);
friend bool operator !=(const inf& number_thirst, const inf& number_second);
friend inf operator +(const inf& number_thirst, const inf& number_second);
friend inf operator -(const inf& number_thirst, const inf& number_second);
friend inf operator *(const inf& number_thirst, const inf& number_second);
friend inf operator /(const inf& number_thirst, const inf& number_second);
friend inf operator %(const inf& number_thirst, const inf& number_second);
inf operator +=(const inf& number);
inf operator -=(const inf& number);
inf operator *=(const inf& number);
inf operator /=(const inf& number);
inf operator %=(const inf& number);
inf operator ++();
inf operator --();
inf operator ++(int);
inf operator --(int);
private:
std::vector<int> digits;
bool natural;
static std::vector<int> string_convert_to_vector(const std::string& string);
static inf zeroes_leading_remove(inf number);
static inf shift_right(inf number, int shift_power);
static char compare(inf number_thirst, inf number_second);
static inf subtraction_natural(inf number_thirst, inf number_second);
static inf sum(inf number_thirst, inf number_second);
static inf subtraction(inf number_thirst, inf number_second);
static inf multiply(const inf& number_thirst, const inf& number_second);
static inf division_whole(inf number_thirst, inf number_second);
static inf division_remainder(inf number_thirst, inf number_second);
};
std::vector<int> inf::string_convert_to_vector(const std::string &string) {
std::vector<int> result;
result.resize(string.size());
for (int i = 0; i < string.size(); i = i + 1) {
result[i] = string[i] - '0';
}
return result;
}
std::string inf::to_string(const inf& number) {
std::string result;
if (number.natural == false) {
result.append("-");
}
result.reserve(number.digits.size());
char tmp;
for (int i = 0; i < number.digits.size(); i = i + 1) {
tmp = number.digits[i] + '0';
result.push_back(tmp);
}
return result;
}
inf inf::zeroes_leading_remove(inf number) {
while (number.digits.size() != 1 and number.digits[0] == 0) {
number.digits.erase(number.digits.begin() + 0);
}
return number;
}
inf inf::shift_right(inf number, int shift_power) {
number.digits.reserve(shift_power);
for (int i = 0; i < shift_power; i = i + 1) {
number.digits.insert(number.digits.begin() + 0, 0);
}
return number;
}
inf::inf() {
digits.resize(1);
digits[0] = 0;
natural = true;
}
inf::inf(std::string string) {
if (string.size() == 0 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 (int 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 = inf::string_convert_to_vector(string);
}
inf::inf(signed int number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned int number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(signed long number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned long number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(signed long long number) {
if (number < 0) {
number = number * -1;
natural = false;
}
else {
natural = true;
}
digits = inf::string_convert_to_vector(std::to_string(number));
}
inf::inf(unsigned long long number) {
natural = true;
digits = inf::string_convert_to_vector(std::to_string(number));
}
char inf::compare(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
return '>';
}
if (number_thirst.natural == false and number_second.natural == true) {
return '<';
}
if (number_thirst.natural == false and number_second.natural == false) {
number_thirst.natural = true;
number_second.natural = true;
char tmp = inf::compare(number_thirst, number_thirst);
if (tmp == '>') {
return '<';
}
if (tmp == '<') {
return '>';
}
return '=';
}
if (number_thirst.digits.size() > number_second.digits.size()) {
return '>';
}
if (number_thirst.digits.size() < number_second.digits.size()) {
return '<';
}
for (int numbers_position = 0; numbers_position < number_thirst.digits.size(); numbers_position = numbers_position + 1) {
if (number_thirst.digits[numbers_position] > number_second.digits[numbers_position]) {
return '>';
}
if (number_thirst.digits[numbers_position] < number_second.digits[numbers_position]) {
return '<';
}
}
return '=';
}
inf inf::subtraction_natural(inf number_thirst, inf number_second) {
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_thirst, number_second) == '<') {
inf tmp = number_thirst;
number_thirst = number_second;
number_second = tmp;
number_thirst.natural = false;
}
number_second = inf::shift_right(number_second, number_thirst.digits.size() - number_second.digits.size());
int different;
for (int numbers_position1 = number_thirst.digits.size() - 1; numbers_position1 >= 0; numbers_position1 = numbers_position1 - 1) {
different = number_thirst.digits[numbers_position1] - number_second.digits[numbers_position1];
if (different >= 0) {
number_thirst.digits[numbers_position1] = different;
}
else {
number_thirst.digits[numbers_position1] = different + 10;
for (int numbers_position2 = numbers_position1 - 1; true; numbers_position2 = numbers_position2 - 1) {
if (number_thirst.digits[numbers_position2] == 0) {
number_thirst.digits[numbers_position2] = 10 - 1;
}
else {
number_thirst.digits[numbers_position2] = number_thirst.digits[numbers_position2] - 1;
break;
}
}
}
}
return inf::zeroes_leading_remove(number_thirst);
}
inf inf::sum(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
return inf::subtraction_natural(number_thirst, number_second);
}
if (number_thirst.natural == false and number_second.natural == true) {
return inf::subtraction_natural(number_second, number_thirst);
}
if (number_thirst.natural == false and number_second.natural == false) {
number_second.natural = true;
}
if (number_thirst.digits.size() > number_second.digits.size()) {
number_second = inf::shift_right(number_second, number_thirst.digits.size() - number_second.digits.size());
}
else {
number_thirst = inf::shift_right(number_thirst, number_second.digits.size() - number_thirst.digits.size());
}
int sum;
int in_mind = 0;
for (int numbers_position = number_thirst.digits.size() - 1; numbers_position >= 0; numbers_position = numbers_position - 1) {
sum = number_thirst.digits[numbers_position] + number_second.digits[numbers_position] + in_mind;
in_mind = sum / 10;
number_thirst.digits[numbers_position] = sum % 10;
}
if (in_mind != 0) {
number_thirst.digits.insert(number_thirst.digits.begin() + 0, in_mind);
}
return number_thirst;
}
inf inf::subtraction(inf number_thirst, inf number_second) {
if (number_thirst.natural == true and number_second.natural == false) {
number_second.natural = true;
return inf::sum(number_thirst, number_second);
}
if (number_thirst.natural == false and number_second.natural == true) {
number_thirst.natural = true;
inf tmp = inf::sum(number_thirst, number_second);
tmp.natural = false;
return tmp;
}
if (number_thirst.natural == false and number_second.natural == false) {
return inf::subtraction_natural(number_second, number_thirst);
}
return inf::subtraction_natural(number_thirst, number_second);
}
inf inf::multiply(const inf& number_thirst, const inf& number_second) {
inf result;
result.digits.resize(number_thirst.digits.size() + number_second.digits.size());
int composition;
for (int number_thirst_position = number_thirst.digits.size() - 1; number_thirst_position >= 0; number_thirst_position = number_thirst_position - 1) {
for (int number_second_position = number_second.digits.size() - 1; number_second_position >= 0; number_second_position = number_second_position - 1) {
composition = number_thirst.digits[number_thirst_position] * number_second.digits[number_second_position];
result.digits[number_thirst_position + number_second_position + 1] = result.digits[number_thirst_position + number_second_position + 1] + composition;
}
}
int base_total_in_one_digit;
for (int result_position = result.digits.size() - 1; result_position >= 1; result_position = result_position - 1) {
base_total_in_one_digit = result.digits[result_position] / 10;
result.digits[result_position] = result.digits[result_position] - (base_total_in_one_digit * 10);
result.digits[result_position - 1] = result.digits[result_position - 1] + base_total_in_one_digit;
}
result.natural = (number_thirst.natural == number_second.natural);
return inf::zeroes_leading_remove(result);
}
inf inf::division_whole(inf number_thirst, inf number_second) {
inf zero = 0;
inf result;
result.natural = (number_thirst.natural == number_second.natural);
inf number_thirst_part;
number_thirst_part.natural = true;
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_second, zero) == '=') {
throw "Fatal error. Division is impossible. Attempt to divide by zero.";
}
if (inf::compare(number_thirst, number_second) == '<') {
return zero;
}
result.digits.resize(0);
number_thirst_part.digits.resize(0);
int quotient;
for (int number_thirst_position = 0; number_thirst_position < number_thirst.digits.size(); number_thirst_position = number_thirst_position + 1) {
number_thirst_part.digits.push_back(number_thirst.digits[number_thirst_position]);
quotient = 0;
while (inf::compare(number_thirst_part, number_second) != '<') {
number_thirst_part = inf::subtraction_natural(number_thirst_part, number_second);
quotient = quotient + 1;
}
if (quotient != 0 or result.digits.size() != 0) {
result.digits.push_back(quotient);
}
if (inf::compare(number_thirst_part, zero) == '=') {
number_thirst_part.digits.resize(0);
}
}
return result;
}
inf inf::division_remainder(inf number_thirst, inf number_second) {
inf zero = 0;
inf number_thirst_part;
number_thirst_part.natural = true;
number_thirst.natural = true;
number_second.natural = true;
if (inf::compare(number_second, zero) == '=') {
throw "Fatal error. Division is impossible. Attempt to divide by zero.";
}
if (inf::compare(number_thirst, number_second) == '<') {
return number_thirst;
}
number_thirst_part.digits.resize(0);
int quotient;
for (int number_thirst_position = 0; number_thirst_position < number_thirst.digits.size(); number_thirst_position = number_thirst_position + 1) {
number_thirst_part.digits.push_back(number_thirst.digits[number_thirst_position]);
quotient = 0;
while (inf::compare(number_thirst_part, number_second) != '<') {
number_thirst_part = inf::subtraction_natural(number_thirst_part, number_second);
quotient = quotient + 1;
}
if (inf::compare(number_thirst_part, zero) == '=') {
number_thirst_part.digits.resize(0);
}
}
if (number_thirst_part.digits.size() > 0) {
return number_thirst_part;
}
return zero;
}
inf inf::pow(inf number_thirst, inf number_second) {
inf zero = 0;
inf one = 1;
inf two = 2;
if (inf::compare(number_thirst, zero) == '=' and inf::compare(number_second, zero) == '=') {
throw "Fatal error. Pow calculation is impossible. It is impossible to raise zero to zero degree.";
}
if (inf::compare(number_second, zero) == '<') {
throw "Fatal error. Pow calculation is impossible. This class only support whole numbers, so erection to negative degree is impossible.";
}
inf result = one;
while (inf::compare(number_second, zero) != '=') {
if (inf::compare(inf::division_remainder(number_second, two), zero) == '=') {
number_second = inf::division_whole(number_second, two);
number_thirst = inf::multiply(number_thirst, number_thirst);
}
else {
number_second = inf::subtraction_natural(number_second, one);
result = inf::multiply(result, number_thirst);
}
}
return result;
}
inf inf::factorial(const inf& number) {
inf zero = 0;
inf one = 1;
inf two = 2;
if (inf::compare(number, one) == '<') {
throw "Fatal error. Factorial calculation is impossible. Factorial is defined only for natural numbers.";
}
if (inf::compare(number, one) == '=') {
return one;
}
inf result = one;
for (inf i = two; inf::compare(i, number) != '>'; i = inf::sum(i, one)) {
result = inf::multiply(result, i);
}
return result;
}
inf inf::gcd(inf number_thirst, inf number_second) {
inf zero = 0;
if (inf::compare(number_thirst, zero) == '=' or inf::compare(number_second, zero) == '=') {
throw "Fatal error. GCD calculation is impossible. One of the numbers is zero.";
}
number_thirst.natural = true;
number_second.natural = true;
while (inf::compare(number_thirst, zero) != '=' and inf::compare(number_second, zero) != '=') {
if (inf::compare(number_thirst, number_second) == '>') {
number_thirst = inf::division_remainder(number_thirst, number_second);
}
else {
number_second = inf::division_remainder(number_second, number_thirst);
}
}
return inf::sum(number_thirst, number_second);
}
inf inf::lcm(inf number_thirst, inf number_second) {
number_thirst.natural = true;
number_second.natural = true;
return inf::division_whole(inf::multiply(number_thirst, number_second), inf::gcd(number_thirst, number_second));
}
inf inf::abs(inf number) {
number.natural = true;
return number;
}
std::ostream &operator <<(std::ostream& ostream, const inf& number) {
std::string string = inf::to_string(number);
for (int i = 0; i < string.size(); i = i + 1) {
ostream.put(string[i]);
}
return ostream;
}
bool operator >(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '>') {
return true;
}
return false;
}
bool operator >=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '<') {
return true;
}
return false;
}
bool operator <(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '<') {
return true;
}
return false;
}
bool operator <=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '>') {
return true;
}
return false;
}
bool operator ==(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) == '=') {
return true;
}
return false;
}
bool operator !=(const inf& number_thirst, const inf& number_second) {
if (inf::compare(number_thirst, number_second) != '=') {
return true;
}
return false;
}
inf operator +(const inf& number_thirst, const inf& number_second) {
return inf::sum(number_thirst, number_second);
}
inf operator -(const inf& number_thirst, const inf& number_second) {
return inf::subtraction(number_thirst, number_second);
}
inf operator *(const inf& number_thirst, const inf& number_second) {
return inf::multiply(number_thirst, number_second);
}
inf operator /(const inf& number_thirst, const inf& number_second) {
return inf::division_whole(number_thirst, number_second);
}
inf operator %(const inf& number_thirst, const inf& number_second) {
return inf::division_remainder(number_thirst, number_second);
}
inf inf::operator +=(const inf& number) {
return *this=(*this + number);
}
inf inf::operator -=(const inf& number) {
return *this=(*this - number);
}
inf inf::operator *=(const inf& number) {
return *this=(*this * number);;
}
inf inf::operator /=(const inf& number) {
return *this=(*this / number);
}
inf inf::operator %=(const inf& number) {
return *this=(*this % number);
}
inf inf::operator ++() {
return *this = (*this + 1);
}
inf inf::operator --() {
return *this = (*this - 1);
}
inf inf::operator ++(int) {
*this = *this + 1;
return *this = (*this - 1);
}
inf inf::operator --(int) {
*this = *this - 1;
return *this = (*this + 1);
}
P.S. На данный момент на моем ноутбуке этот код выдает следующую производительность: Возведение 2 в 100000 степень - 3 секунды. Подсчет факториала от 10000 - 9 секунд.