用于使用 Horner 方法进行多项式计算的 C++ constexpr
C++ constexpr for polynomial evaluation with Horner's method
我希望能够使用 Horner 方法计算多项式的导数并将结果用作 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);
这里的条件:
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>{});
}
我希望能够使用 Horner 方法计算多项式的导数并将结果用作 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);
这里的条件:
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>{});
}