时间戳

首页 > 解决方案 > 使用 boost::multiprecision cpp_int 进行左移时超出时间限制错误

c++ - 使用 boost::multiprecision cpp_int 进行左移时超出时间限制错误

问题描述

我正在尝试以下操作：

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

int main()
{
   using namespace boost::multiprecision;
   cpp_int v = 1;
   unsigned int a = 4294967295;
   std::cout << (v << a) << std::endl; 
   return 0;
}

如何防止相同的错误？我们可以用 cpp_int 做的位移上限是多少。

标签： c++boost

解决方案

这分配了大量（浪费的）内存。

由于您可以使用十进制浮点数来表示此数字而不会损失任何精度，因此我会这样做：

注意1 << n等于2^n(pow(2, n))，所以你可以写：

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

namespace bmp = boost::multiprecision;
using number = bmp::number<bmp::cpp_dec_float<50, intmax_t> >;

int main() {
    int64_t a = 0xffffffff;
    std::cout << pow(number(2), a) << std::endl; 
}

哪个是正确的

1.55164e+1292913986

您可以验证它是否正确：

for (intmax_t const a : { -8888ll, 0xFFFFll, 0xFFFFFFFFll, }) {
    std::cout << pow(number(2), a) << std::endl; 
    auto roundtrip_exponent = bmp::log2(pow(number(2), a));

    auto reverse = round(roundtrip_exponent).convert_to<intmax_t>();
    std::cout << "Reverse: " << std::hex << std::showbase << reverse << std::dec << "\n";

    std::cout << "Match: " << std::boolalpha << (a == reverse) << "\n";
}

在Coliru现场打印

2.78868e-2676
Reverse: 0xffffffffffffdd48
Match: true
1.00176e+19728
Reverse: 0xffff
Match: true
1.55164e+1292913986
Reverse: 0xffffffff
Match: true

在极端情况下，您将不可避免地在不精确的操作 (log2) 上失去一些精度。

如果您很好奇，您可能想尝试通过设置打印完整的精度std::fixed：

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

namespace bmp = boost::multiprecision;
using number = bmp::number<bmp::cpp_dec_float<50, intmax_t> >;

int main() {
    std::cout << std::fixed << pow(number(2), 0xFFFFFFFFll) << std::endl; 
}

将输出重定向到文件！它将以十进制数字写入 1.3GiB。这应该可以解释为什么它不能很好地与任意精度整数表示一起工作。

所有输出压缩为：

0000000 3531 3135 3436 3230 3137 3339 3631 3334
0000020 3730 3130 3934 3439 3535 3737 3339 3831
0000040 3232 3937 3535 3631 3334 3936 3939 3038
0000060 3737 3938 3631 3338 3737 3030 3532 3339
0000100 3533 3538 3636 3230 3935 3039 3030 3030
0000120 3030 3030 3030 3030 3030 3030 3030 3030
*
11504046500 3030 2e30 3030 3030 3030 000a
11504046513

其中*表示只有 0 位数字的行。然后你就会明白为什么我称之为浪费了

推荐阅读