My Project
fac_sqrfree.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 
4 #include "config.h"
5 
6 
7 #include "cf_assert.h"
8 
9 #include "cf_defs.h"
10 #include "canonicalform.h"
11 #include "cf_map.h"
12 #include "cf_algorithm.h"
13 
14 #ifdef HAVE_FLINT
15 #include "FLINTconvert.h" // for __FLINT_RELEASE
16 #endif
17 
18 static int
19 compareFactors( const CFFactor & f, const CFFactor & g )
20 {
21  return f.exp() > g.exp();
22 }
23 
24 CFFList
26 {
27  F.sort( compareFactors );
28 
29  int exp;
31  CFFListIterator I = F;
33 
34  // join elements with the same degree
35  while ( I.hasItem() ) {
36  f = I.getItem().factor();
37  exp = I.getItem().exp();
38  I++;
39  while ( I.hasItem() && I.getItem().exp() == exp ) {
40  f *= I.getItem().factor();
41  I++;
42  }
43  result.append( CFFactor( f, exp ) );
44  }
45 
46  return result;
47 }
48 
50 {
51  if ( a.inCoeffDomain() )
52  return CFFactor( a, 1 );
53  CanonicalForm aa, LcA;
54  if (isOn (SW_RATIONAL))
55  {
56  LcA= bCommonDen (a);
57  aa= a*LcA;
58  }
59  else
60  {
61  LcA= icontent (a);
62  if (lc (a).sign() < 0)
63  LcA= -LcA;
64  aa= a/LcA;
65  }
66  CanonicalForm cont = content( aa );
67  aa /= cont;
68  CanonicalForm b = aa.deriv(), c = gcd( aa, b );
69  CanonicalForm y, z, w = aa / c;
70  int i = 1;
71  CFFList F;
72  Variable v = aa.mvar();
73  CanonicalForm lcinv;
74  while ( c.degree(v) != 0 )
75  {
76  y = gcd( w, c ); z = w / y;
77  if ( degree( z, v ) > 0 )
78  {
79  if (isOn (SW_RATIONAL))
80  {
81  lcinv= 1/Lc (z);
82  z *= lcinv;
83  z *= bCommonDen (z);
84  }
85  if (lc (z).sign() < 0)
86  z= -z;
87  F.append( CFFactor( z, i ) );
88  }
89  i++;
90  w = y; c = c / y;
91  }
92  if ( degree( w,v ) > 0 )
93  {
94  if (isOn (SW_RATIONAL))
95  {
96  lcinv= 1/Lc (w);
97  w *= lcinv;
98  w *= bCommonDen (w);
99  }
100  if (lc (w).sign() < 0)
101  w= -w;
102  F.append( CFFactor( w, i ) );
103  }
104  if ( ! cont.isOne() )
105  {
106  CFFList buf= sqrFreeZ (cont);
107  buf.removeFirst();
108  F = Union( F, buf );
109  }
110  F.insert (CFFactor (LcA, 1));
111  return F;
112 }
113 
116 {
117  if (F.inCoeffDomain())
118  return F;
119  CFMap M;
120  CanonicalForm A= compress (F, M);
121  CanonicalForm w, v, b;
123  int i= 1;
124  for (; i <= A.level(); i++)
125  {
126  if (!deriv (A, Variable (i)).isZero())
127  break;
128  }
129 
130  w= gcd (A, deriv (A, Variable (i)));
131  b= A/w;
132  result= b;
133  if (degree (w) < 1)
134  return M (result);
135  i++;
136  for (; i <= A.level(); i++)
137  {
138  if (!deriv (w, Variable (i)).isZero())
139  {
140  b= w;
141  w= gcd (w, deriv (w, Variable (i)));
142  b /= w;
143  if (degree (b) < 1)
144  break;
145  CanonicalForm g= gcd (b, result);
146  if (degree (g) > 0)
147  result *= b/g;
148  if (degree (g) <= 0)
149  result *= b;
150  }
151  }
152  result= M (result);
153  return result;
154 }
155 
156 #if !defined(HAVE_NTL)
157 static int divexp = 1;
158 
159 static void divexpfunc ( CanonicalForm &, int & e )
160 {
161  e /= divexp;
162 }
163 
164 CFFList sqrFreeFp ( const CanonicalForm & f )
165 {
166  CanonicalForm t0 = f, t, v, w, h;
167  CanonicalForm leadcf = t0.lc();
168  Variable x = f.mvar();
169  CFFList F;
170  int p = getCharacteristic();
171  int k, e = 1;
172 
173  if ( ! leadcf.isOne() )
174  t0 /= leadcf;
175 
176  divexp = p;
177  while ( t0.degree(x) > 0 )
178  {
179  t = gcd( t0, t0.deriv() );
180  v = t0 / t;
181  k = 0;
182  while ( v.degree(x) > 0 )
183  {
184  k = k+1;
185  if ( k % p == 0 )
186  {
187  t /= v;
188  k = k+1;
189  }
190  w = gcd( t, v );
191  h = v / w;
192  v = w;
193  t /= v;
194  if ( h.degree(x) > 0 )
195  F.append( CFFactor( h/h.lc(), e*k ) );
196  }
197  t0 = apply( t, divexpfunc );
198  e = p * e;
199  }
200  if ( ! leadcf.isOne() )
201  {
202  if ( !F.isEmpty() && (F.getFirst().exp() == 1) )
203  {
204  leadcf = F.getFirst().factor() * leadcf;
205  F.removeFirst();
206  }
207  F.insert( CFFactor( leadcf, 1 ) );
208  }
209  return F;
210 }
211 #endif
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
bool isOn(int sw)
switches
Header for factory's main class CanonicalForm.
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
CanonicalForm apply(const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )
Definition: cf_ops.cc:402
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
assertions for Factory
factory switches.
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
map polynomials
FILE * f
Definition: checklibs.c:9
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
bool inCoeffDomain() const
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
const CanonicalForm & w
Definition: facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
Definition: fac_sqrfree.cc:115
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
static int compareFactors(const CFFactor &f, const CFFactor &g)
Definition: fac_sqrfree.cc:19
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
CFFList sqrFreeFp(const CanonicalForm &f)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR Poly * h
Definition: janet.cc:971
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
static int sign(int x)
Definition: ring.cc:3469
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836