My Project
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 #include "si_log2.h"
36 #ifdef HAVE_OMALLOC
37 #ifndef XMEMORY_H
38 #include "omalloc/omallocClass.h"
39 #endif
40 #endif
41 
42 /*BEGINPUBLIC*/
43 
44 #undef CF_INLINE
45 #define CF_INLINE
46 #undef CF_NO_INLINE
47 #define CF_NO_INLINE
48 
49 /*ENDPUBLIC*/
50 
51 #ifdef CF_USE_INLINE
52 #ifndef __CYGWIN__
53 #undef CF_INLINE
54 #define CF_INLINE inline
55 #endif
56 #else
57 #undef CF_INLINE
58 #define CF_INLINE
59 #endif
60 
61 /*BEGINPUBLIC*/
62 
63 class InternalCF;
64 
65 inline int is_imm ( const InternalCF * const ptr )
66 {
67  // returns 0 if ptr is not immediate
68  return ( ((int)((intptr_t)ptr)) & 3 );
69 }
70 
71 
72 /**
73  * factory's main class
74  *
75  * a CanonicalForm can represent a polynomial over or a constant in F_p,
76  * F_p(alpha), GF (F_p[t]/(Conway polynomial)), Z, or Q
77  *
78  * @sa int_poly.h, variable.h, ffops.h, gfops.h, imm.h, int_int.h, int_rat.h
79 **/
81 #ifdef HAVE_OMALLOC
82 #ifndef XMEMORY_H
83  : public omallocClass
84 #endif
85 #endif
86 {
87 private:
89 public:
90  // constructors, destructors, selectors
94  CF_INLINE CanonicalForm( const int );
95  CF_INLINE CanonicalForm( const long );
96  CF_INLINE CanonicalForm( const Variable & );
97  CF_INLINE CanonicalForm( const Variable &, int );
98  CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
99 
101 
102  InternalCF* getval() const; // use with caution !!!
103 
104  CanonicalForm deepCopy() const;
105 
106  void mpzval(mpz_t val) const;
107  // predicates
108  CF_NO_INLINE bool isOne() const;
109  CF_NO_INLINE bool isZero() const;
110  inline bool isImm() const { return is_imm( value ); };
111 
112  bool inZ() const;
113  bool inQ() const;
114  bool inFF() const;
115  bool inGF() const;
116  bool inBaseDomain() const;
117  bool inExtension() const;
118  bool inCoeffDomain() const;
119  bool inPolyDomain() const;
120  bool inQuotDomain() const;
121 
122  bool isFFinGF() const;
123  bool isUnivariate() const;
124  bool isHomogeneous() const;
125 
126  // conversion functions
127  long intval() const;
128  CanonicalForm mapinto () const;
129 
130  CanonicalForm lc () const;
131  CanonicalForm Lc () const;
132  CanonicalForm LC () const;
133  CanonicalForm LC ( const Variable & v ) const;
134 
135  int degree () const;
136  int degree ( const Variable & v ) const;
137 
138  CanonicalForm tailcoeff () const;
139  CanonicalForm tailcoeff ( const Variable & v ) const;
140  int taildegree () const;
141 
142  int level () const;
143  Variable mvar () const;
144 
145  CanonicalForm num () const;
146  CanonicalForm den () const;
147 
148  // assignment operators
149  CF_NO_INLINE CanonicalForm& operator = ( const CanonicalForm& );
150  CF_NO_INLINE CanonicalForm& operator = ( const long );
151 
156  CanonicalForm& operator %= ( const CanonicalForm& );
157  CanonicalForm& div ( const CanonicalForm& );
158  CanonicalForm& tryDiv (const CanonicalForm&, const CanonicalForm&, bool& );
159  CanonicalForm& mod ( const CanonicalForm& );
160 
161  // evaluation operators
162  CanonicalForm operator () ( const CanonicalForm & f ) const;
163  CanonicalForm operator () ( const CanonicalForm & f, const Variable & v ) const;
164 
165  CanonicalForm operator [] ( int i ) const;
166 
167  CanonicalForm deriv() const;
168  CanonicalForm deriv( const Variable & x ) const;
169 
170  int sign() const;
171  CanonicalForm sqrt() const;
172  int ilog2() const;
173 
174  // comparison operators
175  friend bool operator == ( const CanonicalForm&, const CanonicalForm& );
176  friend bool operator != ( const CanonicalForm&, const CanonicalForm& );
177  friend bool operator > ( const CanonicalForm&, const CanonicalForm& );
178  friend bool operator < ( const CanonicalForm&, const CanonicalForm& );
179 
180  // arithmetic operators
182 
183  friend void FACTORY_PUBLIC divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
184  friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
185  friend bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );
186 
187  friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
189 
190  // input/output
191 #ifndef NOSTREAMIO
192  void print( OSTREAM&, char * ) const;
193  void print( OSTREAM& ) const;
194  friend OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
196 #endif /* NOSTREAMIO */
197 
198  // obsolete methods
199  CanonicalForm genZero() const;
200  CanonicalForm genOne() const;
201 
202  friend class CFIterator;
203 };
204 
206 operator + ( const CanonicalForm&, const CanonicalForm& );
207 
210 
212 operator * ( const CanonicalForm&, const CanonicalForm& );
213 
216 
219 
221 div ( const CanonicalForm&, const CanonicalForm& );
222 
224 mod ( const CanonicalForm&, const CanonicalForm& );
225 
226 /*ENDPUBLIC*/
227 
228 #ifdef CF_USE_INLINE
229 #ifndef __CYGWIN__
230 #include "cf_inline.cc"
231 #endif
232 #endif
233 
234 /*BEGINPUBLIC*/
235 
236 //{{{ function declarations from canonicalform.cc
237 CanonicalForm blcm ( const CanonicalForm & f, const CanonicalForm & g );
238 
240 
241 CanonicalForm FACTORY_PUBLIC power ( const Variable & v, int n );
242 //}}}
243 
244 //{{{ function declarations from cf_gcd.cc
246 
247 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g );
248 
249 CanonicalForm lcm ( const CanonicalForm&, const CanonicalForm& );
250 
251 CanonicalForm pp ( const CanonicalForm& );
252 
254 
255 CanonicalForm content ( const CanonicalForm&, const Variable& );
256 
258 
259 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x );
260 //}}}
261 
262 //{{{ function declarations from cf_ops.cc
263 CanonicalForm swapvar ( const CanonicalForm &, const Variable &, const Variable & );
264 
266 
267 int getNumVars( const CanonicalForm & f );
268 
270 
271 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
272 
273 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) );
274 
275 int * degrees ( const CanonicalForm & f, int * degs = 0 );
276 
277 int totaldegree ( const CanonicalForm & f );
278 
279 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
280 
281 int size ( const CanonicalForm & f, const Variable & v );
282 
283 int size ( const CanonicalForm & f );
284 
285 int size_maxexp ( const CanonicalForm & f, int& maxexp );
286 
288 
289 bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
290 
291 CanonicalForm leftShift (const CanonicalForm& F, int n);
292 //}}}
293 
294 //{{{ inline functions corresponding to CanonicalForm methods
295 //{{{ docu
296 //
297 // - inline functions corresponding to CanonicalForm methods.
298 //
299 // These function exist for convenience only and because it is
300 // more beautiful to write 'degree( f )' than 'f.degree()'.
301 //
302 //}}}
303 inline CanonicalForm
304 lc ( const CanonicalForm & f ) { return f.lc(); }
305 
306 inline CanonicalForm
307 Lc ( const CanonicalForm & f ) { return f.Lc(); }
308 
309 inline CanonicalForm
310 LC ( const CanonicalForm & f ) { return f.LC(); }
311 
312 inline CanonicalForm
313 LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
314 
315 inline int
316 degree ( const CanonicalForm & f ) { return f.degree(); }
317 
318 inline int
319 degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
320 
321 inline int
322 taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
323 
324 inline CanonicalForm
325 tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
326 
327 inline CanonicalForm
328 tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
329 
330 inline int
331 level ( const CanonicalForm & f ) { return f.level(); }
332 
333 inline Variable
334 mvar ( const CanonicalForm & f ) { return f.mvar(); }
335 
336 inline CanonicalForm
337 num ( const CanonicalForm & f ) { return f.num(); }
338 
339 inline CanonicalForm
340 den ( const CanonicalForm & f ) { return f.den(); }
341 
342 inline int
343 sign ( const CanonicalForm & a ) { return a.sign(); }
344 
345 inline CanonicalForm
346 deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
347 
348 inline CanonicalForm
349 sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
350 
351 inline int
352 ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
353 
354 inline CanonicalForm
355 mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
356 //}}}
357 
358 //{{{ inline functions
359 inline CanonicalForm
360 head ( const CanonicalForm & f )
361 {
362  if ( f.level() > 0 )
363  return power( f.mvar(), f.degree() ) * f.LC();
364  else
365  return f;
366 }
367 
368 inline int
369 headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
370 
371 
372 //}}}
373 
374 //{{{ other function declarations
375 void FACTORY_PUBLIC setCharacteristic( int c ); // -> Fp && Q
376 void setCharacteristic( int c, int n ); // -> PrimePower
377 void setCharacteristic( int c, int n, char name ); // -> GF(q)
378 
380 int getGFDegree();
382 
383 void FACTORY_PUBLIC On( int );
384 void FACTORY_PUBLIC Off( int );
385 bool FACTORY_PUBLIC isOn( int );
386 //}}}
387 
388 //{{{ type definitions
406 //}}}
407 
408 /*ENDPUBLIC*/
409 #endif /* ! INCL_CANONICALFORM_H */
bool operator!=(const Rational &a, const Rational &b)
Definition: GMPrat.cc:318
bool operator<(const Rational &a, const Rational &b)
Definition: GMPrat.cc:288
bool operator==(const Rational &a, const Rational &b)
Definition: GMPrat.cc:312
bool operator>(const Rational &a, const Rational &b)
Definition: GMPrat.cc:300
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
ISTREAM & operator>>(ISTREAM &is, CanonicalForm &cf)
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
bool FACTORY_PUBLIC isOn(int)
switches
Array< int > Intarray
CF_INLINE CanonicalForm operator+(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs...
Definition: cf_inline.cc:503
int headdegree(const CanonicalForm &f)
CanonicalForm mapinto(const CanonicalForm &f)
AFactor< CanonicalForm > CFAFactor
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div(const CanonicalForm &, const CanonicalForm &)
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm lc(const CanonicalForm &f)
int ilog2(const CanonicalForm &a)
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:492
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:697
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
#define OSTREAM
Definition: canonicalform.h:16
ListIterator< Variable > VarlistIterator
void FACTORY_PUBLIC Off(int)
switches
int sign(const CanonicalForm &a)
CanonicalForm FACTORY_PUBLIC gcd(const CanonicalForm &, const CanonicalForm &)
Definition: cf_gcd.cc:685
CanonicalForm tailcoeff(const CanonicalForm &f)
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
ListIterator< CFAFactor > CFAFListIterator
int taildegree(const CanonicalForm &f)
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator%(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
int size_maxexp(const CanonicalForm &f, int &maxexp)
Definition: cf_ops.cc:641
int getGFDegree()
Definition: cf_char.cc:75
#define CF_INLINE
Definition: canonicalform.h:54
Array< CanonicalForm > CFArray
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:65
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator-(const CanonicalForm &, const CanonicalForm &)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
ListIterator< CFFactor > CFFListIterator
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
Matrix< CanonicalForm > CFMatrix
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
List< CFList > ListCFList
ListIterator< CanonicalForm > CFListIterator
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition: cf_ops.cc:440
CanonicalForm num(const CanonicalForm &f)
CanonicalForm den(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm sqrt(const CanonicalForm &a)
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
ListIterator< CFList > ListCFListIterator
List< int > IntList
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/(const CanonicalForm &, const CanonicalForm &)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm head(const CanonicalForm &f)
CanonicalForm getGFGenerator()
Definition: cf_char.cc:81
#define ISTREAM
Definition: canonicalform.h:17
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation
#define CF_NO_INLINE
Definition: canonicalform.h:47
Factor< CanonicalForm > CFFactor
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:660
CF_INLINE CanonicalForm operator*(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:524
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )
Definition: cf_ops.cc:402
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
CanonicalForm lcm(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:763
int level(const CanonicalForm &f)
void FACTORY_PUBLIC On(int)
switches
List< CanonicalForm > CFList
Variable mvar(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
ListIterator< int > IntListIterator
List< CFAFactor > CFAFList
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
List< Variable > Varlist
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4084
g
Definition: cfModGcd.cc:4092
factory switches.
definition of configurable inline ‘CanonicalForm’ methods.
FILE * f
Definition: checklibs.c:9
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
InternalCF * value
Definition: canonicalform.h:88
CF_NO_INLINE bool isZero() const
CF_NO_INLINE ~CanonicalForm()
int sign() const
int CanonicalForm::sign () const
CF_NO_INLINE bool isOne() const
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
bool isImm() const
int ilog2() const
int CanonicalForm::ilog2 () const
virtual class for internal CanonicalForm's
Definition: int_cf.h:47
factory's class for variables
Definition: factory.h:134
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
char name(const Variable &v)
Definition: factory.h:196
#define FACTORY_PUBLIC
Definition: globaldefs.h:25
char N base
Definition: ValueTraits.h:144
campf< Precision > & operator-=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1156
campf< Precision > & operator*=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1164
campf< Precision > & operator/=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1200
campf< Precision > & operator+=(campf< Precision > &lhs, const campf< Precision > &rhs)
Definition: amp.h:1144
ostream & operator<<(ostream &s, const spectrum &spec)
Definition: semic.cc:249
#define M
Definition: sirandom.c:25
operations on variables