31fe591a0af17bb73f3480f0843bb51cf4e17845
[ginac.git] / ginac / polynomial / eval_uvar.h
1 #ifndef GINAC_EVAL_UPOLY_TCC
2 #define GINAC_EVAL_UPOLY_TCC
3 #include "upoly.h"
4 #include "ring_traits.h"
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