std :: ratio在编译时的std :: ratio的比率？ [英] std::ratio power of a std::ratio at compile-time?
问题描述
我有一个具有挑战性的问题，从数学，算法和metaprogramming递归的角度来看。考虑以下声明：
I have a challenging question from a mathematical, algorithmic and metaprogramming recursion point of view. Consider the following declaration:
template<class R1, class R2>
using ratio_power = /* to be defined */;
< w / cpp / numeric / ratio / ratio> std :: ratio 操作，例如 std :: ratio_add 。给定，两个 std :: ratio R1 和 R2 当且仅当 R1 ^ R2 是有理数时，操作应计算 R1 ^ R2 如果它是不合理的，那么实现应该失败，就像当一个尝试乘以两个非常大的比率，并且编译器说有一个整数溢出。
based on the example of the std::ratio operations like std::ratio_add. Given, two std::ratio R1 and R2 this operation should compute R1^R2 if and only if R1^R2 is a rational number. If it is irrational, then the implementation should fail, like when one try to multiply two very big ratios and the compiler say that there is an integer overflow.
三个问题：
- 你认为这可能没有爆炸编译
的时间吗？ - 要使用哪种算法？
- 如何实施此操作？
推荐答案
此计算需要两个构建块：
You need two building blocks for this calculation:
- 编译时整数的n次方
- 编译时整数的第n个根
注意：我使用int作为分子和分母的类型为了节省一些打字，我希望主要的观点出现。我从一个工作的实现中提取以下代码，但我不能保证我不会在某个地方打字错误;）
Note: I use int as type for numerator and denominator to save some typing, I hope the main point comes across. I extract the following code from a working implementation but I cannot guarantee that I will not make a typo somewhere ;)
第一个是很容易：你使用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
The first one is rather easy: You use x^(2n) = x^n * x^n or x^(2n+1) = x^n * x^n * x That way, you instantiate the least templates, e.g. x^39 be calculated something like that: 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
The second one is a bit tricky and works with a bracketing algorithm: Given x and N we want to find a number r so that r^N = x
- 设置包含解决方案的区间[low，high] [1,1 + x / N]
- 计算中点均值=（低+高）/ 2
- = x
- 如果是，将间隔设置为[low，mean]
- 如果不是，将间隔设置为[mean + 1 ，high]
- set the interval [low, high] that contains the solution to [1, 1 + x / N]
- calculate the midpoint mean = (low + high) / 2
- determine, if mean^N >= x
- if yes, set the interval to [low, mean]
- if not, set the interval to [mean+1, high]
此算法提供最大整数s ^ N <= x
This algorithm gives the largest integer s that folfills s^N <= x
那么检查s ^ N == x。如果是的话，x的第N个根是积分的，否则不是。
So check whether s^N == x. If yes, the N-th root of x is integral, otherwise not.
现在让我们把它写为编译时程序：
Now lets write that as compile-time program:
基本接口：
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; };递归终点，其中间隔只包含一个条目：
endpoint of recursion where the interval consists of only one entry:
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。
helper to detect multiplication overflow (You can exchange the boost-header for c++11 constexpr-numeric_limits, I think). Returns true, if the multiplication a * b would overflow.
#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> BNow we need to implement calculate_left that calculates whether the solution of x^N is left of mean or right of mean. We want to be able to calculate arbitrary roots so a naive implementation like static_pow > x will overflow very quickly and give wrong results. Therefore we use the following scheme: We want to calculate if x^N > B
- 设置A = x和i = 1
- 如果A> = B，我们已经完成了 - > A ^ N肯定会大于B
-
- 如果是 - > A ^ N肯定大于B
- 如果不是 - > A * = x和i + 1
- set A = x and i = 1
- if A >= B we are already finished -> A^N will surely be larger than B
- will A * x overflow?
- if yes -> A^N will surely be larger than B
- if not -> A *= x and i += 1
现在可以将其作为元程序写入
now lets write this as metaprogram
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
endpoint where 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溢出到帐户中以消除编译器警告： / p>
helper to calculate the next value of x * A, takex overflow into account to eliminate compiler warnings:
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 };所以，应该是。我们需要一个额外的帮助器
So, that should be it. We need an additional 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如下：
Now we can implement ratio_pow as follows:
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; };所以，我希望至少基本的想法出现。
So, I hope at least the basic idea comes across.
这篇关于std :: ratio在编译时的std :: ratio的比率？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
