factory.h
Go to the documentation of this file.
1 /* factory.h automatically generated by makeheader from factory.template */
2 /* emacs edit mode for this file is -*- C++ -*- */
3 
4 #ifndef INCL_FACTORY_H
5 #define INCL_FACTORY_H
6 
7 /* factory.template is a template to generate `factory.h' */
8 
9 /**
10 *
11 * @file factory.h
12 *
13 * `factory.h' is the user interface to Factory. Created
14 * automatically by `makeheader', it collects all important
15 * declarations from all important Factory header files into one
16 * overall header file leaving out all boring Factory internal
17 * stuff. See `./bin/makeheader' for an explanation of the syntax
18 * of this file.
19 *
20 * Note: In this file the order of "includes" matters (since this
21 * are not real includes)! In general, files at the end depend
22 * on files at the beginning.
23 *
24 **/
25 
26 #include <factory/factoryconf.h>
27 #include <stdint.h>
28 #ifdef HAVE_OMALLOC
29 #include <omalloc/omallocClass.h>
30 #endif
31 
32 #ifndef NOSTREAMIO
33 # ifdef HAVE_IOSTREAM
34 # include <iostream>
35 # define OSTREAM std::ostream
36 # define ISTREAM std::istream
37 # elif defined(HAVE_IOSTREAM_H)
38 # include <iostream.h>
39 # define OSTREAM ostream
40 # define ISTREAM istream
41 # endif
42 #endif /* ! NOSTREAMIO */
43 
44 #include <factory/cf_gmp.h>
45 
51 
52 /* stuff included from ./cf_globals.h */
53 
54 
55 extern const char factoryVersion[];
56 extern const char factoryConfiguration[];
57 
58 
59 /* stuff included from ./cf_primes.h */
60 
61 
62 int cf_getPrime( int i );
63 
64 int cf_getNumPrimes();
65 
66 int cf_getSmallPrime( int i );
67 
69 
70 int cf_getBigPrime( int i );
71 
72 int cf_getNumBigPrimes();
73 
74 
75 /* stuff included from ./cf_defs.h */
76 
77 
78 #define LEVELBASE -1000000
79 #define LEVELTRANS -500000
80 #define LEVELQUOT 1000000
81 #define LEVELEXPR 1000001
82 
83 #define UndefinedDomain 32000
84 #define GaloisFieldDomain 4
85 #define FiniteFieldDomain 3
86 #define RationalDomain 2
87 #define IntegerDomain 1
88 
89 /// set to 1 for computations over Q
90 static const int SW_RATIONAL = 0;
91 /// set to 1 for symmetric representation over F_q
92 static const int SW_SYMMETRIC_FF = 1;
93 /// set to 1 to use EZGCD over Z
94 static const int SW_USE_EZGCD = 2;
95 /// set to 1 to use EZGCD over F_q
96 static const int SW_USE_EZGCD_P = 3;
97 /// set to 1 to sort factors in a factorization
98 static const int SW_USE_NTL_SORT=4;
99 /// set to 1 to use modular gcd over Z
100 static const int SW_USE_CHINREM_GCD=5;
101 /// set to 1 to use Encarnacion GCD over Q(a)
102 static const int SW_USE_QGCD=6;
103 /// set to 1 to use modular GCD over F_q
104 static const int SW_USE_FF_MOD_GCD=7;
105 
106 
107 /* stuff included from ./variable.h */
108 
109 
110 class CanonicalForm;
111 
112 /**
113  * factory's class for variables
114 **/
115 class Variable
116 {
117 private:
118  int _level;
119  Variable( int l, bool flag );
120 public:
121  Variable() : _level(LEVELBASE) {}
122  Variable( int l );
123  Variable( char name );
124  Variable( int l, char name );
125  Variable( const Variable & v ) : _level(v._level) {}
126  ~Variable() {};
128  {
129  _level = v._level;
130  return *this;
131  }
132  int level() const { return _level; }
133  char name() const;
134  static Variable highest() { return Variable( LEVELQUOT-1 ); }
135  Variable next() const { return Variable( _level+1 ); }
136  friend bool operator == ( const Variable & lhs, const Variable & rhs )
137  {
138  return lhs._level == rhs._level;
139  }
140  friend bool operator != ( const Variable & lhs, const Variable & rhs )
141  {
142  return lhs._level != rhs._level;
143  }
144  friend bool operator > ( const Variable & lhs, const Variable & rhs )
145  {
146  return lhs._level > rhs._level;
147  }
148  friend bool operator < ( const Variable & lhs, const Variable & rhs )
149  {
150  return lhs._level < rhs._level;
151  }
152  friend bool operator >= ( const Variable & lhs, const Variable & rhs )
153  {
154  return lhs._level >= rhs._level;
155  }
156  friend bool operator <= ( const Variable & lhs, const Variable & rhs )
157  {
158  return lhs._level <= rhs._level;
159  }
160 #ifndef NOSTREAMIO
161  friend OSTREAM & operator << ( OSTREAM & os, const Variable & v );
162 #endif /* NOSTREAMIO */
163  friend void swap_levels();
164  /** returns a symbolic root of polynomial with name @a name.
165  * Use it to define algebraic variables
166  * @note: algebraic variables have a level < 0
167  **/
168  friend Variable rootOf( const CanonicalForm &, char name );
169 };
170 
171 /** returns a symbolic root of polynomial with name @a name
172  * Use it to define algebraic variables
173  * @note: algebraic variables have a level < 0
174 **/
175 Variable rootOf( const CanonicalForm &, char name = '@' );
176 
177 inline int level( const Variable & v ) { return v.level(); }
178 inline char name( const Variable & v ) { return v.name(); }
179 
180 void setReduce( const Variable & alpha, bool reduce );
181 void setMipo ( const Variable & alpha, const CanonicalForm & mipo);
182 CanonicalForm getMipo( const Variable & alpha, const Variable & x );
183 bool hasMipo( const Variable & alpha );
184 
185 char getDefaultVarName();
186 char getDefaultExtName();
187 
188 void prune (Variable& alpha);
189 void prune1 (const Variable& alpha);
190 int ExtensionLevel();
191 
192 
193 /* stuff included from ./canonicalform.h */
194 
195 
196 #undef CF_INLINE
197 #define CF_INLINE
198 #undef CF_NO_INLINE
199 #define CF_NO_INLINE
200 
201 
202 class InternalCF;
203 
204 inline int is_imm ( const InternalCF * const ptr )
205 {
206  // returns 0 if ptr is not immediate
207  return ( ((int)((intptr_t)ptr)) & 3 );
208 }
209 
210 
211 /**
212  * factory's main class
213  *
214  * a CanonicalForm can represent a polynomial over or a constant in F_p,
215  * F_p(alpha), GF (F_p[t]/(Conway polynomial)), Z, or Q
216  *
217  * @sa int_poly.h, variable.h, ffops.h, gfops.h, imm.h, int_int.h, int_rat.h
218 **/
219 class CanonicalForm
220 #ifdef HAVE_OMALLOC
221  : public omallocClass
222 #endif
223 {
224 private:
225  InternalCF *value;
226 public:
227  // constructors, destructors, selectors
229  CF_INLINE CanonicalForm( const CanonicalForm& );
230  CF_INLINE CanonicalForm( InternalCF* );
231  CF_INLINE CanonicalForm( const int );
232  CF_INLINE CanonicalForm( const long );
233  CF_INLINE CanonicalForm( const Variable & );
234  CF_INLINE CanonicalForm( const Variable &, int );
235  CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
236 
237  CF_NO_INLINE ~CanonicalForm();
238 
239  InternalCF* getval() const; // use with caution !!!
240 
241  CanonicalForm deepCopy() const;
242 
243  void mpzval(mpz_t val) const;
244  // predicates
245  CF_NO_INLINE bool isOne() const;
246  CF_NO_INLINE bool isZero() const;
247  inline bool isImm() const { return is_imm( value ); };
248 
249  bool inZ() const;
250  bool inQ() const;
251  bool inFF() const;
252  bool inGF() const;
253  bool inBaseDomain() const;
254  bool inExtension() const;
255  bool inCoeffDomain() const;
256  bool inPolyDomain() const;
257  bool inQuotDomain() const;
258 
259  bool isFFinGF() const;
260  bool isUnivariate() const;
261  bool isHomogeneous() const;
262 
263  // conversion functions
264  long intval() const;
265  CanonicalForm mapinto () const;
266 
267  CanonicalForm lc () const;
268  CanonicalForm Lc () const;
269  CanonicalForm LC () const;
270  CanonicalForm LC ( const Variable & v ) const;
271 
272  int degree () const;
273  int degree ( const Variable & v ) const;
274 
275  CanonicalForm tailcoeff () const;
276  CanonicalForm tailcoeff ( const Variable & v ) const;
277  int taildegree () const;
278 
279  int level () const;
280  Variable mvar () const;
281 
282  CanonicalForm num () const;
283  CanonicalForm den () const;
284 
285  // assignment operators
286  CF_NO_INLINE CanonicalForm& operator = ( const CanonicalForm& );
287  CF_NO_INLINE CanonicalForm& operator = ( const long );
288 
289  CanonicalForm& operator += ( const CanonicalForm& );
290  CanonicalForm& operator -= ( const CanonicalForm& );
291  CanonicalForm& operator *= ( const CanonicalForm& );
292  CanonicalForm& operator /= ( const CanonicalForm& );
293  CanonicalForm& operator %= ( const CanonicalForm& );
294  CanonicalForm& div ( const CanonicalForm& );
295  CanonicalForm& tryDiv (const CanonicalForm&, const CanonicalForm&, bool& );
296  CanonicalForm& mod ( const CanonicalForm& );
297 
298  // evaluation operators
299  CanonicalForm operator () ( const CanonicalForm & f ) const;
300  CanonicalForm operator () ( const CanonicalForm & f, const Variable & v ) const;
301 
302  CanonicalForm operator [] ( int i ) const;
303 
304  CanonicalForm deriv() const;
305  CanonicalForm deriv( const Variable & x ) const;
306 
307  int sign() const;
308  CanonicalForm sqrt() const;
309  int ilog2() const;
310 
311  // comparison operators
312  friend bool operator == ( const CanonicalForm&, const CanonicalForm& );
313  friend bool operator != ( const CanonicalForm&, const CanonicalForm& );
314  friend bool operator > ( const CanonicalForm&, const CanonicalForm& );
315  friend bool operator < ( const CanonicalForm&, const CanonicalForm& );
316 
317  // arithmetic operators
318  friend CF_NO_INLINE CanonicalForm operator - ( const CanonicalForm& );
319 
320  friend void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
321  friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
322  friend bool tryDivremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm&, const CanonicalForm&, bool& );
323 
324  friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
325  friend CanonicalForm bextgcd ( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm & );
326 
327  // input/output
328 #ifndef NOSTREAMIO
329  void print( OSTREAM&, char * ) const;
330  void print( OSTREAM& ) const;
331  friend OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
332  friend ISTREAM& operator >> ( ISTREAM&, CanonicalForm& );
333 #endif /* NOSTREAMIO */
334 
335  // obsolete methods
336  CanonicalForm genZero() const;
337  CanonicalForm genOne() const;
338 
339  friend class CFIterator;
340 };
341 
343 operator + ( const CanonicalForm&, const CanonicalForm& );
344 
346 operator - ( const CanonicalForm&, const CanonicalForm& );
347 
349 operator * ( const CanonicalForm&, const CanonicalForm& );
350 
352 operator / ( const CanonicalForm&, const CanonicalForm& );
353 
355 operator % ( const CanonicalForm&, const CanonicalForm& );
356 
358 div ( const CanonicalForm&, const CanonicalForm& );
359 
361 mod ( const CanonicalForm&, const CanonicalForm& );
362 
363 
364 //{{{ function declarations from canonicalform.cc
365 CanonicalForm blcm ( const CanonicalForm & f, const CanonicalForm & g );
366 
367 CanonicalForm power ( const CanonicalForm & f, int n );
368 
369 CanonicalForm power ( const Variable & v, int n );
370 //}}}
371 
372 //{{{ function declarations from cf_gcd.cc
373 CanonicalForm gcd ( const CanonicalForm&, const CanonicalForm& );
374 
375 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g );
376 
377 CanonicalForm lcm ( const CanonicalForm&, const CanonicalForm& );
378 
379 CanonicalForm pp ( const CanonicalForm& );
380 
382 
383 CanonicalForm content ( const CanonicalForm&, const Variable& );
384 
385 CanonicalForm icontent ( const CanonicalForm & f );
386 
387 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x );
388 //}}}
389 
390 //{{{ function declarations from cf_ops.cc
391 CanonicalForm swapvar ( const CanonicalForm &, const Variable &, const Variable & );
392 
393 CanonicalForm replacevar ( const CanonicalForm &, const Variable &, const Variable & );
394 
395 int getNumVars( const CanonicalForm & f );
396 
397 CanonicalForm getVars( const CanonicalForm & f );
398 
399 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) );
400 
401 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) );
402 
403 int * degrees ( const CanonicalForm & f, int * degs = 0 );
404 
405 int totaldegree ( const CanonicalForm & f );
406 
407 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 );
408 
409 int size ( const CanonicalForm & f, const Variable & v );
410 
411 int size ( const CanonicalForm & f );
412 
413 CanonicalForm reduce ( const CanonicalForm& f, const CanonicalForm & M);
414 
415 bool hasFirstAlgVar( const CanonicalForm & f, Variable & a);
416 
417 CanonicalForm leftShift (const CanonicalForm& F, int n);
418 //}}}
419 
420 //{{{ inline functions corresponding to CanonicalForm methods
421 //{{{ docu
422 //
423 // - inline functions corresponding to CanonicalForm methods.
424 //
425 // These function exist for convenience only and because it is
426 // more beautiful to write 'degree( f )' than 'f.degree()'.
427 //
428 //}}}
429 inline CanonicalForm
430 lc ( const CanonicalForm & f ) { return f.lc(); }
431 
432 inline CanonicalForm
433 Lc ( const CanonicalForm & f ) { return f.Lc(); }
434 
435 inline CanonicalForm
436 LC ( const CanonicalForm & f ) { return f.LC(); }
437 
438 inline CanonicalForm
439 LC ( const CanonicalForm & f, const Variable & v ) { return f.LC( v ); }
440 
441 inline int
442 degree ( const CanonicalForm & f ) { return f.degree(); }
443 
444 inline int
445 degree ( const CanonicalForm & f, const Variable & v ) { return f.degree( v ); }
446 
447 inline int
448 taildegree ( const CanonicalForm & f ) { return f.taildegree(); }
449 
450 inline CanonicalForm
451 tailcoeff ( const CanonicalForm & f ) { return f.tailcoeff(); }
452 
453 inline CanonicalForm
454 tailcoeff (const CanonicalForm& f, const Variable& v) { return f.tailcoeff(v); }
455 
456 inline int
457 level ( const CanonicalForm & f ) { return f.level(); }
458 
459 inline Variable
460 mvar ( const CanonicalForm & f ) { return f.mvar(); }
461 
462 inline CanonicalForm
463 num ( const CanonicalForm & f ) { return f.num(); }
464 
465 inline CanonicalForm
466 den ( const CanonicalForm & f ) { return f.den(); }
467 
468 inline int
469 sign ( const CanonicalForm & a ) { return a.sign(); }
470 
471 inline CanonicalForm
472 deriv ( const CanonicalForm & f, const Variable & x ) { return f.deriv( x ); }
473 
474 inline CanonicalForm
475 sqrt ( const CanonicalForm & a ) { return a.sqrt(); }
476 
477 inline int
478 ilog2 ( const CanonicalForm & a ) { return a.ilog2(); }
479 
480 inline CanonicalForm
481 mapinto ( const CanonicalForm & f ) { return f.mapinto(); }
482 //}}}
483 
484 //{{{ inline functions
485 inline CanonicalForm
486 head ( const CanonicalForm & f )
487 {
488  if ( f.level() > 0 )
489  return power( f.mvar(), f.degree() ) * f.LC();
490  else
491  return f;
492 }
493 
494 inline int
495 headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
496 
497 
498 //}}}
499 
500 //{{{ other function declarations
501 void setCharacteristic( int c ); // -> Fp && Q
502 void setCharacteristic( int c, int n ); // -> PrimePower
503 void setCharacteristic( int c, int n, char name ); // -> GF(q)
504 
505 int getCharacteristic();
506 int getGFDegree();
508 
509 void On( int );
510 void Off( int );
511 bool isOn( int );
512 //}}}
513 
514 //{{{ type definitions
532 //}}}
533 
534 
535 /* stuff included from ./cf_algorithm.h */
536 
537 
538 //{{{ function declarations from cf_algorithm.cc
539 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
540 
541 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
542 
543 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
544 
546 
547 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
548 
549 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot );
550 
551 bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail );
552 
553 CanonicalForm maxNorm ( const CanonicalForm & f );
554 
556 //}}}
557 
558 //{{{ function declarations from cf_chinese.cc
559 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew );
560 
561 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
562 
564 
565 
566 CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
567 //}}}
568 
569 //{{{ function declarations from cf_factor.cc
570 extern int singular_homog_flag;
571 
572 bool isPurePoly(const CanonicalForm & f);
573 
574 bool isPurePoly_m(const CanonicalForm & f);
575 
576 CFFList factorize ( const CanonicalForm & f, bool issqrfree = false );
577 
578 CFFList factorize ( const CanonicalForm & f, const Variable & alpha );
579 
580 CFFList sqrFree ( const CanonicalForm & f, bool sort= false );
581 
582 CanonicalForm homogenize( const CanonicalForm & f, const Variable & x);
583 CanonicalForm homogenize( const CanonicalForm & f, const Variable & x,
584  const Variable & v1, const Variable & v2);
586 CFList get_Terms( const CanonicalForm & f );
587 void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
588 
589 
590 //}}}
591 
592 //{{{ function declarations from cf_linsys.cc
593 bool linearSystemSolve ( CFMatrix & M );
594 
595 CanonicalForm determinant ( const CFMatrix & M, int n );
596 //}}}
597 
598 //{{{ function declarations from cf_resultant.cc
599 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
600 
601 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x );
602 //}}}
603 
604 /** inline CanonicalForm abs ( const CanonicalForm & f )
605  *
606  * abs() - return absolute value of `f'.
607  *
608  * The absolute value is defined in terms of the function
609  * `sign()'. If it reports negative sign for `f' than -`f' is
610  * returned, otherwise `f'.
611  *
612  * This behaviour is most useful for integers and rationals. But
613  * it may be used to sign-normalize the leading coefficient of
614  * arbitrary polynomials, too.
615  *
616  * Type info:
617  * ----------
618  * f: CurrentPP
619  *
620 **/
621 inline CanonicalForm
622 abs ( const CanonicalForm & f )
623 {
624  // it is not only more general to use `sign()' instead of a
625  // direct comparison `f < 0', it is faster, too
626  if ( sign( f ) < 0 )
627  return -f;
628  else
629  return f;
630 }
631 //}}}
632 
633 
634 /* stuff included from ./cf_eval.h */
635 
636 
637 /**
638  * class to evaluate a polynomial at points
639 **/
640 class Evaluation
641 {
642 protected:
643  CFArray values;
644 public:
645  Evaluation() : values() {}
646  Evaluation( int min0, int max0 ) : values( min0, max0 ) {}
647  Evaluation( const Evaluation & e ) : values( e.values ) {}
648  virtual ~Evaluation() {}
649  Evaluation& operator= ( const Evaluation & e );
650  int min() const { return values.min(); }
651  int max() const { return values.max(); }
652  CanonicalForm operator[] ( int i ) const { return values[i]; }
653  CanonicalForm operator[] ( const Variable & v ) const { return operator[](v.level()); }
654  CanonicalForm operator() ( const CanonicalForm& f ) const;
655  CanonicalForm operator() ( const CanonicalForm & f, int i, int j ) const;
656  void setValue (int i, const CanonicalForm& f);
657  virtual void nextpoint();
658 #ifndef NOSTREAMIO
659  friend OSTREAM& operator<< ( OSTREAM& s, const Evaluation &e );
660 #endif /* NOSTREAMIO */
661 };
662 
663 
664 /* stuff included from ./cf_generator.h */
665 
666 
667 /**
668  * virtual class for generators
669 **/
670 class CFGenerator
671 {
672 public:
674  virtual ~CFGenerator() {}
675  virtual bool hasItems() const { return false; }
676  virtual void reset() {};
677  virtual CanonicalForm item() const { return 0; }
678  virtual void next() {};
679  virtual CFGenerator * clone() const { return new CFGenerator();}
680 };
681 
682 /**
683  * generate integers starting from 0
684 **/
685 class IntGenerator : public CFGenerator
686 {
687 private:
688  int current;
689 public:
690  IntGenerator() : current(0) {}
692  bool hasItems() const;
693  void reset() { current = 0; }
694  CanonicalForm item() const;
695  void next();
696  void operator++ () { next(); }
697  void operator++ ( int ) { next(); }
698  CFGenerator * clone() const;
699 };
700 
701 /**
702  * generate all elements in F_p starting from 0
703 **/
704 class FFGenerator : public CFGenerator
705 {
706 private:
707  int current;
708 public:
709  FFGenerator() : current(0) {}
711  bool hasItems() const;
712  void reset() { current = 0; }
713  CanonicalForm item() const;
714  void next();
715  void operator++ () { next(); }
716  void operator++ ( int ) { next(); }
717  CFGenerator * clone() const;
718 };
719 
720 /**
721  * generate all elements in GF starting from 0
722 **/
723 class GFGenerator : public CFGenerator
724 {
725 private:
726  int current;
727 public:
728  GFGenerator();
730  bool hasItems() const;
731  void reset();
732  CanonicalForm item() const;
733  void next();
734  void operator++ () { next(); }
735  void operator++ ( int ) { next(); }
736  CFGenerator * clone() const;
737 };
738 
739 /**
740  * generate all elements in F_p(alpha) starting from 0
741 **/
742 class AlgExtGenerator: public CFGenerator
743 {
744 private:
745  Variable algext;
746  FFGenerator **gensf;
747  GFGenerator **gensg;
748  int n;
749  bool nomoreitems;
750  AlgExtGenerator();
751  AlgExtGenerator( const AlgExtGenerator & );
753 public:
754  AlgExtGenerator( const Variable & a );
755  ~AlgExtGenerator();
756 
757  bool hasItems() const { return ! nomoreitems; }
758  void reset();
759  CanonicalForm item() const;
760  void next();
761  void operator++ () { next(); }
762  void operator++ ( int ) { next(); }
763  CFGenerator * clone() const;
764 };
765 
766 class CFGenFactory
767 {
768 public:
769  static CFGenerator* generate();
770 };
771 
772 
773 /* stuff included from ./cf_iter.h */
774 
775 
776 #undef CF_INLINE
777 #define CF_INLINE
778 #undef CF_NO_INLINE
779 #define CF_NO_INLINE
780 
781 
782 class term;
783 typedef term * termList;
784 
785 /**
786  * class to iterate through CanonicalForm's
787  *
788  * @note a (multivariate) polynomial is viewed as a univariate poly in its main
789  * variable
790 **/
791 class CFIterator {
792 private:
793  CanonicalForm data;
794  termList cursor;
795  bool ispoly, hasterms;
796 public:
797  CFIterator ();
798  CFIterator ( const CFIterator& );
799  CFIterator ( const CanonicalForm& );
800  CFIterator ( const CanonicalForm&, const Variable& );
801 
802  ~CFIterator ();
803 
804  CFIterator& operator= ( const CFIterator& );
806 
807  CF_NO_INLINE CFIterator& operator++ ();
808  CF_NO_INLINE CFIterator& operator++ ( int );
809  CF_NO_INLINE int hasTerms () const; ///< check if iterator has reached
810  ///< the end of CanonicalForm
811  CF_NO_INLINE CanonicalForm coeff () const;///< get the current coefficient
812  CF_NO_INLINE int exp () const; ///< get the current exponent
813 };
814 
815 
816 /* stuff included from ./cf_random.h */
817 
818 
819 /**
820  * virtual class for random element generation
821 **/
822 class CFRandom {
823 public:
824  virtual ~CFRandom() {}
825  virtual CanonicalForm generate() const { return 0; }
826  virtual CFRandom * clone() const { return new CFRandom(); }
827 };
828 
829 /**
830  * generate random elements in GF
831 **/
832 class GFRandom : public CFRandom
833 {
834 public:
835  GFRandom() {};
837  CanonicalForm generate() const;
838  CFRandom * clone() const;
839 };
840 
841 /**
842  * generate random elements in F_p
843 **/
844 class FFRandom : public CFRandom
845 {
846 public:
847  FFRandom() {}
849  CanonicalForm generate() const;
850  CFRandom * clone() const;
851 };
852 
853 /**
854  * generate random integers
855 **/
856 class IntRandom : public CFRandom
857 {
858 private:
859  int max;
860 public:
861  IntRandom();
862  IntRandom( int m );
863  ~IntRandom();
864  CanonicalForm generate() const;
865  CFRandom * clone() const;
866 };
867 
868 /**
869  * generate random elements in F_p(alpha)
870 **/
871 class AlgExtRandomF : public CFRandom {
872 private:
873  Variable algext;
874  CFRandom * gen;
875  int n;
876  AlgExtRandomF();
877  AlgExtRandomF( const Variable & v, CFRandom * g, int nn );
879 public:
880  AlgExtRandomF( const AlgExtRandomF & );
881  AlgExtRandomF( const Variable & v );
882  AlgExtRandomF( const Variable & v1, const Variable & v2 );
883  ~AlgExtRandomF();
884  CanonicalForm generate() const;
885  CFRandom * clone() const;
886 };
887 
888 class CFRandomFactory {
889 public:
890  static CFRandom * generate();
891 };
892 
893 /// random integers with abs less than n
894 int factoryrandom( int n );
895 
896 /// random seed initializer
897 void factoryseed( int s );
898 
899 
900 /* stuff included from ./fac_util.h */
901 
902 
903 /**
904  * class to do operations mod p^k for int's p and k
905 **/
906 class modpk
907 {
908 private:
909  CanonicalForm pk;
910  CanonicalForm pkhalf;
911  int p;
912  int k;
913 public:
914  modpk();
915  modpk( int q, int l );
916  modpk( const modpk & m );
917  modpk& operator= ( const modpk& m );
918  ~modpk() {}
919  int getp() const { return p; }
920  int getk() const { return k; }
921  CanonicalForm inverse( const CanonicalForm & f, bool symmetric = true ) const;
922  CanonicalForm getpk() const { return pk; }
923  CanonicalForm operator() ( const CanonicalForm & f, bool symmetric = true ) const;
924 };
925 
926 
927 CanonicalForm replaceLc( const CanonicalForm & f, const CanonicalForm & c );
928 
929 
930 /* stuff included from ./cf_map.h */
931 
932 
933 /** class MapPair
934  *
935  * class MapPair - stores one mapping pair (Variable -> CanonicalForm).
936  *
937  * This class is only used to store such pairs. It has no
938  * methods to transform a CanonicalForm as the class CFMap has.
939  *
940  * V, S: the pair (V -> S)
941  *
942 **/
943 /** inline method
944  *
945  * Variable var () const
946  * CanonicalForm subst () const
947  *
948  * var(), subst() - selectors, return V and P, resp.
949  *
950 **/
951 class MapPair
952 {
953 private:
954  Variable V;
955  CanonicalForm S;
956 public:
957  MapPair ( const Variable & v, const CanonicalForm & s ) : V(v), S(s) {}
958  MapPair () : V(), S(1) {}
959  MapPair ( const MapPair & p ) : V(p.V), S(p.S) {}
960  ~MapPair () {}
961  MapPair & operator = ( const MapPair & p );
962  Variable var () const { return V; }
963  CanonicalForm subst () const { return S; }
964 #ifndef NOSTREAMIO
965  void print( OSTREAM&) const;
966  friend OSTREAM & operator << ( OSTREAM & s, const MapPair & p );
967 #endif /* NOSTREAMIO */
968 };
969 
972 
973 /** class CFMap
974  *
975  * class CFMap - class to map canonical forms.
976  *
977  * Use an object of class CFMap to insert 'values' into canonical
978  * form. Such a mapping is defined by a list of MapPairs (V -> S)
979  * describing which canonical form S to insert for variable V.
980  * Hereby, the substituted canonical forms are not subject to
981  * further substitutions.
982  *
983  * P: list of MapPairs, sorted by level in descending order
984  *
985 **/
986 class CFMap
987 {
988 private:
989  MPList P;
990 public:
991  CFMap () {}
992  CFMap ( const CanonicalForm & s ) : P( MapPair( Variable(), s ) ) {}
993  CFMap ( const Variable & v ) : P( MapPair( v, 1 ) ) {}
994  CFMap ( const Variable & v, const CanonicalForm & s ) : P( MapPair( v, s ) ) {}
995  ~CFMap () {}
996  CFMap ( const CFList & L );
997  CFMap ( const CFMap & m ) : P( m.P ) {}
998  CFMap & operator = ( const CFMap & m );
999  void newpair ( const Variable & v, const CanonicalForm & s );
1000  CanonicalForm operator () ( const CanonicalForm & f ) const;
1001 #ifndef NOSTREAMIO
1002  friend OSTREAM & operator << ( OSTREAM & s, const CFMap & m );
1003 #endif /* NOSTREAMIO */
1004 };
1005 
1006 CanonicalForm compress ( const CanonicalForm & f, CFMap & m );
1007 void compress ( const CFArray & a, CFMap & M, CFMap & N );
1008 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N );
1009 
1010 
1011 /* stuff included from ./cf_reval.h */
1012 
1013 
1014 /**
1015  * class to generate random evaluation points
1016  *
1017  * @sa cf_eval.h
1018 **/
1019 class REvaluation : public Evaluation
1020 {
1021 protected: // neeeded in FFREvaluation
1022  CFRandom * gen;
1023 public:
1024  REvaluation() : Evaluation(), gen(0) {}
1025  REvaluation( int min0, int max0, const CFRandom & sample ) : Evaluation( min0, max0 ), gen( sample.clone() ) {}
1026  REvaluation( const REvaluation & e );
1027  ~REvaluation();
1028  REvaluation& operator= ( const REvaluation & e );
1029  void nextpoint();
1030  void nextpoint(int n);
1031 };
1032 
1033 
1034 /* stuff included from ./fac_sqrfree.h */
1035 
1036 
1037 /* stuff included from ./gfops.h */
1038 
1039 
1040 long gf_gf2ff ( long a );
1041 int gf_gf2ff ( int a );
1042 
1043 bool gf_isff ( long a );
1044 bool gf_isff ( int a );
1045 
1046 
1047 /* stuff included from ./cf_hnf.h */
1048 
1049 
1050 #ifdef HAVE_NTL
1051 
1052 /**
1053  *
1054  * The input matrix A is square matrix of integers
1055  * output: the Hermite Normal Form of A; that is,
1056  * the unique m x m matrix whose rows span L, such that
1057  *
1058  * - lower triangular,
1059  * - the diagonal entries are positive,
1060  * - any entry below the diagonal is a non-negative number
1061  * strictly less than the diagonal entry in its column.
1062  *
1063  * @note: uses NTL
1064  *
1065 **/
1066 
1068 
1069 /**
1070  * performs LLL reduction.
1071  *
1072  * B is an m x n matrix, viewed as m rows of n-vectors. m may be less
1073  * than, equal to, or greater than n, and the rows need not be
1074  * linearly independent. B is transformed into an LLL-reduced basis,
1075  * and the return value is the rank r of B. The first m-r rows of B
1076  * are zero.
1077  *
1078  * More specifically, elementary row transformations are performed on
1079  * B so that the non-zero rows of new-B form an LLL-reduced basis
1080  * for the lattice spanned by the rows of old-B.
1081  * The default reduction parameter is delta=3/4, which means
1082  * that the squared length of the first non-zero basis vector
1083  * is no more than 2^{r-1} times that of the shortest vector in
1084  * the lattice.
1085  *
1086  * @note: uses NTL
1087 **/
1088 
1089 CFMatrix* cf_LLL(CFMatrix& A);
1090 
1091 #endif
1092 
1093 
1094 /* stuff included from ./singext.h */
1095 
1096 
1097 void gmp_numerator ( const CanonicalForm & f, mpz_ptr result );
1098 
1099 void gmp_denominator ( const CanonicalForm & f, mpz_ptr result );
1100 
1101 int gf_value (const CanonicalForm & f );
1102 
1103 CanonicalForm make_cf ( const mpz_ptr n );
1104 
1105 CanonicalForm make_cf ( const mpz_ptr n, const mpz_ptr d, bool normalize );
1106 
1107 CanonicalForm make_cf_from_gf ( const int z );
1108 
1109 
1110 /* stuff included from ./cf_util.h */
1111 
1112 int igcd (int a, int b);
1113 int ipower ( int b, int n );
1114 void factoryError_intern(const char *s);
1115 extern void (*factoryError)(const char *s);
1116 
1117 /* stuff included from ./facIrredTest.h */
1118 
1119 
1120 /// given some error probIrredTest detects irreducibility or reducibility of F
1121 /// with confidence level 1-error
1122 ///
1123 /// @return probIrredTest returns 1 for irreducibility, -1 for reducibility
1124 /// or 0 if the test is not applicable
1125 int probIrredTest (const CanonicalForm& F, ///< [in] some poly over Z/p
1126  double error ///< [in] 0 < error < 1
1127  );
1128 
1129 
1130 /* stuff included from ./facAbsFact.h */
1131 
1132 #ifdef HAVE_NTL
1133 /// absolute factorization of a multivariate poly over Q
1134 ///
1135 /// @return absFactorize returns a list whose entries contain three
1136 /// entities:
1137 /// an absolute irreducible factor, an irreducible univariate polynomial
1138 /// that defines the minimal field extension over which the irreducible
1139 /// factor is defined (note: in case the factor is already defined over
1140 /// Q[t]/(t), 1 is returned), and the multiplicity of the
1141 /// absolute irreducible factor
1142 CFAFList absFactorize (const CanonicalForm& G ///<[in] poly over Q
1143  );
1144 #endif
1145 
1146 /* stuff included from ./cfModResultant.h */
1147 
1148 /// modular resultant algorihtm over Z
1149 ///
1150 /// @return @a resultantZ returns the resultant of A and B wrt. x
1152 resultantZ (const CanonicalForm& A, ///<[in] some poly
1153  const CanonicalForm& B, ///<[in] some poly
1154  const Variable& x, ///<[in] some polynomial variable
1155  bool prob= true ///<[in] if true use probabilistic algorithm
1156  );
1157 
1158 /* stuff included from ./facAlgFunc.h */
1159 
1160 
1161 /// factorize a polynomial @a f that is irreducible over the ground field modulo
1162 /// an extension given by an irreducible characteristic set @a as, @a f is
1163 /// assumed to be integral, i.e. \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each
1164 /// element of @a as is assumed to be integral as well. \f$ K \f$ must be either
1165 /// \f$ F_p \f$ or \f$ Q \f$.
1166 ///
1167 /// @return the returned factors are not necessarily monic but only primitive
1168 /// and the product of the factors equals @a f up to a unit.
1169 CFFList facAlgFunc2 (const CanonicalForm & f,///<[in] univariate poly
1170  const CFList & as ///<[in] irreducible characteristic
1171  ///< set
1172  );
1173 
1174 /// factorize a polynomial @a f modulo an extension given by an irreducible
1175 /// characteristic set as, @a f is assumed to be integral, i.e.
1176 /// \f$ f\in K[x_1,\ldots,x_n]/(as) \f$, and each element of @a as is assumed to
1177 /// be integral as well. \f$ K \f$ must be either \f$ F_p \f$ or \f$ Q \f$.
1178 ///
1179 /// @return the returned factors are not necessarily monic but only primitive
1180 /// and the product of the factors equals @a f up to a unit.
1181 CFFList facAlgFunc (const CanonicalForm & f, ///<[in] univariate poly
1182  const CFList & as ///<[in] irreducible characteristic
1183  ///< set
1184  );
1185 
1186 /* stuff included from ./cfCharSetsUtil.h */
1187 
1188 /**
1189  * class to store factors that get removed during char set computation
1190 **/
1191 class StoreFactors
1192 {
1193  public:
1194  CFList FS1; ///< factors that were removed
1195  CFList FS2; ///< candidate factors that might get removed
1196  inline StoreFactors& operator= (const StoreFactors& value)
1197  {
1198  if ( this != &value )
1199  {
1200  FS1 = value.FS1;
1201  FS2 = value.FS2;
1202  }
1203  return *this;
1204  }
1205 };
1206 
1208 Prem (const CanonicalForm& F, const CanonicalForm& G);
1209 
1210 
1211 /* stuff included from ./cfCharSets.h */
1212 
1213 
1214 /// basic set in the sense of Wang a.k.a. minimal ascending set in the sense of
1215 /// Greuel/Pfister
1216 CFList
1217 basicSet (const CFList& PS);
1218 
1219 /// characteristic set
1220 CFList
1221 charSet (const CFList& PS);
1222 
1223 /// modified medial set
1224 CFList
1225 modCharSet (const CFList& PS, StoreFactors& StoredFactors,
1226  bool removeContents= true);
1227 
1228 CFList
1229 modCharSet (const CFList& PS, bool removeContents);
1230 
1231 CFList
1232 charSetViaCharSetN (const CFList& PS);
1233 
1234 CFList
1235 charSetN (const CFList &PS);
1236 
1237 /// modified characteristic set, i.e. a characteristic set with certain
1238 /// factors removed
1239 CFList
1240 charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors,
1241  bool removeContents= true);
1242 
1243 /// modified characteristic set, i.e. a characteristic set with certain
1244 /// factors removed
1245 CFList
1246 charSetViaModCharSet (const CFList& PS, bool removeContents= true);
1247 
1248 /// characteristic series
1249 ListCFList
1250 charSeries (const CFList& L);
1251 
1252 /// irreducible characteristic series
1253 ListCFList
1254 irrCharSeries (const CFList & PS);
1255 
1256 // the next three give you a heuristically optimal reorderd list of the
1257 // variables. For internal and external (e.g. Singular/Macaulay2) library use.
1258 // This is really experimental!
1259 // See the comments in reorder.cc.
1260 //
1261 // this gives you a heuristically optimal ordering for the ring variables
1262 // if you use the irreducible characteristic series.
1263 Varlist neworder (const CFList & PolyList);
1264 
1265 // the same as neworder(...) only returning a list of CanonicalForm 's
1266 // (i.e. the variables as CanonicalForms)
1267 CFList newordercf (const CFList & PolyList);
1268 
1269 // the same as neworder(...) only returning a list of int 's (i.e. the levels)
1270 IntList neworderint (const CFList & PolyList);
1271 
1272 // for library internal use only:
1273 // next function reorders the variables in PS:
1274 // a code segment to use:
1275 // ...
1276 // #include <tmpl_inst.h> // for typedef's
1277 // CFList PS= <setup-your-list-of-CanonicalForms>;
1278 // Varlist betterorder= neworder(PS);
1279 // PS= reorder(betterorder,PS); // reorder variables in PS from oldorder
1280 // to betterorder
1281 // ListCFList Q= IrrCharSeries( PS );
1282 // Q= reorder(betterorder,Q); // revert ordering to oldorder
1283 //
1284 CFList reorder (const Varlist & betterorder, const CFList & PS);
1285 CFFList reorder (const Varlist & betterorder, const CFFList & PS);
1286 ListCFList reorder (const Varlist & betterorder, const ListCFList & Q);
1287 
1288 /* stuff included from ./cfUnivarGcd.h */
1289 
1291 extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b );
1292 
1293 
1294 #endif /* ! INCL_FACTORY_H */
int ilog2() const
int CanonicalForm::ilog2 () const
class MapPair
Definition: cf_map.h:49
~MapPair()
Definition: factory.h:960
List< int > IntList
Definition: factory.h:527
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
const char factoryVersion[]
IntList neworderint(const CFList &PolyList)
Definition: cfCharSets.cc:88
CFGenerator()
Definition: factory.h:673
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
int gf_value(const CanonicalForm &f)
Definition: singext.cc:60
ListIterator< CFList > ListCFListIterator
Definition: factory.h:526
const CanonicalForm int s
Definition: facAbsFact.cc:55
friend bool operator==(const Variable &lhs, const Variable &rhs)
Definition: factory.h:136
Array< int > Intarray
Definition: factory.h:531
generate random elements in GF
Definition: cf_random.h:31
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:93
MapPair()
Definition: factory.h:958
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
MapPair(const MapPair &p)
Definition: factory.h:959
const poly a
Definition: syzextra.cc:212
CanonicalForm Lc() const
ListIterator< MapPair > MPListIterator
Definition: factory.h:971
CanonicalForm lc(const CanonicalForm &f)
Definition: factory.h:430
friend Variable rootOf(const CanonicalForm &, char name)
returns a symbolic root of polynomial with name name.
Definition: variable.cc:162
CFList FS1
factors that were removed
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial f that is irreducible over the ground field modulo an extension given by an ir...
Definition: facAlgFunc.cc:905
int is_imm(const InternalCF *const ptr)
Definition: factory.h:204
~CFMap()
Definition: factory.h:995
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
CanonicalForm operator[](const Variable &v) const
Definition: factory.h:653
void prune1(const Variable &alpha)
Definition: variable.cc:288
friend bool operator<(const Variable &lhs, const Variable &rhs)
Definition: factory.h:148
CFMap(const CanonicalForm &s)
Definition: factory.h:992
const char factoryConfiguration[]
virtual ~CFGenerator()
Definition: factory.h:674
FFRandom()
Definition: factory.h:847
Definition: int_poly.h:33
Array< CanonicalForm > CFArray
Definition: factory.h:523
ListIterator< int > IntListIterator
Definition: factory.h:528
int degree(const CanonicalForm &f)
Definition: factory.h:442
return P p
Definition: myNF.cc:203
friend bool operator<=(const Variable &lhs, const Variable &rhs)
Definition: factory.h:156
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
ListCFList irrCharSeries(const CFList &PS)
irreducible characteristic series
Definition: cfCharSets.cc:568
virtual ~CFRandom()
Definition: factory.h:824
factory&#39;s class for variables
Definition: factory.h:115
class to store factors that get removed during char set computation
#define CF_INLINE
Definition: factory.h:777
virtual class for generators
Definition: cf_generator.h:21
~Variable()
Definition: factory.h:126
CFMatrix * cf_LLL(CFMatrix &A)
performs LLL reduction.
Definition: cf_hnf.cc:48
bool isImm() const
Definition: factory.h:247
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial f modulo an extension given by an irreducible characteristic set as...
Definition: facAlgFunc.cc:1043
Variable var() const
Definition: factory.h:962
void setMipo(const Variable &alpha, const CanonicalForm &mipo)
Definition: variable.cc:219
friend OSTREAM & operator<<(OSTREAM &os, const Variable &v)
Definition: variable.cc:133
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CanonicalForm lcm(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:343
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: factory.h:96
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
friend bool operator!=(const Variable &lhs, const Variable &rhs)
Definition: factory.h:140
#define LEVELBASE
Definition: factory.h:78
int taildegree(const CanonicalForm &f)
Definition: factory.h:448
void error(const char *fmt,...)
Definition: emacs.cc:58
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition: factory.h:92
CanonicalForm determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
#define LEVELQUOT
Definition: factory.h:80
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
ListIterator< CanonicalForm > CFListIterator
Definition: factory.h:522
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
List< CFAFactor > CFAFList
Definition: factory.h:516
long gf_gf2ff(long a)
Definition: gfops.cc:226
CFMap()
Definition: factory.h:991
List< Variable > Varlist
Definition: factory.h:529
~IntGenerator()
Definition: factory.h:691
CFMatrix * cf_HNF(CFMatrix &A)
The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is...
Definition: cf_hnf.cc:38
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: factory.h:104
char N base
Definition: ValueTraits.h:144
MapPair(const Variable &v, const CanonicalForm &s)
Definition: factory.h:957
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: factory.h:100
void factoryError_intern(const char *s)
Definition: cf_util.cc:70
~GFGenerator()
Definition: factory.h:729
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:245
CanonicalForm sqrt(const CanonicalForm &a)
Definition: factory.h:475
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm gcd(const CanonicalForm &, const CanonicalForm &)
Definition: cf_gcd.cc:262
virtual CFRandom * clone() const
Definition: factory.h:826
class to generate random evaluation points
Definition: cf_reval.h:25
CanonicalForm abs(const CanonicalForm &f)
inline CanonicalForm abs ( const CanonicalForm & f )
Definition: factory.h:622
CFList newordercf(const CFList &PolyList)
Definition: cfCharSets.cc:75
int sign(const CanonicalForm &a)
Definition: factory.h:469
generate random integers
Definition: cf_random.h:55
int ilog2(const CanonicalForm &a)
Definition: factory.h:478
int singular_homog_flag
Definition: cf_factor.cc:377
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:298
generate integers starting from 0
Definition: cf_generator.h:36
Variable alpha
Definition: facAbsBiFact.cc:52
CanonicalForm make_cf(const mpz_ptr n)
Definition: singext.cc:70
CFList charSetN(const CFList &PS)
medial set
Definition: cfCharSets.cc:216
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
term * termList
Definition: factory.h:782
#define Q
Definition: sirandom.c:25
CanonicalForm LC(const CanonicalForm &f)
Definition: factory.h:436
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
int min() const
Definition: ftmpl_array.cc:98
static TreeM * G
Definition: janet.cc:38
Evaluation(int min0, int max0)
Definition: factory.h:646
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f ...
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CF_NO_INLINE CanonicalForm operator%(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:540
bool linearSystemSolve(CFMatrix &M)
Definition: cf_linsys.cc:78
int max() const
Definition: factory.h:651
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void reset()
Definition: factory.h:712
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
virtual class for internal CanonicalForm&#39;s
Definition: int_cf.h:39
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) ...
Definition: cf_ops.cc:402
void prune(Variable &alpha)
Definition: variable.cc:261
CanonicalForm tailcoeff(const CanonicalForm &f)
Definition: factory.h:451
CanonicalForm mapinto() const
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
char getDefaultExtName()
Definition: variable.cc:249
char getDefaultVarName()
Definition: variable.cc:244
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: factory.h:90
#define CF_NO_INLINE
Definition: factory.h:779
return modpk(p, k)
#define M
Definition: sirandom.c:24
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:94
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
CanonicalForm num() const
num() returns the numerator of CO if CO is a rational number, CO itself otherwise.
GFRandom()
Definition: factory.h:835
static Variable highest()
Definition: factory.h:134
CFMap(const Variable &v)
Definition: factory.h:993
const ring r
Definition: syzextra.cc:208
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int _level
Definition: factory.h:118
CanonicalForm make_cf_from_gf(const int z)
Definition: singext.cc:86
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int max() const
Definition: ftmpl_array.cc:104
IntGenerator()
Definition: factory.h:690
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2...
Definition: cf_chinese.cc:52
AFactor< CanonicalForm > CFAFactor
Definition: factory.h:515
int j
Definition: myNF.cc:70
static int max(int a, int b)
Definition: fast_mult.cc:264
virtual CanonicalForm generate() const
Definition: factory.h:825
ListIterator< CFFactor > CFFListIterator
Definition: factory.h:520
FFGenerator()
Definition: factory.h:709
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition: cfCharSets.cc:101
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister ...
Definition: cfCharSets.cc:150
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition: fac_util.cc:89
void factoryseed(int s)
random seed initializer
Definition: cf_random.cc:176
int level() const
Definition: factory.h:132
bool gf_isff(long a)
Definition: gfops.cc:270
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
virtual bool hasItems() const
Definition: factory.h:675
CFList FS2
candidate factors that might get removed
#define A
Definition: sirandom.c:23
int igcd(int a, int b)
Definition: cf_util.cc:51
Evaluation()
Definition: factory.h:645
int probIrredTest(const CanonicalForm &F, double error)
given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-er...
Definition: facIrredTest.cc:63
Matrix< CanonicalForm > CFMatrix
Definition: factory.h:524
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
modified characteristic set, i.e. a characteristic set with certain factors removed ...
Definition: cfCharSets.cc:356
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) ...
Definition: cf_ops.cc:440
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
Definition: facAbsFact.cc:267
int m
Definition: cfEzgcd.cc:119
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r...
int cf_getPrime(int i)
Definition: cf_primes.cc:14
Variable()
Definition: factory.h:121
List< CFFactor > CFFList
Definition: factory.h:519
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: factory.h:94
FILE * f
Definition: checklibs.c:9
generate random elements in F_p
Definition: cf_random.h:43
int i
Definition: cfEzgcd.cc:123
Variable(const Variable &v)
Definition: factory.h:125
bool hasItems() const
Definition: factory.h:757
CanonicalForm euclideanNorm(const CanonicalForm &f)
CanonicalForm euclideanNorm ( const CanonicalForm & f )
void setCharacteristic(int c)
Definition: cf_char.cc:23
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
void reset()
Definition: factory.h:693
virtual ~Evaluation()
Definition: factory.h:648
Evaluation(const Evaluation &e)
Definition: factory.h:647
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true)
modular resultant algorihtm over Z
Variable next() const
Definition: factory.h:135
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm getGFGenerator()
Definition: cf_char.cc:62
char name() const
Definition: variable.cc:122
ListIterator< Variable > VarlistIterator
Definition: factory.h:530
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
CanonicalForm leftShift(const CanonicalForm &F, int n)
left shift the main variable of F by n
Definition: cf_ops.cc:683
int min() const
Definition: factory.h:650
List< CanonicalForm > CFList
Definition: factory.h:521
void Off(int)
switches
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
CanonicalForm num(const CanonicalForm &f)
Definition: factory.h:463
CanonicalForm head(const CanonicalForm &f)
Definition: factory.h:486
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
void On(int)
switches
virtual void reset()
Definition: factory.h:676
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
~FFGenerator()
Definition: factory.h:710
class CFMap
Definition: cf_map.h:84
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
friend bool operator>(const Variable &lhs, const Variable &rhs)
Definition: factory.h:144
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: factory.h:102
generate random elements in F_p(alpha)
Definition: cf_random.h:70
int getk() const
Definition: factory.h:920
CanonicalForm den() const
den() returns the denominator of CO if CO is a rational number, 1 (from the current domain!) otherwis...
~FFRandom()
Definition: factory.h:848
ISTREAM & operator>>(ISTREAM &is, CanonicalForm &cf)
class to evaluate a polynomial at points
Definition: cf_eval.h:31
void(* factoryError)(const char *s)
Definition: cf_util.cc:75
CanonicalForm subst() const
Definition: factory.h:963
Variable mvar(const CanonicalForm &f)
Definition: factory.h:460
Variable & operator=(const Variable &v)
Definition: factory.h:127
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 ...
int cf_getNumPrimes()
Definition: cf_primes.cc:23
CanonicalForm mipo
Definition: facAlgExt.cc:57
void chineseRemainderCached(CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
Definition: cf_chinese.cc:264
~GFRandom()
Definition: factory.h:836
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
b *CanonicalForm B
Definition: facBivar.cc:51
virtual CFGenerator * clone() const
Definition: factory.h:679
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CanonicalForm getpk() const
Definition: factory.h:922
CF_INLINE CanonicalForm operator*(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:517
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:197
int ipower(int b, int n)
int ipower ( int b, int m )
Definition: cf_util.cc:25
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
generate all elements in GF starting from 0
Definition: cf_generator.h:74
Variable x
Definition: cfModGcd.cc:4023
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
Definition: cf_resultant.cc:42
CanonicalForm psq(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CFMap(const Variable &v, const CanonicalForm &s)
Definition: factory.h:994
bool isZero(const CFArray &A)
checks if entries of A are zero
#define OSTREAM
Definition: canonicalform.h:16
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
friend void swap_levels()
CF_INLINE CanonicalForm operator+(const CanonicalForm &, const CanonicalForm &)
CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs...
Definition: cf_inline.cc:496
int getGFDegree()
Definition: cf_char.cc:56
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
friend bool operator>=(const Variable &lhs, const Variable &rhs)
Definition: factory.h:152
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:219
virtual class for random element generation
Definition: cf_random.h:21
void sort(CFArray &A, int l=0)
quick sort A
int level() const
level() returns the level of CO.
List< MapPair > MPList
Definition: factory.h:970
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
p exp[i]
Definition: DebugPrint.cc:39
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
Definition: cfUnivarGcd.cc:173
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
int factoryrandom(int n)
random integers with abs less than n
Definition: cf_random.cc:168
CanonicalForm mapinto(const CanonicalForm &f)
Definition: factory.h:481
~modpk()
Definition: factory.h:918
kBucketDestroy & P
Definition: myNF.cc:191
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
virtual void next()
Definition: factory.h:678
int taildegree() const
taildegree() returns -1 for the zero polynomial, 0 if CO is in a base domain, otherwise the least deg...
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int ExtensionLevel()
Definition: variable.cc:254
CanonicalForm Lc(const CanonicalForm &f)
Definition: factory.h:433
CF_NO_INLINE CanonicalForm operator/(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:529
const poly b
Definition: syzextra.cc:213
CFList charSet(const CFList &PS)
characteristic set
Definition: cfCharSets.cc:187
ListIterator< CFAFactor > CFAFListIterator
Definition: factory.h:517
bool isOn(int)
switches
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22
int headdegree(const CanonicalForm &f)
Definition: factory.h:495
int sign() const
int CanonicalForm::sign () const
#define ISTREAM
Definition: canonicalform.h:17
Factor< CanonicalForm > CFFactor
Definition: factory.h:518
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
CF_NO_INLINE CanonicalForm operator-(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:505
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: factory.h:98
List< CFList > ListCFList
Definition: factory.h:525
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
ListCFList charSeries(const CFList &L)
characteristic series
Definition: cfCharSets.cc:411
Varlist neworder(const CFList &PolyList)
int getp() const
Definition: factory.h:919
virtual CanonicalForm item() const
Definition: factory.h:677
CanonicalForm blcm(const CanonicalForm &f, const CanonicalForm &g)
CFList modCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
modified medial set
Definition: cfCharSets.cc:284
CanonicalForm den(const CanonicalForm &f)
Definition: factory.h:466
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: factory.h:472
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
CFMap(const CFMap &m)
Definition: factory.h:997
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
REvaluation(int min0, int max0, const CFRandom &sample)
Definition: factory.h:1025
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CanonicalForm LC() const