创建一个静态查找表,当整数类型是Boost多精度数字/cpp_int时。

huangapple go评论66阅读模式
英文:

Creating a static lookup table when the integer type is Boost multiprecision number/cpp_int

问题

I'd like to create a static lookup table for powers of ten returned as type boost::mulitprecision's uint256_t:

static uint256_t power_ten(const uint8_t n)
{
    static const uint256_t table[] = 
    { 
        1,
        10
        // etc
    };

    return table[n];
}

However, I won't be able to define the literals for 256 bits because C++ literals are ints.

Consequently I thought I could use template metaprogramming to calculate the powers so I don't need to specify literals, similar to this Fibonacci example I found:

#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

using Integer = int;            // Works
//using Integer = uint256_t;    // Causes compiler errors

template<Integer n>
struct fibonacci
{
  static constexpr Integer value = fibonacci<n-1>::value + fibonacci<n-2>::value;
};

template<>
struct fibonacci<0>
{
  static constexpr Integer value = 0;
};

template<>
struct fibonacci<1>
{
  static constexpr Integer value = 1;
};

int main()
{   
    Integer a = fibonacci<40>::value;
    std::cout << a << std::endl;
}

This code works for int. However, if I comment/uncomment to use uint256_t I get these compiler errors:

clang-14: warning: -lquadmath: 'linker' input unused [-Wunused-command-line-argument]
<source>:8:18: error: a non-type template parameter cannot have type 'Integer' (aka 'number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void>>')
template<Integer n>
                 ^
<source>:11:28: error: declaration of constexpr static data member 'value' requires an initializer
  static constexpr Integer value = fibonacci<n-1>::value + fibonacci<n-2>::value;
                           ^
2 errors generated.
ASM generation compiler returned: 1
<source>:8:18: error: a non-type template parameter cannot have type 'Integer' (aka 'number<cpp_int_backend<256, 256, unsigned_magnitude, unchecked, void>>')
template<Integer n>
                 ^
<source>:11:28: error: declaration of constexpr static data member 'value' requires an initializer
  static constexpr Integer value = fibonacci<n-1>::value + fibonacci<n-2>::value;
                           ^

Is there another way to achieve this?

UPDATE

I've just tried populating the static table using uint256_t with a string constructor, as per the comments. This seemed to work but once I reach:

uint256_t("1000000000000000000000000000000000000000000000000000000000000000000000000000000")

std::cout outputs the wrong value:

73663286101470436611432119930496737173840122674875487684339327936694962880512
英文:

I'd like to create a static lookup table for powers of ten returned as type boost::mulitprecision's uint256_t:

static uint256_t power_ten(const uint8_t n)
{
    static const uint256_t table[] = 
    { 
        1,
        10
        // etc
    };

    return table[n];
}

However, I won't be able to define the literals for 256 bits because C++ literals are ints.

Consequently I thought I could use template metaprogramming to calculate the powers so I don't need to specify literals, similar to this Fibonacci example I found:

#include &lt;boost/multiprecision/cpp_int.hpp&gt;

using namespace boost::multiprecision;

using Integer = int;            // Works
//using Integer = uint256_t;    // Causes compiler errors

template&lt;Integer n&gt;
struct fibonacci
{
  static constexpr Integer value = fibonacci&lt;n-1&gt;::value + fibonacci&lt;n-2&gt;::value;
};

template&lt;&gt;
struct fibonacci&lt;0&gt;
{
  static constexpr Integer value = 0;
};

template&lt;&gt;
struct fibonacci&lt;1&gt;
{
  static constexpr Integer value = 1;
};

int main()
{   
    Integer a = fibonacci&lt;40&gt;::value;
    std::cout &lt;&lt; a &lt;&lt; std::endl;
}

This code works for int. However, if I comment/uncomment to use uint256_t I get these compiler errors:

clang-14: warning: -lquadmath: &#39;linker&#39; input unused [-Wunused-command-line-argument]
&lt;source&gt;:8:18: error: a non-type template parameter cannot have type &#39;Integer&#39; (aka &#39;number&lt;cpp_int_backend&lt;256, 256, unsigned_magnitude, unchecked, void&gt;&gt;&#39;)
template&lt;Integer n&gt;
                 ^
&lt;source&gt;:11:28: error: declaration of constexpr static data member &#39;value&#39; requires an initializer
  static constexpr Integer value = fibonacci&lt;n-1&gt;::value + fibonacci&lt;n-2&gt;::value;
                           ^
2 errors generated.
ASM generation compiler returned: 1
&lt;source&gt;:8:18: error: a non-type template parameter cannot have type &#39;Integer&#39; (aka &#39;number&lt;cpp_int_backend&lt;256, 256, unsigned_magnitude, unchecked, void&gt;&gt;&#39;)
template&lt;Integer n&gt;
                 ^
&lt;source&gt;:11:28: error: declaration of constexpr static data member &#39;value&#39; requires an initializer
  static constexpr Integer value = fibonacci&lt;n-1&gt;::value + fibonacci&lt;n-2&gt;::value;

https://godbolt.org/z/qsK8rG5WG

Is there another way to achieve this?

UPDATE

I've just tried populating the static table using uint256_t with a string constructor, as per the comments. This seemed to work but once I reach:

uint256_t(&quot;1000000000000000000000000000000000000000000000000000000000000000000000000000000&quot;)

std::cout outputs the wrong value:

73663286101470436611432119930496737173840122674875487684339327936694962880512

答案1

得分: 1

以下是代码的翻译部分:

// 替代使用昂贵的字符串初始化,考虑使用更高效的表达式:
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::uint512_t;

static uint512_t power_ten(const uint8_t n)
{
    static const uint512_t table[] = {
        pow(uint512_t(10), 0),   pow(uint512_t(10), 1),  pow(uint512_t(10), 2),  pow(uint512_t(10), 3),
        pow(uint512_t(10), 4),   pow(uint512_t(10), 5),  pow(uint512_t(10), 6),  pow(uint512_t(10), 7),
        pow(uint512_t(10), 8),   pow(uint512_t(10), 9),  pow(uint512_t(10), 10), pow(uint512_t(10), 11),
        pow(uint512_t(10), 12),  pow(uint512_t(10), 13), pow(uint512_t(10), 14), pow(uint512_t(10), 15),
        pow(uint512_t(10), 16),  pow(uint512_t(10), 17), pow(uint512_t(10), 18), pow(uint512_t(10), 19),
        pow(uint512_t(10), 20),  pow(uint512_t(10), 21), pow(uint512_t(10), 22), pow(uint512_t(10), 23),
        pow(uint512_t(10), 24),  pow(uint512_t(10), 25), pow(uint512_t(10), 26), pow(uint512_t(10), 27),
        pow(uint512_t(10), 28),  pow(uint512_t(10), 29), pow(uint512_t(10), 30), pow(uint512_t(10), 31),
        pow(uint512_t(10), 32),  pow(uint512_t(10), 33), pow(uint512_t(10), 34), pow(uint512_t(10), 35),
        pow(uint512_t(10), 36),  pow(uint512_t(10), 37), pow(uint512_t(10), 38), pow(uint512_t(10), 39),
        pow(uint512_t(10), 40),  pow(uint512_t(10), 41), pow(uint512_t(10), 42), pow(uint512_t(10), 43),
        pow(uint512_t(10), 44),  pow(uint512_t(10), 45), pow(uint512_t(10), 46), pow(uint512_t(10), 47),
        pow(uint512_t(10), 48),  pow(uint512_t(10), 49), pow(uint512_t(10), 50), pow(uint512_t(10), 51),
        pow(uint512_t(10), 52),  pow(uint512_t(10), 53), pow(uint512_t(10), 54), pow(uint512_t(10), 55),
        pow(uint512_t(10), 56),  pow(uint512_t(10), 57), pow(uint512_t(10), 58), pow(uint512_t(10), 59),
        pow(uint512_t(10), 60),  pow(uint512_t(10), 61), pow(uint512_t(10), 62), pow(uint512_t(10), 63),
        pow(uint512_t(10), 64),  pow(uint512_t(10), 65), pow(uint512_t(10), 66), pow(uint512_t(10), 67),
        pow(uint512_t(10), 68),  pow(uint512_t(10), 69), pow(uint512_t(10), 70), pow(uint512_t(10), 71),
        pow(uint512_t(10), 72),  pow(uint512_t(10), 73), pow(uint512_t(10), 74), pow(uint512_t(10), 75),
        pow(uint512_t(10), 76),  pow(uint512_t(10), 77), pow(uint512_t(10), 78), pow(uint512_t(10), 79),
        pow(uint512_t(10), 80),  pow(uint512_t(10), 81), pow(uint512_t(10), 82), pow(uint512_t(10), 83),
        pow(uint512_t(10), 84),  pow(uint512_t(10), 85), pow(uint512_t(10), 86), pow(uint512_t(10), 87),
        pow(uint512_t(10), 88),  pow(uint512_t(10), 89), pow(uint512_t(10), 90), pow(uint512_t(10), 91),
        pow(uint512_t(10), 92),  pow(uint512_t(10), 93), pow(uint512_t(10), 94), pow(uint512_t(10), 95),
        pow(uint512_t(10), 96),  pow(uint512_t(10), 97), pow(uint512_t(10), 98), pow(uint512_t(10), 99),
        pow(uint512_t(10), 100),
        // 等等
    };

    return table[n];
}

int main() {
    for (auto n = 0; n < 100; ++n)
        std::cout << power_ten(n) << "\n";
}

请注意,由于代码中包含一些特定的C++标准库函数和类,因此可能需要相应的库和头文件才能编译和运行此代码。

英文:

Instead of using costly string initialization, consider an expression that is likely to be more efficient:

Live On Coliru

#include &lt;boost/multiprecision/cpp_int.hpp&gt;
using boost::multiprecision::uint512_t;
static uint512_t power_ten(const uint8_t n)
{
static const uint512_t table[] = {
pow(uint512_t(10), 0),   pow(uint512_t(10), 1),  pow(uint512_t(10), 2),  pow(uint512_t(10), 3),
pow(uint512_t(10), 4),   pow(uint512_t(10), 5),  pow(uint512_t(10), 6),  pow(uint512_t(10), 7),
pow(uint512_t(10), 8),   pow(uint512_t(10), 9),  pow(uint512_t(10), 10), pow(uint512_t(10), 11),
pow(uint512_t(10), 12),  pow(uint512_t(10), 13), pow(uint512_t(10), 14), pow(uint512_t(10), 15),
pow(uint512_t(10), 16),  pow(uint512_t(10), 17), pow(uint512_t(10), 18), pow(uint512_t(10), 19),
pow(uint512_t(10), 20),  pow(uint512_t(10), 21), pow(uint512_t(10), 22), pow(uint512_t(10), 23),
pow(uint512_t(10), 24),  pow(uint512_t(10), 25), pow(uint512_t(10), 26), pow(uint512_t(10), 27),
pow(uint512_t(10), 28),  pow(uint512_t(10), 29), pow(uint512_t(10), 30), pow(uint512_t(10), 31),
pow(uint512_t(10), 32),  pow(uint512_t(10), 33), pow(uint512_t(10), 34), pow(uint512_t(10), 35),
pow(uint512_t(10), 36),  pow(uint512_t(10), 37), pow(uint512_t(10), 38), pow(uint512_t(10), 39),
pow(uint512_t(10), 40),  pow(uint512_t(10), 41), pow(uint512_t(10), 42), pow(uint512_t(10), 43),
pow(uint512_t(10), 44),  pow(uint512_t(10), 45), pow(uint512_t(10), 46), pow(uint512_t(10), 47),
pow(uint512_t(10), 48),  pow(uint512_t(10), 49), pow(uint512_t(10), 50), pow(uint512_t(10), 51),
pow(uint512_t(10), 52),  pow(uint512_t(10), 53), pow(uint512_t(10), 54), pow(uint512_t(10), 55),
pow(uint512_t(10), 56),  pow(uint512_t(10), 57), pow(uint512_t(10), 58), pow(uint512_t(10), 59),
pow(uint512_t(10), 60),  pow(uint512_t(10), 61), pow(uint512_t(10), 62), pow(uint512_t(10), 63),
pow(uint512_t(10), 64),  pow(uint512_t(10), 65), pow(uint512_t(10), 66), pow(uint512_t(10), 67),
pow(uint512_t(10), 68),  pow(uint512_t(10), 69), pow(uint512_t(10), 70), pow(uint512_t(10), 71),
pow(uint512_t(10), 72),  pow(uint512_t(10), 73), pow(uint512_t(10), 74), pow(uint512_t(10), 75),
pow(uint512_t(10), 76),  pow(uint512_t(10), 77), pow(uint512_t(10), 78), pow(uint512_t(10), 79),
pow(uint512_t(10), 80),  pow(uint512_t(10), 81), pow(uint512_t(10), 82), pow(uint512_t(10), 83),
pow(uint512_t(10), 84),  pow(uint512_t(10), 85), pow(uint512_t(10), 86), pow(uint512_t(10), 87),
pow(uint512_t(10), 88),  pow(uint512_t(10), 89), pow(uint512_t(10), 90), pow(uint512_t(10), 91),
pow(uint512_t(10), 92),  pow(uint512_t(10), 93), pow(uint512_t(10), 94), pow(uint512_t(10), 95),
pow(uint512_t(10), 96),  pow(uint512_t(10), 97), pow(uint512_t(10), 98), pow(uint512_t(10), 99),
pow(uint512_t(10), 100),
// etc
};
return table[n];
}
int main() {
for (auto n = 0; n&lt;100; ++n) 
std::cout &lt;&lt; power_ten(n) &lt;&lt; &quot;\n&quot;;
}

Prints

1
10
100
1000
10000
100000
...
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Bonus

Even cleaner, make it procedural:

Live On Coliru

static uint512_t power_ten(const uint8_t n) {
static auto const table = [] {
std::array&lt;uint512_t, 155&gt; tmp;
for(int exp = 0; auto&amp; el : tmp)
el = pow(uint512_t(10), exp++);
return tmp;
}();
return table.at(n); // or [n]
}

Printing the same and more.

huangapple
  • 本文由 发表于 2023年6月19日 10:46:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/76503332.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定