std ::比率在编译时的std :: ratio的功率？

Question

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

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

基于std::ratio类似操作的例子std::ratio_add.给定,两个std::ratio R1和R2此操作应该计算R1^R2if和only if R1^R2是否为有理数.如果它是不合理的,那么实现应该失败,就像当一个人尝试将两个非常大的比率相乘并且编译器说存在整数溢出时.

三个问题:

1. 您是否认为这可以在不扩大编译时间的情况下实现？
2. 使用什么算法？
3. 如何实现这个操作？

Answer 1

此计算需要两个构建块:

• 编译时整数的n次幂
• 编译时整数的第n个根

注意:我使用int作为分子和分母的类型来保存一些输入,我希望主要的观点是.我从一个有效的实现中提取以下代码,但我不能保证我不会在某个地方写错字;)

第一个是相当容易的:你使用x ^(2n)= x ^ n*x ^ n或x ^(2n + 1)= x ^ n*x ^ n*x这样,你实例化最少的模板,例如x ^ 39计算如下:x39 = x19*x19*x x19 = x9*x9*x x9 = x4*x4*x x4 = x2*x2 x2 = x1*x1 x1 = x0*x x0 = 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

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

该算法给出了最大整数s,其中s ^ N <= x

所以检查s ^ N == x.如果是,则x的第N个根是积分的,否则不是.

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

基本界面:

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

帮手:

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;
};

帮助检测乘法溢出(我认为你可以用c ++ 11 constexpr-numeric_limits交换boost-header).如果乘法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的下一个值,考虑takex overflow以消除编译器警告:

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
};

那应该是它.我们需要一个额外的帮手

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;
};

所以,我希望至少基本的想法能够实现.

Answer 2

是的,这是可能的.

设定R1 = P1/Q1,R2 = P2/Q2,R1 ^ R2 = R3 = P3/Q3.进一步假设P和Q是共素数.

R1^R2 = R1^(P2/Q2) = R3
R1 ^ P2 = R3 ^ Q2.

R1^P2是已知的并且具有素数的唯一因子2^a * 3^b * 5^c * ...注意,a, b, c如R1所示可以是负数P1/Q1.现在第一个问题是所有a,b,c是已知因子Q2的倍数.如果没有,那么你就直接失败了.如果是的话,那么R3 = 2^(a/Q2) * 3^(b/Q2) * 5^(c/Q2) ....

所有除法都是精确的或结果不存在,因此我们可以在模板中使用纯整数数学.在模板中对一个数字进行保理是相当简单的(部分专业化x%y==0).

示例:2 ^(1/2)= R3 - > a = 1,b = 0,c = 0,......和a%2 != 0- >不可能.(1/9)^(1/2) - > a = 0,b = -2,b%2 = 0,可能,结果= 3 ^( - 2/2).