Compile time polynoms

Question

I (finally) recently heard about variadic templates. I'd like to know that if there is a way to make a int - polynomial with compile time operators:

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

Which coud support add, unary minus and mul operators.

[Edit] : claryfying question:

A int-polynom is basically one integer list (coefficients) :

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

I'd like this polynom to be represented by a compile time constant:

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

Let's first consider addition (in which we add elements one by one).

Is it possible to have somehow an operator+ such that:

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

?

For multiplication it would be a similar (but more complex issue).

Does someone here any experience about that?

Answer 1

After 7 years, I finally got it right, published and documented in what became a large library named aerobus, dedicated to operate on discrete algebraic structures such as polynomials.

Polynomials can be defined with coefficients in any structure providing addition, subtraction, multiplication, division and gcd.

In addition, library provides all other operations (including constexpr evalution) on polynomials.

#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

Answer 2

Here's what I came up with in 10 minutes, probably not the most elegant or efficient solution but quite straightforward one, using only boring bog-standard technique of recursion over the variadic argument list.

#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 3

I don't understand what do you exactly want (can you propose an example of use?) but I suppose that a way is define a set of types based on std::integral_constant.

By example, the unary minus can be defined as follows

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

and the add operator as follows

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

To semplify your expression, you can define a single integer as follows

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

so you can write expression (computed compile time) as follows

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

The following is a full working example

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