ginac/polynomial/eval_uvar.h

   1 #ifndef GINAC_EVAL_UPOLY_TCC
   2 #define GINAC_EVAL_UPOLY_TCC
   3 #include "upoly.hpp"
   4 #include "ring_traits.hpp"
   5
   6 namespace GiNaC
   7 {
   8
   9 /// Evaluate the polynomial using Horner rule.
  10 /// TODO:
  11 /// - a better algorithm for small polynomials (use SIMD instructions)
  12 /// - a better algorithm for large polynomials (use Karatsuba trick)
  13 /// - a better algorithm for modular polynomials (especially for small
  14 ///     moduli and GFN)
  15 template<typename T> static typename T::value_type
  16 eval(const T& p, const typename T::value_type& x)
  17 {
  18         // p(x) = c_n x^n + c_{n-1} x^{n-1} + \ldots + c_0 =
  19         // c_0 + x (c_1 + x (c_2 + x ( \ldots (c_{n-1} + c_n x) \ldots )))
  20         // (AKA Horner rule)
  21         typedef typename T::value_type ring_t;
  22         if (p.empty())
  23                 return 0;
  24         if (degree(p) == 0)
  25                 return p[0];
  26
  27         ring_t y = lcoeff(p);
  28         // read the formula above from the right to the left
  29         for (std::size_t i = p.size() - 1; i-- != 0; )
  30                 y = x*y + p[i];
  31
  32         return y;
  33 }
  34
  35 } // namespace GiNaC
  36
  37 #endif // GINAC_EVAL_UPOLY_TCC
  38