RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1320123
Accepted
gth-other
gth-other
Asked:2022-08-22 02:06:13 +0000 UTC2022-08-22 02:06:13 +0000 UTC 2022-08-22 02:06:13 +0000 UTC

C++ 长算术优化

  • 772

我最近决定用 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 секунд.

c++
  • 2 2 个回答
  • 10 Views

2 个回答

  • Voted
  1. Mark Shevchenko
    2022-08-22T02:55:57Z2022-08-22T02:55:57Z

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

    Скажем, у вас есть число 21000, для хранения которого надо 1000 битов или 125 байт. Младшие 8 бит можно хранить в первом байте, следующие 8 бит — во втором. Способ хранения можете выбрать сами.

    Сложение двух таких чисел сведётся к побайтовому сложению значений из двух массивов. Если результат больше 256, необходимо к следующей паре байт прибавить 1 — это перенос разряда.

    void add(unsigned char[] a, unsigned char[] b, unsigned char result[], size_t size)
    {
        int curry = 0;
        for (size_t i = 0; i < size; i++) {
            int next_byte = a[i] + b[i];
            if (next_byte >= 256) {
                next_byte -= 256;
                curry = 1;
            }
            else
                curry = 0;
    
            result[i] = next_byte;
        }
    }
    

    Вы можете существенно ускорить сложение, если будете работать не с байтами, а с целыми unsigned int. ЦПУ складывает и умножает целые числа с той же скоростью, что и байты, или даже быстрее.

    Умножение в простейшем случае можно разложить на умножения байтов и сложение результатов.

    Скажем, если у нас есть первое число состоит из байтов A и B, а второй из C и D, то их можно представить, как 256×A + B и 256×C + D. Их произведением будет равно 256×256×A×C+256×A×D + 256×B×C+B×D.

    Умножение на 256 означает, что мы просто переходим к следующему байту в массиве.

    result[0] = low(b * d);
    result[1] = high(b * d) + low(a * d) + low(b * c);
    result[2] = high(a * d) + high(b * c) + low(a * c);
    result[3] = high(a * c);
    

    Здесь low(x) означает младший байт двухбайтового слова x, а high(x) — старший.

    За счёт перехода к двоичной системе, тем более к целым, вы можете сделать код гораздо быстрее. Есть интересные алгоритмы быстрого умножения (см. алгоритм Шёнхаге — Штрассена), но они довольно трудные. Тем не менее, если интересно, можете погрузиться в тему.

    Есть также трюки, снижающие количество операций. Например, чтобы возвести число в степень 1000, нужно 999 умножений само на себя.

    Но если разложить 1000 на степени двойки, то получиться 1000 = 512 + 256 + 128 + 64 + 32 + 8, то есть, a1000 = a512*a256*a128*a64*a32*a8.

    Здесь умножений уже гораздо меньше, особенно, если кэшировать промежуточные результаты:

    a8 = ((a2)2)2
    a32 = ((a8)2)2
    a64 = (a32)2
    a128 = (a64)2
    a256 = (a128)2
    a512 = (a256)2

    Возведение в квадрат это как раз одно умножения. В приведённом примере вместо 1000 умножений мы использовали всего 9.

    • 3
  2. Best Answer
    gth-other
    2022-08-23T00:31:09Z2022-08-23T00:31:09Z

    Я сменил базу с 10 на 1000000000, заменил примитивный алгоритм нахождения факториала на алгоритм нахождения деревом, а также добавил функцию быстрой проверки на четность. Кому интересно что получилось --- https://github.com/gth-other/long_arithmetic.

    • 1

相关问题

  • 编译器和模板处理

  • 指针。找到最小数量

  • C++,关于枚举类对象初始化的问题

  • 函数中的二维数组

  • 无法使用默认构造函数创建类对象

  • C++ 和循环依赖

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    表格填充不起作用

    • 2 个回答
  • Marko Smith

    提示 50/50,有两个,其中一个是正确的

    • 1 个回答
  • Marko Smith

    在 PyQt5 中停止进程

    • 1 个回答
  • Marko Smith

    我的脚本不工作

    • 1 个回答
  • Marko Smith

    在文本文件中写入和读取列表

    • 2 个回答
  • Marko Smith

    如何像屏幕截图中那样并排排列这些块?

    • 1 个回答
  • Marko Smith

    确定文本文件中每一行的字符数

    • 2 个回答
  • Marko Smith

    将接口对象传递给 JAVA 构造函数

    • 1 个回答
  • Marko Smith

    正确更新数据库中的数据

    • 1 个回答
  • Marko Smith

    Python解析不是css

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5