c++ - 编译时 std::ratio 的 std::ratio 功率？

Question

从数学、算法和元编程递归的角度来看，我有一个具有挑战性的问题。考虑以下声明:

template<class R1, class R2>
using ratio_power = /* to be defined */;

基于 std::ratio 的示例类似 std::ratio_add 的操作.给定两个 std::ratio R1 和 R2 当且仅当 R1^R2 是有理数。如果它是不合理的，那么实现应该会失败，就像当一个人试图将两个非常大的比率相乘时，编译器会说存在整数溢出。

三个问题:

1. 你认为这在不爆炸编译的情况下是可能的吗时间？
2. 使用什么算法？
3. 如何实现这个操作？

Answer 1

此计算需要两个构建 block :

• 编译时整数的 n 次方
• 编译时整数的 n 次方根

注意:我使用 int 作为分子和分母的类型以节省一些输入，我希望主要观点能得到理解。我从一个有效的实现中提取了以下代码，但我不能保证我不会在某处打错字；)

第一个相当简单:您使用 x^(2n) = x^n * x^n 或 x^(2n+1) = x^n * x^n * x这样，您实例化最少的模板，例如x^39 可以这样计算:x39 = x19 * x19 * xx19 = x9 * x9 * xx9 = x4 * x4 * xx4 = x2 * x2x2 = x1 * x1x1 = x0 * xx0 = 1

template <int Base, int Exponent>
struct static_pow
{
  static const int temp = static_pow<Base, Exponent / 2>::value;
  static const int value = temp * temp * (Exponent % 2 == 1 ? Base : 1);
};

template <int Base>
struct static_pow<Base, 0>
{
  static const int value = 1;
};

第二个有点棘手，它使用包围算法:给定 x 和 N 我们想找到一个数 r 使得 r^N = x

• 将包含解的区间[low, high]设置为[1, 1 + x/N]
• 计算中点平均值 = (low + high)/2
• 确定，如果 mean^N >= x
  • 如果是，将区间设置为[low, mean]
  • 如果不是，设置区间为[mean+1, high]
• 如果区间只有一个数，则计算结束
• 否则，再次迭代

该算法给出满足 s^N <= x 的最大整数 s

所以检查是否 s^N == x。如果是，则 x 的 N 次方根是整数，否则不是。

现在让我们把它写成编译时程序:

基本界面:

template <int x, int N>
struct static_root : static_root_helper<x, N, 1, 1 + x / N> { };

helper :

template <int x, int N, int low, int high>
struct static_root_helper
{
  static const int mean = (low + high) / 2;
  static const bool is_left = calculate_left<mean, N, x>::value;
  static const int value = static_root_helper<x, N, (is_left ? low : mean + 1), (is_left ? mean, high)>::value;
};

递归的终点，其中区间只包含一个条目:

template <int x, int N, int mid>
struct static_root_helper<x, N, mid, mid>
{
  static const int value = mid;
};

检测乘法溢出的帮助程序(我认为您可以将 boost-header 替换为 c++11 constexpr-numeric_limits)。如果乘法 a * b 溢出，则返回 true。

#include "boost/integer_traits.hpp"

template <typename T, T a, T b>
struct mul_overflow
{
  static_assert(std::is_integral<T>::value, "T must be integral");
  static const bool value = (a > boost::integer_traits<T>::const_max / b);
};

现在我们需要实现 calculate_left 来计算 x^N 的解是在均值左侧还是在均值右侧。我们希望能够计算任意根，这样像 static_pow > x 这样的简单实现会很快溢出并给出错误的结果。因此，我们使用以下方案:我们要计算是否 x^N > B

• 设 A = x 且 i = 1
• 如果 A >= B 我们已经完成了 -> A^N 肯定会大于 B
• A * x 会溢出吗？
  • 如果是 -> A^N 一定会大于 B
  • 如果不是 -> A *= x 且 i += 1
• 如果 i == N，我们就完成了，我们可以和 B 做一个简单的比较

现在让我们把它写成元程序

template <int A, int N, int B>
struct calculate_left : calculate_left_helper<A, 1, A, N, B, (A >= B)> { };

template <int x, int i, int A, int N, int B, bool short_circuit>
struct calulate_left_helper
{
  static const bool overflow = mul_overflow<int, x, A>::value;
  static const int next = calculate_next<x, A, overflow>::value;
  static const bool value = calculate_left_helper<next, i + 1, A, N, B, (overflow || next >= B)>::value;
};

端点 i == N

template <int x, int A, int N, int B, bool short_circuit>
struct calculate_left_helper<x, N, A, N, B, short_circuit>
{
  static const bool value = (x >= B);
};

短路端点

template <int x, int i, int A, int N, int B>
struct calculate_down_helper<x, i, A, N, B, true>
{
  static const bool value = true;
};

template <int x, int A, int N, int B>
struct calculate_down_helper<x, N, A, N, B, true>
{
  static const bool value = true;
};

帮助计算 x * A 的下一个值，考虑溢出以消除编译器警告:

template <int a, int b, bool overflow>
struct calculate_next
{
  static const int value = a * b;
};

template <int a, int b>
struct calculate_next<a, b, true>
{
  static const int value = 0; // any value will do here, calculation will short-circuit anyway
};

所以，应该是这样。我们需要一个额外的 helper

template <int x, int N>
struct has_integral_root
{
  static const int root = static_root<x, N>::value;
  static const bool value = (static_pow<root, N>::value == x);
};

现在我们可以按如下方式实现ratio_pow:

template <typename, typename> struct ratio_pow;

template <int N1, int D1, int N2, int D2>
struct ratio_pow<std::ratio<N1, D1>, std::ratio<N2, D2>>
{
  // ensure that all roots are integral
  static_assert(has_integral_root<std::ratio<N1, D1>::num, std::ratio<N2, D2>::den>::value, "numerator has no integral root");
  static_assert(has_integral_root<std::ratio<N1, D1>::den, std::ratio<N2, D2>::den>::value, "denominator has no integral root");
  // calculate the "D2"-th root of (N1 / D1)
  static const int num1 = static_root<std::ratio<N1, D1>::num, std::ratio<N2, D2>::den>::value;
  static const int den1 = static_root<std::ratio<N1, D1>::den, std::ratio<N2, D2>::den>::value;
  // exchange num1 and den1 if the exponent is negative and set the exp to the absolute value of the exponent
  static const bool positive_exponent = std::ratio<N2, D2>::num >= 0;
  static const int num2 = positive_exponent ? num1 : den1;
  static const int den2 = positive_exponent ? den1 : num1;
  static const int exp = positive_exponent ? std::ratio<N2, D2>::num : - std::ratio<N2, D2>::num;
  //! calculate (num2 / den2) ^ "N2"
  typedef std::ratio<static_pow<num2, exp>::value, static_pow<den2, exp>::value> type;
};

所以，我希望至少能表达基本的想法。