提升的位数::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

如果不需要转换为cpp_dec_foat¹（我猜不是），可以除以10:

在Coliru上直播

#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

Answer 3

如果您使用的是boost:：multiprecision:：cpp_int，那么boost:：multirecision：：log10应该是最具性能的方式。不要像这里建议的那样进行除法或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;
}