My Project  debian-1:4.1.2-p1+ds-2
cfSubResGcd.cc
Go to the documentation of this file.
1 #include "config.h"
2 
3 #include "cf_defs.h"
4 #include "cf_algorithm.h"
5 #include "cfEzgcd.h"
6 #include "cfGcdUtil.h"
8 #include "cf_factory.h"
9 #include "cfUnivarGcd.h"
10 
13 {
14  if (f.inCoeffDomain() || g.inCoeffDomain()) //zero case should be caught by gcd
15  return 1;
16  CanonicalForm pi, pi1;
17  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
18  bool bpure, ezgcdon= isOn (SW_USE_EZGCD_P);
19  int delta = degree( f ) - degree( g );
20 
21  if ( delta >= 0 )
22  {
23  pi = f; pi1 = g;
24  }
25  else
26  {
27  pi = g; pi1 = f; delta = -delta;
28  }
29  if (pi.isUnivariate())
30  Ci= 1;
31  else
32  {
33  if (!ezgcdon)
35  Ci = content( pi );
36  if (!ezgcdon)
38  pi = pi / Ci;
39  }
40  if (pi1.isUnivariate())
41  Ci1= 1;
42  else
43  {
44  if (!ezgcdon)
46  Ci1 = content( pi1 );
47  if (!ezgcdon)
49  pi1 = pi1 / Ci1;
50  }
51  C = gcd( Ci, Ci1 );
52  int d= 0;
53  if ( !( pi.isUnivariate() && pi1.isUnivariate() ) )
54  {
55  if ( gcd_test_one( pi1, pi, true, d ) )
56  {
57  C=abs(C);
58  //out_cf("GCD:",C,"\n");
59  return C;
60  }
61  bpure = false;
62  }
63  else
64  {
65  bpure = isPurePoly(pi) && isPurePoly(pi1);
66 #ifdef HAVE_FLINT
67  if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
68  return gcd_univar_flintp(pi,pi1)*C;
69 #else
70 #ifdef HAVE_NTL
71  if (bpure && (CFFactory::gettype() != GaloisFieldDomain))
72  return gcd_univar_ntlp(pi, pi1 ) * C;
73 #endif
74 #endif
75  }
76  Variable v = f.mvar();
77  Hi = power( LC( pi1, v ), delta );
78  int maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
79 
80  if (!(pi.isUnivariate() && pi1.isUnivariate()))
81  {
82  if (size (Hi)*size (pi)/(maxNumVars*3) > 500) //maybe this needs more tuning
83  {
85  C *= gcd (pi, pi1);
87  return C;
88  }
89  }
90 
91  if ( (delta+1) % 2 )
92  bi = 1;
93  else
94  bi = -1;
95  CanonicalForm oldPi= pi, oldPi1= pi1, powHi;
96  while ( degree( pi1, v ) > 0 )
97  {
98  if (!(pi.isUnivariate() && pi1.isUnivariate()))
99  {
100  if (size (pi)/maxNumVars > 500 || size (pi1)/maxNumVars > 500)
101  {
103  C *= gcd (oldPi, oldPi1);
105  return C;
106  }
107  }
108  pi2 = psr( pi, pi1, v );
109  pi2 = pi2 / bi;
110  pi = pi1; pi1 = pi2;
111  maxNumVars= tmax (getNumVars (pi), getNumVars (pi1));
112  if (!pi1.isUnivariate() && (size (pi1)/maxNumVars > 500))
113  {
115  C *= gcd (oldPi, oldPi1);
117  return C;
118  }
119  if ( degree( pi1, v ) > 0 )
120  {
121  delta = degree( pi, v ) - degree( pi1, v );
122  powHi= power (Hi, delta-1);
123  if ( (delta+1) % 2 )
124  bi = LC( pi, v ) * powHi*Hi;
125  else
126  bi = -LC( pi, v ) * powHi*Hi;
127  Hi = power( LC( pi1, v ), delta ) / powHi;
128  if (!(pi.isUnivariate() && pi1.isUnivariate()))
129  {
130  if (size (Hi)*size (pi)/(maxNumVars*3) > 1500) //maybe this needs more tuning
131  {
133  C *= gcd (oldPi, oldPi1);
135  return C;
136  }
137  }
138  }
139  }
140  if ( degree( pi1, v ) == 0 )
141  {
142  C=abs(C);
143  //out_cf("GCD:",C,"\n");
144  return C;
145  }
146  if (!pi.isUnivariate())
147  {
148  if (!ezgcdon)
149  On (SW_USE_EZGCD_P);
150  Ci= gcd (LC (oldPi,v), LC (oldPi1,v));
151  pi /= LC (pi,v)/Ci;
152  Ci= content (pi);
153  pi /= Ci;
154  if (!ezgcdon)
156  }
157  if ( bpure )
158  pi /= pi.lc();
159  C=abs(C*pi);
160  //out_cf("GCD:",C,"\n");
161  return C;
162 }
163 
166 {
167  CanonicalForm pi, pi1;
168  CanonicalForm C, Ci, Ci1, Hi, bi, pi2;
169  int delta = degree( f ) - degree( g );
170 
171  if ( delta >= 0 )
172  {
173  pi = f; pi1 = g;
174  }
175  else
176  {
177  pi = g; pi1 = f; delta = -delta;
178  }
179  Ci = content( pi ); Ci1 = content( pi1 );
180  pi1 = pi1 / Ci1; pi = pi / Ci;
181  C = gcd( Ci, Ci1 );
182  int d= 0;
183  if ( pi.isUnivariate() && pi1.isUnivariate() )
184  {
185 #ifdef HAVE_FLINT
186  if (isPurePoly(pi) && isPurePoly(pi1) )
187  return gcd_univar_flint0(pi, pi1 ) * C;
188 #else
189 #ifdef HAVE_NTL
190  if (isPurePoly(pi) && isPurePoly(pi1) )
191  return gcd_univar_ntl0(pi, pi1 ) * C;
192 #endif
193 #endif
194 #ifndef HAVE_NTL
195  return gcd_poly_univar0( pi, pi1, true ) * C;
196 #endif
197  }
198  else if ( gcd_test_one( pi1, pi, true, d ) )
199  return C;
200  Variable v = f.mvar();
201  Hi = power( LC( pi1, v ), delta );
202  if ( (delta+1) % 2 )
203  bi = 1;
204  else
205  bi = -1;
206  while ( degree( pi1, v ) > 0 )
207  {
208  pi2 = psr( pi, pi1, v );
209  pi2 = pi2 / bi;
210  pi = pi1; pi1 = pi2;
211  if ( degree( pi1, v ) > 0 )
212  {
213  delta = degree( pi, v ) - degree( pi1, v );
214  if ( (delta+1) % 2 )
215  bi = LC( pi, v ) * power( Hi, delta );
216  else
217  bi = -LC( pi, v ) * power( Hi, delta );
218  Hi = power( LC( pi1, v ), delta ) / power( Hi, delta-1 );
219  }
220  }
221  if ( degree( pi1, v ) == 0 )
222  return C;
223  else
224  return C * pp( pi );
225 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
int degree(const CanonicalForm &f)
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
CanonicalForm LC(const CanonicalForm &f)
Extended Zassenhaus GCD over finite fields and Z.
bool gcd_test_one(const CanonicalForm &f, const CanonicalForm &g, bool swap, int &d)
Coprimality Check. f and g are assumed to have the same level. If swap is true, the main variables of...
Definition: cfGcdUtil.cc:21
coprimality check and change of representation mod n
g
Definition: cfModGcd.cc:4031
int maxNumVars
Definition: cfModGcd.cc:4071
CanonicalForm subResGCD_p(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over finite fields. In case things become too dense we switch to a modular algorithm
Definition: cfSubResGcd.cc:12
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
Definition: cfSubResGcd.cc:165
CanonicalForm gcd_univar_flint0(const CanonicalForm &F, const CanonicalForm &G)
Definition: cfUnivarGcd.cc:60
CanonicalForm gcd_univar_flintp(const CanonicalForm &F, const CanonicalForm &G)
Definition: cfUnivarGcd.cc:47
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
declarations of higher level algorithms.
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
factory switches.
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:35
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:43
#define GaloisFieldDomain
Definition: cf_defs.h:23
Interface to generate InternalCF's over various domains from intrinsic types or mpz_t's.
FILE * f
Definition: checklibs.c:9
static int gettype()
Definition: cf_factory.h:28
factory's main class
Definition: canonicalform.h:83
bool isUnivariate() const
factory's class for variables
Definition: factory.h:118
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define pi
Definition: libparse.cc:1145
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int gcd(int a, int b)
Definition: walkSupport.cc:836