atlas  0.6
polynomials.h
Go to the documentation of this file.
1
5 /*
6  This is polynomials.h
7
8  Copyright (C) 2004,2005 Fokko du Cloux
9  part of the Atlas of Lie Groups and Representations
10
12 */
13
14 #ifndef POLYNOMIALS_H /* guard against multiple inclusions */
15 #define POLYNOMIALS_H
16
17 #include "polynomials_fwd.h"
18
19 #include <limits>
20 #include <vector>
21 #include <iostream>
22
23 namespace atlas {
24
25 namespace polynomials {
26
27 /******** constant declarations *********************************************/
28
29
30  const Degree MinusOne = ~ Degree(0); // -1 as unsigned, the degree of Zero
31
32
33
34 /******** function declarations *********************************************/
35
36
37 template<typename C>
38  bool compare(const Polynomial<C>&, const Polynomial<C>&); // lex ordering
39
40 // basic operations which test for overflow/underflow, assuming |C| is unsigned
41 template<typename C>
42  void safeAdd(C&, C); // version of |operator+=| testing for overflow
43
44 template<typename C>
45  void safeDivide(C&, C); // version of |operator/=| testing for divisibility
46
47 template<typename C>
48  void safeProd(C&, C); // version of |operator*=| testing for overflow
49
50 template<typename C>
51 void safeSubtract(C&, C);// version of |operator-=| testing for underflow
52
53
54 /******** type definitions **************************************************/
55
56
64 template<typename C> class Polynomial
65 {
66  std::vector<C> d_data;
67
68  public:
69
70 // constructors and destructors
71  Polynomial() : d_data() {} // zero polynomial
72  explicit Polynomial(C c); // constant polynomial, |c==0| handled correctly
73  Polynomial(Degree d, C c); // initialised to \$cX^d\$ (with |c!=0|)
74  Polynomial(Degree d,const Polynomial& Q); // initialised to \$X^d Q\$
75
76 // copy, assignment (default will do) and swap
77
78 template <typename U>
79  Polynomial(const Polynomial<U>& src) : d_data(src.begin(),src.end()) { }
80
81  void swap(Polynomial& other) { d_data.swap(other.d_data); }
82
83 // accessors
84  const C& operator[] (Degree i) const; // get coefficient \$X^i\$
85  const C coef (Degree i) const { return i>=d_data.size() ? C(0) : d_data[i]; }
86
87  bool operator== (const Polynomial& q) const { return d_data == q.d_data; }
88  bool operator!= (const Polynomial& q) const { return d_data != q.d_data; }
89
97  bool operator< (const Polynomial& q) const { return d_data < q.d_data; }
98
99  typename std::vector<C>::const_iterator begin() const
100  { return d_data.begin();}
101  typename std::vector<C>::const_iterator end() const { return d_data.end();}
102
103  Degree degree() const { return d_data.size()-1; }
104  Degree size() const { return d_data.size(); }
105
106  bool isZero() const { return size() == 0; } // because of reduction
107  bool multi_term () const; // whether more than one term is nonzero (printing)
108
109  // write polynomial as \$(1+cX)Q+rX^d\$, and return \$r\$
110  C up_remainder(C c, Degree d) const; // assumes \$d\geq degree()\$
111
112 // manipulators
113  C& operator[] (Degree j); // non-const version of above
114
115  Polynomial& operator+= (const Polynomial& q);
116
117  Polynomial& operator-= (const Polynomial& q);
118
119  Polynomial& subtract_from (const Polynomial& p); // *this = p - *this
120
123  Polynomial operator* (C c) const { return Polynomial (*this)*=c; }
124
125  Polynomial operator* (const Polynomial& q) const;
127  { operator*(q).swap(*this); return *this; }
129  { // avoid requiring reallocation during addition
130  return d_data.size()>=q.d_data.size()
131  ? Polynomial(*this)+=q : Polynomial(q)+=*this;
132  }
134  { // avoid requiring reallocation during addition
135  return d_data.size()>=q.d_data.size()
136  ? Polynomial(*this)-=q : (Polynomial(q)*=C(-1))+=*this;
137  }
138  Polynomial operator- () const { return Polynomial(*this)*= C(-1); }
139
140  // as |up_remainder| above, but also change polynomial into quotient \$Q\$
141  C factor_by(C c, Degree d); // assumes \$d\geq degree()\$
142
143  std::ostream& print(std::ostream& strm, const char* x) const;
144
145 protected:
146  void resize (Degree d) { d_data.resize(d,C(0)); }
148
149  }; // |template<typename C> class Polynomial|
150
151 /*
152  The following class template assumes |C| is an _unsigned_ integer type,
153  for which |std::numeric_limits<C>| is defined; it then provides safe
154  versions of shifted additive operations
155  */
156 template <typename C>
157  class Safe_Poly : public Polynomial<C>
158 {
160  public:
161  Safe_Poly() : base() {} // zero polynomial
162  explicit Safe_Poly(Degree d, C c) : base(d,c) {}
163
164  // unlike |operator+| etc., the following test for negative coefficients
165  void safeAdd(const Safe_Poly& p, Degree d, C c); // *this += c*q^d*p
166  void safeAdd(const Safe_Poly& p, Degree d = 0); // *this += q^d*p
167  void safeDivide(C c); // *this = *this/c
168  void safeQuotient(Degree d = 0); // *this = (*this + mq^d)/(q+1)
169
170  void safeSubtract(const Safe_Poly& p, Degree d, C c);
171  void safeSubtract(const Safe_Poly& p, Degree d = 0 );
172
173 }; // |template <typename C> class Safe_Poly|
174
175 } // |namespace polynomials|
176
177 } // |namespace atlas|
178
179 #include "polynomials_def.h"
180
181 #endif
Safe_Poly()
Definition: polynomials.h:161
bool operator!=(const Polynomial &q) const
Definition: polynomials.h:88
Polynomials with coefficients in |C|.
Definition: Atlas.h:121
Adjusts the size of d_data so that it corresponds to the degree + 1.
Definition: polynomials_def.h:104
Polynomial & operator+=(const Polynomial &q)
Definition: polynomials_def.h:112
Polynomial operator+(const Polynomial &q) const
Definition: polynomials.h:128
Polynomial()
Definition: polynomials.h:71
uA p
Definition: lists.cpp:26
C up_remainder(C c, Degree d) const
Definition: polynomials_def.h:207
bool operator<(const Polynomial &q) const
Operator < is the default from the standard library < on vector.
Definition: polynomials.h:97
bool operator==(const Polynomial &q) const
Definition: polynomials.h:87
Degree degree() const
Definition: polynomials.h:103
Polynomial & subtract_from(const Polynomial &p)
Definition: polynomials_def.h:146
void safeProd(C &, C)
a *= b.
Definition: polynomials_def.h:352
std::vector< C >::const_iterator end() const
Definition: polynomials.h:101
std::vector< C >::const_iterator begin() const
Definition: polynomials.h:99
a += b.
Definition: polynomials_def.h:323
const Degree MinusOne
Definition: polynomials.h:30
void resize(Degree d)
Definition: polynomials.h:146
Polynomial & operator/=(C)
Definition: polynomials_def.h:173
std::vector< C > d_data
Definition: polynomials.h:66
Polynomial< C > base
Definition: polynomials.h:159
Polynomial & operator-=(const Polynomial &q)
Definition: polynomials_def.h:130
void safeDivide(C &, C)
a /= b.
Definition: polynomials_def.h:338
const C coef(Degree i) const
Definition: polynomials.h:85
Forward class declarations for Polynomial and LaurentPolynomial.
Definition: Atlas.h:122
bool compare(const Polynomial< C > &, const Polynomial< C > &)
Polynomial comparison: whether p < q.
Definition: polynomials_def.h:252
Safe_Poly(Degree d, C c)
Definition: polynomials.h:162
std::ostream & print(std::ostream &strm, const char *x) const
Definition: polynomials_def.h:296
void swap(Polynomial &other)
Definition: polynomials.h:81
const C & operator[](Degree i) const
Definition: polynomials_def.h:83
size_t Degree
Definition: Atlas.h:122
Polynomial & operator*=(C)
Definition: polynomials_def.h:163
Degree size() const
Definition: polynomials.h:104
Definition: Atlas.h:38
Polynomial operator-() const
Definition: polynomials.h:138
void safeSubtract(C &, C)
a -= b.
Definition: polynomials_def.h:371
Polynomial operator*(C c) const
Definition: polynomials.h:123
bool multi_term() const
Definition: polynomials_def.h:235
bool isZero() const
Definition: polynomials.h:106
C factor_by(C c, Degree d)
Definition: polynomials_def.h:219
Polynomial(const Polynomial< U > &src)
Definition: polynomials.h:79