3 * Interface to polynomials with integer and modular coefficients. */
6 * GiNaC Copyright (C) 1999-2010 Johannes Gutenberg University Mainz, Germany
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
26 #include "ring_traits.h"
30 #include <cln/integer.h>
31 #include <cln/integer_io.h>
32 #include <cln/modinteger.h>
41 typedef std::vector<cln::cl_I> upoly;
42 typedef std::vector<cln::cl_MI> umodpoly;
44 template<typename T> static std::size_t degree(const T& p)
49 template<typename T> static typename T::value_type lcoeff(const T& p)
51 bug_on(p.empty(), "lcoeff of a zero polynomial is undefined");
52 return p[p.size() - 1];
55 template<typename T> static typename T::reference lcoeff(T& p)
57 bug_on(p.empty(), "lcoeff of a zero polynomial is undefined");
58 return p[p.size() - 1];
61 template<typename T> static typename T::value_type max_coeff(const T& p)
63 bug_on(p.empty(), "max_coeff of a zero polynomial is undefined");
64 typename T::value_type curr = p[p.size() - 1];
65 for (std::size_t i = p.size(); i-- != 0; ) {
74 // Canonicalize the polynomial, i.e. remove leading zero coefficients
75 template<typename T> static void
76 canonicalize(T& p, const typename T::size_type hint =
77 std::numeric_limits<typename T::size_type>::max())
82 std::size_t i = p.size() - 1;
83 // Be fast if the polynomial is already canonicalized
108 bug_on(!zerop(p.at(i)), "p[" << i << "] = " << p[i] << " != 0 would be erased.");
110 typename T::const_iterator it = p.begin() + i;
111 for (std::size_t k = i; it != p.end(); ++it, ++k) {
112 bug_on(!zerop(*it), "p[" << k << "] = " << p[k] << " != 0 "
116 p.erase(p.begin() + i, p.end());
118 bug_on(!p.empty() && zerop(lcoeff(p)), "oops, lcoeff(p) = 0");
121 // Multiply a univariate polynomial p \in R[x] with a constant c \in R
122 template<typename T> static T&
123 operator*=(T& p, const typename T::value_type& c)
131 if (c == the_one(p[0]))
134 for (std::size_t i = p.size(); i-- != 0; )
140 /// Divide the polynomial @a p by the ring element @a c, put the result
141 /// into @a r. If @a p is not divisible by @a c @a r is undefined.
142 template<typename T> bool divide(T& r, const T& p, const typename T::value_type& c)
148 if (r.size() != p.size())
150 bool divisible = true;
151 for (std::size_t i = p.size(); i-- != 0; ) {
152 divisible = div(r[i], p[i], c);
159 template<typename T> bool divide(T& p, const typename T::value_type& c)
164 bool divisible = divide(r, p, c);
170 // Convert Z[x] -> Z/p[x]
173 make_umodpoly(umodpoly& up, const upoly& p, const cln::cl_modint_ring& R)
175 for (std::size_t i = p.size(); i-- != 0; )
176 up[i] = R->canonhom(p[i]);
182 #endif // GINAC_UPOLY_H