Цифра-счет повышения::multiprecision::cpp_int

Question

Какой эффективный способ получить количество цифр boost::multiprecision::cpp_int? log10() Функция, очевидно, не совместима с целочисленными точными числами, и я не могу найти другой способ сделать это.

Answer 1

Ты можешь использовать .str().size(),

const cpp_int n = cpp_int("123456789") * cpp_int("987654321");
const size_t digits = n.str().size(); // digits == 18

Это выглядит расточительно, но быстрее, чем log10 или деление на 10.

Answer 2

Если вы используете boost::multiprecision::cpp_int, тогда boost::multiprecision::log10 должен быть наиболее эффективным способом. Не делайте деление или to str, как предлагается здесь, так как это очень медленно.

      input: 1'000'000 ^ 1'000
calc time: 0s
log digits: 6001, log time: 0s
str digits: 6001, str time: 0.001s
div digits: 6001, div time: 0.022s

input: 1'000'000 ^ 10'000
calc time: 0.004s
log digits: 60001, log time: 0.003s
str digits: 60001, str time: 0.1s
div digits: 60001, div time: 1.808s

input: 1'000'000 ^ 100'000
calc time: 0.374s
log digits: 600001, log time: 0.436s
str digits: 600001, str time: 10.143s
div digits: 600001, div time: 183.218s

input: 1'000'000 ^ 1'000'000
log digits: 6000001, log time: 48.968s

Другие не тестировались. Версия str должна быть примерно 15-20 минут, а версия div, вероятно, 5 часов.

тестовый код:

      #include <iostream>
#include <chrono>
#include <boost/multiprecision/gmp.hpp>
#include <boost/multiprecision/cpp_int.hpp>

int main() {
    std::chrono::steady_clock::time_point calcStart = std::chrono::steady_clock::now();
    boost::multiprecision::cpp_int x = boost::multiprecision::pow(boost::multiprecision::cpp_int(1'000'000), 1'000);
    std::chrono::steady_clock::time_point calcEnd_logStart = std::chrono::steady_clock::now();
    boost::multiprecision::cpp_int digits = boost::multiprecision::log10(x.convert_to<boost::multiprecision::mpf_float_50>()).convert_to<boost::multiprecision::cpp_int>() + 1;
    std::chrono::steady_clock::time_point logEnd_strStart = std::chrono::steady_clock::now();

    size_t strDigits =  x.str().size();
    std::chrono::steady_clock::time_point strEnd_divStart = std::chrono::steady_clock::now();

    uint64_t divCnt = 1;
    while (x >= 10) {
        x /= 10;
        divCnt++;
    }
    std::chrono::steady_clock::time_point divEnd = std::chrono::steady_clock::now();


    std::cerr << "calc time: " << std::chrono::duration_cast<std::chrono::milliseconds> (calcEnd_logStart - calcStart).count() / 1000.0 << "s" << std::endl;
    std::cerr << "log digits: " << digits << ", log time: " << std::chrono::duration_cast<std::chrono::milliseconds> (logEnd_strStart - calcEnd_logStart).count() / 1000.0 << "s" << std::endl;
    std::cerr << "str digits: " << strDigits << ", str time: " << std::chrono::duration_cast<std::chrono::milliseconds> (strEnd_divStart - logEnd_strStart).count() / 1000.0 << "s" << std::endl;
    std::cerr << "div digits: " << divCnt << ", div time: " << std::chrono::duration_cast<std::chrono::milliseconds> (divEnd - strEnd_divStart).count() / 1000.0 << "s" << std::endl;

    return 0;
}

Answer 3

Если преобразование в cpp_dec_float¹ нежелательно (думаю, нет), вы можете разделить на 10:

Жить на Колиру

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using Int   = boost::multiprecision::cpp_int;
using Float = boost::multiprecision::cpp_dec_float_50;

int main() {
    Int demo("12345678912345678");

    int digits = 0;
    for (Int tmp = abs(demo); tmp > 0; tmp /= 10)
        digits += 1;
    std::cout << digits << ", " << ceil(log10(Float(demo))) << "\n";
}

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

---

¹ C++ Boost мультиточность cpp_int