编译时多项式

Question

我（终于）最近听说了可变参数模板。我想知道是否有一种方法可以使用编译时运算符创建 int 多项式：

template <int... coefs> 
struct polynom {}

可以支持加法、一元减法和乘法运算符。

[编辑]：澄清问题：

int 多项式基本上是一个整数列表（系数）：

1 + 2x^2 - 7x^5 <=> (1, 0, 2, 0, 0, -7)

我希望这个多项式由编译时间常数表示：

polynom<1,0,2,0,0,-7>

我们首先考虑加法（将元素逐个相加）。

是否有可能以某种方式拥有一个运算符+，使得：

polynom<1,0,1> + polynom<-1,2,1,3> -> polynom<0, 2, 2, 3>

？

对于乘法来说，这将是一个类似的（但更复杂的问题）。

这里有人有这方面的经验吗？

Answer 1

这是我在 10 分钟内想出的解决方案，可能不是最优雅或最有效的解决方案，但非常简单，仅使用无聊的沼泽标准递归技术对可变参数列表进行递归。

#include <iostream>

// our polynomials are little-endian: the first coefficient is for power 0,
// the second one is for power 1 etc
// The empty list corresponds to the zero polynomial
template <int ... coeff> struct Poly {};

// Print it out
template <int ... coeff> std::ostream& operator<< (std::ostream& os, Poly<coeff...>);
template <> std::ostream& operator<< (std::ostream& os, Poly<>) { return os; }
template <int coeff0, int ... coeff> std::ostream& operator<< (std::ostream& os, Poly<coeff0, coeff...>) {
    os << coeff0 << " " << Poly<coeff...>();
}

// For number coeff0 and polynomial poly(x), return coeff0 + x * poly(x) 
template <int coeff0, class poly> struct poly_shift;
template <int coeff0, int ... coeff> struct poly_shift<coeff0, Poly<coeff...>>{
    using type = Poly<coeff0, coeff...>;
};

// Addition of polynomials 
template <class poly1, class poly2>
struct poly_add;
template <>
struct poly_add<Poly<>, Poly<>> { using type = Poly<>; };
template <int ... coeff>
struct poly_add<Poly<coeff...>, Poly<>> { using type = Poly<coeff...>; };
template <int ... coeff>
struct poly_add<Poly<>, Poly<coeff...>> { using type = Poly<coeff...>; };
template <int coeff_l0, int coeff_r0, int... coeff_l, int... coeff_r>
struct poly_add<Poly<coeff_l0, coeff_l...>, Poly<coeff_r0, coeff_r...>> {
    using type = typename poly_shift<coeff_l0 + coeff_r0, typename poly_add<Poly<coeff_l...>, Poly<coeff_r...>>::type>::type;
};

// convenient infix operator for values 
template <class poly1, class poly2>
constexpr typename poly_add<poly1, poly2>::type  operator+ (poly1 p1, poly2 p2) { return {}; }

// test it
int main()
{
   Poly <1,2,3> a;
   Poly <3,4,5,6> b;
   std::cout << (a+b);
}

Answer 2

我不明白你到底想要什么（你能提出一个使用示例吗？）但我认为一种方法是基于

std::integral_constant

定义一组类型。

举例来说，一元减号可以定义如下

template <typename T>
struct uminus
   : std::integral_constant<typename T::value_type, - T::value>
 { };

以及添加运算符如下

template <typename T1, typename T2>
struct add
   : std::integral_constant<typename T1::value_type, T1::value + T2::value>
 { };

为了简化表达式，您可以定义一个整数，如下所示

template <int I>
struct i : std::integral_constant<int, I>
 { };

所以你可以编写表达式（计算编译时间）如下

constexpr auto val = add<i<5>, uminus<i<3>>>::value;

以下是完整的工作示例

#include <iostream>
#include <type_traits>

template <typename T>
struct uminus
   : std::integral_constant<typename T::value_type, - T::value>
 { };

template <typename T1, typename T2>
struct add
   : std::integral_constant<typename T1::value_type, T1::value + T2::value>
 { };

template <int I>
struct i : std::integral_constant<int, I>
 { };

int main ()
 {
   constexpr auto val = add<i<5>, uminus<i<3>>>::value;

   std::cout << val << std::endl; // print 2
 }

Answer 3

7年后，我终于做对了，发布了并记录了，后来成为一个名为

aerobus

的大型图书馆，专门用于运算多项式等离散代数结构。

可以用任何结构中的系数定义多项式，提供加法、减法、乘法、除法和 gcd。

此外，库还提供多项式上的所有其他运算（包括 constexpr 求值）。

#include <cstdio>

using namespace aerobus;
// 1 + x - x^2
using P1 = polynomial<i32>::val<i32::val<-1>, i32::val<1>, i32::val<1>>;
// 1 + x + x^2
using P2 = polynomial<i32>::val<i32::val<1>, i32::val<1>, i32::val<1>>;
// 2 + 2x
using SUM = add_t<P1, P2>;

int main() {
    ::printf("[%s](1) = %lf\n", SUM::to_string().c_str(), SUM::eval<double>(1));
}

[2 x + 2] (1) = 4.000000