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
compareFactors(const CFFactor & f,const CFFactor & g)19 compareFactors( const CFFactor & f, const CFFactor & g )
20 {
21     return f.exp() > g.exp();
22 }
23 
24 CFFList
sortCFFList(CFFList & F)25 sortCFFList( CFFList & F )
26 {
27     F.sort( compareFactors );
28 
29     int exp;
30     CanonicalForm f;
31     CFFListIterator I = F;
32     CFFList result;
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 
sqrFreeZ(const CanonicalForm & a)49 CFFList sqrFreeZ ( const CanonicalForm & a )
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 
114 CanonicalForm
sqrfPart(const CanonicalForm & F)115 sqrfPart (const CanonicalForm& F)
116 {
117   if (F.inCoeffDomain())
118     return F;
119   CFMap M;
120   CanonicalForm A= compress (F, M);
121   CanonicalForm w, v, b;
122   CanonicalForm result;
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 
divexpfunc(CanonicalForm &,int & e)159 static void divexpfunc ( CanonicalForm &, int & e )
160 {
161     e /= divexp;
162 }
163 
sqrFreeFp(const CanonicalForm & f)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
212