canonicalform.h
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  * @file canonicalform.h
5  *
6  * Header for factory's main class CanonicalForm
7 **/
8 #ifndef INCL_CANONICALFORM_H
9 #define INCL_CANONICALFORM_H
10 
11 // #include "config.h"
12 
13 #ifndef NOSTREAMIO
14 # ifdef HAVE_IOSTREAM
15 # include <iostream>
16 # define OSTREAM std::ostream
17 # define ISTREAM std::istream
18 # elif defined(HAVE_IOSTREAM_H)
19 # include <iostream.h>
20 # define OSTREAM ostream
21 # define ISTREAM istream
22 # endif
23 #endif /* NOSTREAMIO */
24 
25 #include <stdint.h>
26 
27 #include "cf_defs.h"
28 #include "variable.h"
29 #include <factory/cf_gmp.h>
35 #ifdef HAVE_OMALLOC
36 #include <omalloc/omallocClass.h>
37 #endif
38 
39 /*BEGINPUBLIC*/
40 
41 #undef CF_INLINE
42 #define CF_INLINE
43 #undef CF_NO_INLINE
44 #define CF_NO_INLINE
45 
46 /*ENDPUBLIC*/
47 
48 #ifdef CF_USE_INLINE
49 #undef CF_INLINE
50 #define CF_INLINE inline
51 #else
52 #undef CF_INLINE
53 #define CF_INLINE
54 #endif
55 
56 /*BEGINPUBLIC*/
57 
58 class InternalCF;
59 
60 inline int is_imm ( const InternalCF * const ptr )
61 {
62  // returns 0 if ptr is not immediate
63  return ( ((int)((intptr_t)ptr)) & 3 );
64 }
65 
66 
67 /**
68  * factory's main class
69  *
70  * a CanonicalForm can represent a polynomial over or a constant in F_p,
71  * F_p(alpha), GF (F_p[t]/(Conway polynomial)), Z, or Q
72  *
73  * @sa int_poly.h, variable.h, ffops.h, gfops.h, imm.h, int_int.h, int_rat.h
74 **/
76 #ifdef HAVE_OMALLOC
77  : public omallocClass
78 #endif
79 {
80 private:
82 public:
83  // constructors, destructors, selectors
87  CF_INLINE CanonicalForm( const int );
88  CF_INLINE CanonicalForm( const long );
89  CF_INLINE CanonicalForm( const Variable & );
90  CF_INLINE CanonicalForm( const Variable &, int );
91  CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
92 
94 
95  InternalCF* getval() const; // use with caution !!!
96 
97  CanonicalForm deepCopy() const;
98 
99  void mpzval(mpz_t val) const;
100  // predicates
101  CF_NO_INLINE bool isOne() const;
102  CF_NO_INLINE bool isZero() const;
103  inline bool isImm() const { return is_imm( value ); };
104 
105  bool inZ() const;
106  bool inQ() const;
107  bool inFF() const;
108  bool inGF() const;
109  bool inBaseDomain() const;
110  bool inExtension() const;
111  bool inCoeffDomain() const;
112  bool inPolyDomain() const;
113  bool inQuotDomain() const;
114 
115  bool isFFinGF() const;
116  bool isUnivariate() const;
117  bool isHomogeneous() const;
118 
119  // conversion functions
120  long intval() const;
121  CanonicalForm mapinto () const;
122 
123  CanonicalForm lc () const;
124  CanonicalForm Lc () const;
125  CanonicalForm LC () const;
126  CanonicalForm LC ( const Variable & v ) const;
127 
128  int degree () const;
129  int degree ( const Variable & v ) const;
130 
131  CanonicalForm tailcoeff () const;
132  CanonicalForm tailcoeff ( const Variable & v ) const;
133  int taildegree () const;
134 
135  int level () const;
136  Variable mvar () const;
137 
138  CanonicalForm num () const;
139  CanonicalForm den () const;
140 
141  // assignment operators
143  CF_NO_INLINE CanonicalForm& operator = ( const long );
144 
150  CanonicalForm& div ( const CanonicalForm& );
151  CanonicalForm& tryDiv (const CanonicalForm&, const CanonicalForm&, bool& );
152  CanonicalForm& mod ( const CanonicalForm& );
153 
154  // evaluation operators
155  CanonicalForm operator () ( const CanonicalForm & f ) const;
156  CanonicalForm operator () ( const CanonicalForm & f, const Variable & v ) const;
157 
158  CanonicalForm operator [] ( int i ) const;
159 
160  CanonicalForm deriv() const;
161  CanonicalForm deriv( const Variable & x ) const;
162 
163  int sign() const;
164  CanonicalForm sqrt() const;
165  int ilog2() const;
166 
167  // comparison operators
168  friend bool operator == ( const CanonicalForm&, const CanonicalForm& );
169  friend bool operator != ( const CanonicalForm&, const CanonicalForm& );
170  friend bool operator > ( const CanonicalForm&, const CanonicalForm& );
171  friend bool operator < ( const CanonicalForm&, const CanonicalForm& );
172 
173  // arithmetic operators
175 
176  friend void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
177  friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
178  friend bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );
179 
180  friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
182 
183  // input/output
184 #ifndef NOSTREAMIO
185  void print( OSTREAM&, char * ) const;
186  void print( OSTREAM& ) const;
187  friend OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
189 #endif /* NOSTREAMIO */
190 
191  // obsolete methods
192  CanonicalForm genZero() const;
193  CanonicalForm genOne() const;
194 
195  friend class CFIterator;
196 };
197 
199 operator + ( const CanonicalForm&, const CanonicalForm& );
200 
202 operator - ( const CanonicalForm&, const CanonicalForm& );
203 
205 operator * ( const CanonicalForm&, const CanonicalForm& );
206 
208 operator / ( const CanonicalForm&, const CanonicalForm& );
209 
211 operator % ( const CanonicalForm&, const CanonicalForm& );
212 
214 div ( const CanonicalForm&, const CanonicalForm& );
215 
217 mod ( const CanonicalForm&, const CanonicalForm& );
218 
219 /*ENDPUBLIC*/
220 
221 #ifdef CF_USE_INLINE
222 #include "cf_inline.cc"
223 #endif
224 
225 /*BEGINPUBLIC*/
226 
227 //{{{ function declarations from canonicalform.cc
228 CanonicalForm blcm ( const CanonicalForm & f, const CanonicalForm & g );
229 
230 CanonicalForm power ( const CanonicalForm & f, int n );
231 
232 CanonicalForm power ( const Variable & v, int n );
233 //}}}
234 
235 //{{{ function declarations from cf_gcd.cc
236 CanonicalForm gcd ( const CanonicalForm&, const CanonicalForm& );
237 
238 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g );
239 
240 CanonicalForm lcm ( const CanonicalForm&, const CanonicalForm& );
241 
242 CanonicalForm pp ( const CanonicalForm& );
243 
245 
246 CanonicalForm content ( const CanonicalForm&, const Variable& );
247 
249 
250 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x );
251 //}}}
252 
253 //{{{ function declarations from cf_ops.cc
254 CanonicalForm swapvar ( const CanonicalForm &, const Variable &, const Variable & );
255 
256 CanonicalForm replacevar ( const CanonicalForm &, const Variable &, const Variable & );
257 
258 int getNumVars( const CanonicalForm & f );
259 
261 
262 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
263 
264 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) );
265 
266 int * degrees ( const CanonicalForm & f, int * degs = 0 );
267 
268 int totaldegree ( const CanonicalForm & f );
269 
270 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
271 
272 int size ( const CanonicalForm & f, const Variable & v );
273 
274 int size ( const CanonicalForm & f );
275 
277 
278 bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
279 
280 CanonicalForm leftShift (const CanonicalForm& F, int n);
281 //}}}
282 
283 //{{{ inline functions corresponding to CanonicalForm methods
284 //{{{ docu
285 //
286 // - inline functions corresponding to CanonicalForm methods.
287 //
288 // These function exist for convenience only and because it is
289 // more beautiful to write 'degree( f )' than 'f.degree()'.
290 //
291 //}}}
292 inline CanonicalForm
293 lc ( const CanonicalForm & f ) { return f.lc(); }
294 
295 inline CanonicalForm
296 Lc ( const CanonicalForm & f ) { return f.Lc(); }
297 
298 inline CanonicalForm
299 LC ( const CanonicalForm & f ) { return f.LC(); }
300 
301 inline CanonicalForm
302 LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
303 
304 inline int
305 degree ( const CanonicalForm & f ) { return f.degree(); }
306 
307 inline int
308 degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
309 
310 inline int
311 taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
312 
313 inline CanonicalForm
314 tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
315 
316 inline CanonicalForm
317 tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
318 
319 inline int
320 level ( const CanonicalForm & f ) { return f.level(); }
321 
322 inline Variable
323 mvar ( const CanonicalForm & f ) { return f.mvar(); }
324 
325 inline CanonicalForm
326 num ( const CanonicalForm & f ) { return f.num(); }
327 
328 inline CanonicalForm
329 den ( const CanonicalForm & f ) { return f.den(); }
330 
331 inline int
332 sign ( const CanonicalForm & a ) { return a.sign(); }
333 
334 inline CanonicalForm
335 deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
336 
337 inline CanonicalForm
338 sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
339 
340 inline int
341 ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
342 
343 inline CanonicalForm
344 mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
345 //}}}
346 
347 //{{{ inline functions
348 inline CanonicalForm
349 head ( const CanonicalForm & f )
350 {
351  if ( f.level() > 0 )
352  return power( f.mvar(), f.degree() ) * f.LC();
353  else
354  return f;
355 }
356 
357 inline int
358 headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
359 
360 
361 //}}}
362 
363 //{{{ other function declarations
364 void setCharacteristic( int c ); // -> Fp && Q
365 void setCharacteristic( int c, int n ); // -> PrimePower
366 void setCharacteristic( int c, int n, char name ); // -> GF(q)
367 
368 int getCharacteristic();
369 int getGFDegree();
371 
372 void On( int );
373 void Off( int );
374 bool isOn( int );
375 //}}}
376 
377 //{{{ type definitions
395 //}}}
396 
397 /*ENDPUBLIC*/
398 
399 #endif /* ! INCL_CANONICALFORM_H */
int ilog2() const
int CanonicalForm::ilog2 () const
bool inGF() const
long intval() const
conversion functions
List< CFList > ListCFList
List< CanonicalForm > CFList
List< Variable > Varlist
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
friend bool operator==(const CanonicalForm &, const CanonicalForm &)
operator ==() - compare canonical forms on (in)equality.
const poly a
Definition: syzextra.cc:212
CanonicalForm Lc() const
friend OSTREAM & operator<<(OSTREAM &, const CanonicalForm &)
int level(const CanonicalForm &f)
CanonicalForm & operator%=(const CanonicalForm &)
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
void On(int)
switches
#define CF_INLINE
Definition: canonicalform.h:53
Matrix< CanonicalForm > CFMatrix
CanonicalForm num(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
ListIterator< CanonicalForm > CFListIterator
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:646
CF_INLINE CanonicalForm operator+(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs...
Definition: cf_inline.cc:496
factory&#39;s class for variables
Definition: factory.h:115
bool isImm() const
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
friend CF_NO_INLINE CanonicalForm operator-(const CanonicalForm &)
CF_INLINE CanonicalForm operator - ( const CanonicalForm & cf )
Definition: cf_inline.cc:438
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
ListIterator< CFAFactor > CFAFListIterator
CF_NO_INLINE CanonicalForm operator/(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:529
char N base
Definition: ValueTraits.h:144
factory&#39;s main class
Definition: canonicalform.h:75
CF_INLINE CanonicalForm operator*(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:517
CanonicalForm & operator-=(const CanonicalForm &)
List< CFFactor > CFFList
Variable mvar(const CanonicalForm &f)
Array< CanonicalForm > CFArray
g
Definition: cfModGcd.cc:4031
CanonicalForm operator()(const CanonicalForm &f) const
operator ()() - evaluation operator.
friend bool divremt(const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm &)
ListIterator< CFList > ListCFListIterator
ListIterator< CFFactor > CFFListIterator
CanonicalForm Lc(const CanonicalForm &f)
void mpzval(mpz_t val) const
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
void setCharacteristic(int c)
Definition: cf_char.cc:23
friend bool operator<(const CanonicalForm &, const CanonicalForm &)
void Off(int)
switches
int getCharacteristic()
Definition: cf_char.cc:51
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm mapinto() const
bool isOn(int)
switches
CanonicalForm lc(const CanonicalForm &f)
friend void divrem(const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm &)
#define CF_NO_INLINE
Definition: canonicalform.h:44
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible ...
#define M
Definition: sirandom.c:24
int taildegree(const CanonicalForm &f)
CanonicalForm num() const
num() returns the numerator of CO if CO is a rational number, CO itself otherwise.
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
bool inBaseDomain() const
bool inPolyDomain() const
friend ISTREAM & operator>>(ISTREAM &, CanonicalForm &)
ListIterator< int > IntListIterator
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int headdegree(const CanonicalForm &f)
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) ...
Definition: cf_ops.cc:402
AFactor< CanonicalForm > CFAFactor
CanonicalForm & operator*=(const CanonicalForm &)
bool isUnivariate() const
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
void print(OSTREAM &, char *) const
input/output
friend bool operator!=(const CanonicalForm &, const CanonicalForm &)
operator !=() returns true iff lhs does not equal rhs.
definition of configurable inline ‘CanonicalForm’ methods.
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
bool inQuotDomain() const
friend bool operator>(const CanonicalForm &, const CanonicalForm &)
operator >() - compare canonical forms.
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
CanonicalForm mapinto(const CanonicalForm &f)
bool inExtension() const
CanonicalForm getGFGenerator()
Definition: cf_char.cc:62
char name(const Variable &v)
Definition: factory.h:178
factory switches.
CanonicalForm sqrt(const CanonicalForm &a)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inFF() const
CF_INLINE CanonicalForm()
CF_INLINE CanonicalForm::CanonicalForm ()
Definition: cf_inline.cc:126
int ilog2(const CanonicalForm &a)
CanonicalForm & operator+=(const CanonicalForm &)
assignment operators
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
InternalCF * value
Definition: canonicalform.h:81
CF_NO_INLINE ~CanonicalForm()
CF_INLINE CanonicalForm::~CanonicalForm ()
Definition: cf_inline.cc:253
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm operator[](int i) const
operator []() - return i&#39;th coefficient from CO.
operations on variables
CanonicalForm & mod(const CanonicalForm &)
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CF_NO_INLINE CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) ...
Definition: cf_inline.cc:553
Array< int > Intarray
CanonicalForm head(const CanonicalForm &f)
CanonicalForm den() const
den() returns the denominator of CO if CO is a rational number, 1 (from the current domain!) otherwis...
bool inQ() const
friend CanonicalForm bgcd(const CanonicalForm &, const CanonicalForm &)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm den(const CanonicalForm &f)
CanonicalForm & div(const CanonicalForm &)
CF_NO_INLINE CanonicalForm operator-(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:505
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:683
Factor< CanonicalForm > CFFactor
bool inZ() const
predicates
bool isHomogeneous() const
ListIterator< Variable > VarlistIterator
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:60
int getGFDegree()
Definition: cf_char.cc:56
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm tailcoeff(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
#define OSTREAM
Definition: canonicalform.h:16
CanonicalForm genZero() const
genOne(), genZero()
int level() const
level() returns the level of CO.
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) ...
Definition: cf_ops.cc:440
friend CanonicalForm bextgcd(const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm &)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
CanonicalForm genOne() const
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:94
int degree(const CanonicalForm &f)
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm LC(const CanonicalForm &f)
int taildegree() const
taildegree() returns -1 for the zero polynomial, 0 if CO is in a base domain, otherwise the least deg...
List< CFAFactor > CFAFList
CanonicalForm & operator/=(const CanonicalForm &)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
InternalCF * getval() const
friend bool tryDivremt(const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible ...
List< int > IntList
bool isFFinGF() const
int sign() const
int CanonicalForm::sign () const
#define ISTREAM
Definition: canonicalform.h:17
CanonicalForm lcm(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:343
int sign(const CanonicalForm &a)
CanonicalForm deepCopy() const
CF_NO_INLINE CanonicalForm & operator=(const CanonicalForm &)
CF_INLINE CanonicalForm & CanonicalForm::operator = ( const CanonicalForm & cf )
Definition: cf_inline.cc:272
CF_NO_INLINE CanonicalForm operator%(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:540
bool inCoeffDomain() const
CanonicalForm LC() const
CanonicalForm gcd(const CanonicalForm &, const CanonicalForm &)
Definition: cf_gcd.cc:262