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