使用Horner方法进行多项式求值的C++ constexpr

Question

我希望能够使用Horner方法评估多项式的​​导数并将结果用作a constexpr.这似乎非常平凡,但我遗漏了一些明显的东西,因为编译器说我超过了最大递归深度.核心递归发生在这里:

template<size_t d, size_t i, typename C, typename X>
constexpr X evalImpl(const C &c, const X &x) {
    return i >= (C::SizeAtCompileTime - 1 - d) ? 1 : evalImpl<d, i + 1, C, X>(c, x);
}

您甚至不需要知道Horner的方法就知道它在这里发生了什么,所以我尽可能地删除了代码,甚至删除了如何x使用,因为它似乎与我遇到的问题无关.

这个想法是当一个索引i等于多项式的次数Degree<C>::value减去导数的次序时d,那么递归就应该停止.否则,它应该增加索引i并再试一次.

我通过调用表单来调用上面的递归

 eval<derivative, 0>(c, x)

哪里c是类型的特征矩阵Eigen::Matrix<double,1,7>,并且x是双精度矩阵.这个想法是从0开始并基本上计算多项式的次数.

编译器错误消息的形式

In file included from /mnt/c/proj/src/main.cpp:11:0:
/mnt/c/proj/src/polynomial.h: In instantiation of 'constexpr X {anonymous}::evalImpl(const C&, const X&) [with long unsigned int d = 1ul; long unsigned int i = 898ul; C = Eigen::Matrix<double, 1, 7>; X = double]':
/mnt/c/proj/src/polynomial.h:74:108:   recursively required from 'constexpr X {anonymous}::evalImpl(const C&, const X&) [with long unsigned int d = 1ul; long unsigned int i = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double]'
/mnt/c/proj/src/polynomial.h:74:108:   required from 'constexpr X {anonymous}::evalImpl(const C&, const X&) [with long unsigned int d = 1ul; long unsigned int i = 0ul; C = Eigen::Matrix<double, 1, 7>; X = double]'
/mnt/c/proj/src/polynomial.h:109:39:   required from 'constexpr X Polynomial::eval(const C&, const X&) [with long unsigned int d = 1ul; C = Eigen::Matrix<double, 1, 7>; X = double]'
/mnt/c/proj/src/main.cpp:306:66:   required from here
/mnt/c/proj/src/polynomial.h:74:108: fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)
         return i >= (C::SizeAtCompileTime - 1 - d) ? 1 : evalImpl<d, i + 1, C, X>(c, x);

Answer 1

这里的条件:

return i >= (C::SizeAtCompileTime - 1 - d) ? 1 : evalImpl<d, i + 1, C, X>(c, x);

不是if constexpr.因此,无论是否i >= (C::SizeAtCompileTime - 1 - d),true或false其余的将始终被实例化.因此,递归不会像你想要的那样停止.

改为:

if constexpr (i >= (C::SizeAtCompileTime - 1 - d)) {
    return 1;
} else { 
    return evalImpl<d, i + 1, C, X>(c, x);  
}

编辑:

如果您无权访问C++ 17,请使用标记调度:

template<size_t d, size_t i, typename C, typename X>
constexpr X evalImpl_impl(const C &c, const X &x, std::true_type) {
    return 1;
}

template<size_t d, size_t i, typename C, typename X>
constexpr X evalImpl_impl(const C &c, const X &x, std::false_type) {
    return evalImpl_impl<d, i + 1, C, X>(c, x, std::integral_constant<bool, C::SizeAtCompileTime-1-d <= i+1>{});
}

template<size_t d, size_t i, typename C, typename X>
constexpr X evalImpl(const C &c, const X &x) {
    return evalImpl_impl(c, x, std::integral_constant<bool, C::SizeAtCompileTime-1-d <= i>{});
}