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

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

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:

  1. static uint256_t power_ten(const uint8_t n)
  2. {
  3.     static const uint256_t table[] = 
  4.     { 
  5.         1,
  6.         10
  7.         // etc
  8.     };
  10.     return table[n];
  11. }

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:

  1. #include <boost/multiprecision/cpp_int.hpp>
  3. using namespace boost::multiprecision;
  5. using Integer = int;            // Works
  6. //using Integer = uint256_t;    // Causes compiler errors
  8. template<Integer n>
  9. struct fibonacci
  10. {
  11.   static constexpr Integer value = fibonacci<n-1>::value + fibonacci<n-2>::value;
  12. };
  14. template<>
  15. struct fibonacci<0>
  16. {
  17.   static constexpr Integer value = 0;
  18. };
  20. template<>
  21. struct fibonacci<1>
  22. {
  23.   static constexpr Integer value = 1;
  24. };
  26. int main()
  27. {   
  28.     Integer a = fibonacci<40>::value;
  29.     std::cout << a << std::endl;
  30. }

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

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

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:

  1. uint256_t("1000000000000000000000000000000000000000000000000000000000000000000000000000000")

std::cout outputs the wrong value:

  1. 73663286101470436611432119930496737173840122674875487684339327936694962880512
英文:

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

  1. static uint256_t power_ten(const uint8_t n)
  2. {
  3.     static const uint256_t table[] = 
  4.     { 
  5.         1,
  6.         10
  7.         // etc
  8.     };
  10.     return table[n];
  11. }

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:

  1. #include &lt;boost/multiprecision/cpp_int.hpp&gt;
  3. using namespace boost::multiprecision;
  5. using Integer = int;            // Works
  6. //using Integer = uint256_t;    // Causes compiler errors
  8. template&lt;Integer n&gt;
  9. struct fibonacci
  10. {
  11.   static constexpr Integer value = fibonacci&lt;n-1&gt;::value + fibonacci&lt;n-2&gt;::value;
  12. };
  14. template&lt;&gt;
  15. struct fibonacci&lt;0&gt;
  16. {
  17.   static constexpr Integer value = 0;
  18. };
  20. template&lt;&gt;
  21. struct fibonacci&lt;1&gt;
  22. {
  23.   static constexpr Integer value = 1;
  24. };
  26. int main()
  27. {   
  28.     Integer a = fibonacci&lt;40&gt;::value;
  29.     std::cout &lt;&lt; a &lt;&lt; std::endl;
  30. }

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

  1. clang-14: warning: -lquadmath: &#39;linker&#39; input unused [-Wunused-command-line-argument]
  2. &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;)
  3. template&lt;Integer n&gt;
  4.                  ^
  5. &lt;source&gt;:11:28: error: declaration of constexpr static data member &#39;value&#39; requires an initializer
  6.   static constexpr Integer value = fibonacci&lt;n-1&gt;::value + fibonacci&lt;n-2&gt;::value;
  7.                            ^
  8. 2 errors generated.
  9. ASM generation compiler returned: 1
  10. &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;)
  11. template&lt;Integer n&gt;
  12.                  ^
  13. &lt;source&gt;:11:28: error: declaration of constexpr static data member &#39;value&#39; requires an initializer
  14.   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:

  1. uint256_t(&quot;1000000000000000000000000000000000000000000000000000000000000000000000000000000&quot;)

std::cout outputs the wrong value:

  1. 73663286101470436611432119930496737173840122674875487684339327936694962880512

答案1

得分: 1

以下是代码的翻译部分：

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

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

英文:

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

Live On Coliru

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

Prints

  1. 1
  2. 10
  3. 100
  4. 1000
  5. 10000
  6. 100000
  7. ...
  8. 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  9. 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  10. 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  11. 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  12. 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Bonus

Even cleaner, make it procedural:

Live On Coliru

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

Printing the same and more.

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

发表评论

匿名网友

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

确定