source: git/factory/fac_sqrfree.cc @ d92d71

spielwiese
Last change on this file since d92d71 was f78374, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: more changes of squarefree decomposition according to master
  • Property mode set to 100644
File size: 4.8 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4#include "config.h"
5
6#include "cf_assert.h"
7
8#include "cf_defs.h"
9#include "canonicalform.h"
10#include "cf_map.h"
11#include "cf_algorithm.h"
12
13static int divexp = 1;
14
15static void divexpfunc ( CanonicalForm &, int & e )
16{
17    e /= divexp;
18}
19
20static int
21compareFactors( const CFFactor & f, const CFFactor & g )
22{
23    return f.exp() > g.exp();
24}
25
26CFFList
27sortCFFList( CFFList & F )
28{
29    F.sort( compareFactors );
30
31    int exp;
32    CanonicalForm f;
33    CFFListIterator I = F;
34    CFFList result;
35
36    // join elements with the same degree
37    while ( I.hasItem() ) {
38        f = I.getItem().factor();
39        exp = I.getItem().exp();
40        I++;
41        while ( I.hasItem() && I.getItem().exp() == exp ) {
42            f *= I.getItem().factor();
43            I++;
44        }
45        result.append( CFFactor( f, exp ) );
46    }
47
48    return result;
49}
50
51CFFList sqrFreeFp ( const CanonicalForm & f )
52{
53    CanonicalForm t0 = f, t, v, w, h;
54    CanonicalForm leadcf = t0.lc();
55    Variable x = f.mvar();
56    CFFList F;
57    int p = getCharacteristic();
58    int k, e = 1;
59
60    if ( ! leadcf.isOne() )
61        t0 /= leadcf;
62
63    divexp = p;
64    while ( t0.degree(x) > 0 )
65    {
66        t = gcd( t0, t0.deriv() );
67        v = t0 / t;
68        k = 0;
69        while ( v.degree(x) > 0 )
70        {
71            k = k+1;
72            if ( k % p == 0 )
73            {
74                t /= v;
75                k = k+1;
76            }
77            w = gcd( t, v );
78            h = v / w;
79            v = w;
80            t /= v;
81            if ( h.degree(x) > 0 )
82                F.append( CFFactor( h/h.lc(), e*k ) );
83        }
84        t0 = apply( t, divexpfunc );
85        e = p * e;
86    }
87    if ( ! leadcf.isOne() )
88    {
89        if ( !F.isEmpty() && (F.getFirst().exp() == 1) )
90        {
91            leadcf = F.getFirst().factor() * leadcf;
92            F.removeFirst();
93        }
94        F.insert( CFFactor( leadcf, 1 ) );
95    }
96    return F;
97}
98
99bool isSqrFreeFp( const CanonicalForm & f )
100{
101  CFFList F = sqrFreeFp( f );
102  return ( F.length() == 1 && F.getFirst().exp() == 1 );
103}
104
105bool isSqrFreeZ ( const CanonicalForm & f )
106{
107    return gcd( f, f.deriv() ).degree() == 0;
108}
109
110/*
111
112CFFList sqrFreeZ ( const CanonicalForm & a )
113{
114    CanonicalForm b = a.deriv(), c = gcd( a, b );
115    CanonicalForm y, z, w = a / c;
116    int i = 1;
117    CFFList F;
118
119    while ( ! c.degree() == 0 )
120    {
121        y = gcd( w, c ); z = w / y;
122        if ( degree( z ) > 0 )
123            if ( lc( z ).sign() < 0 )
124                F.append( CFFactor( -z, i ) );
125            else
126                F.append( CFFactor( z, i ) );
127        i++;
128        w = y; c = c / y;
129    }
130    if ( degree( w ) > 0 )
131        if ( lc( w ).sign() < 0 )
132            F.append( CFFactor( -w, i ) );
133        else
134            F.append( CFFactor( w, i ) );
135    return F;
136}
137*/
138
139CFFList sqrFreeZ ( const CanonicalForm & a )
140{
141    if ( a.inCoeffDomain() )
142        return CFFactor( a, 1 );
143    CanonicalForm aa, LcA;
144    if (isOn (SW_RATIONAL))
145    {
146      LcA= bCommonDen (a);
147      aa= a*LcA;
148    }
149    else
150    {
151      LcA= icontent (a);
152      if (lc (a).sign() < 0)
153        LcA= -LcA;
154      aa= a/LcA;
155    }
156    CanonicalForm cont = content( aa );
157    aa /= cont;
158    CanonicalForm b = aa.deriv(), c = gcd( aa, b );
159    CanonicalForm y, z, w = aa / c;
160    int i = 1;
161    CFFList F;
162    Variable v = aa.mvar();
163    while ( ! c.degree(v) == 0 )
164    {
165        y = gcd( w, c ); z = w / y;
166        if ( degree( z, v ) > 0 )
167        {
168          if (isOn (SW_RATIONAL))
169          {
170            z /= Lc (z);
171            z *= bCommonDen (z);
172          }
173          if (lc (z).sign() < 0)
174            z= -z;
175          F.append( CFFactor( z, i ) );
176        }
177        i++;
178        w = y; c = c / y;
179    }
180    if ( degree( w,v ) > 0 )
181    {
182      if (isOn (SW_RATIONAL))
183      {
184        w /= Lc (w);
185        w *= bCommonDen (w);
186      }
187      if (lc (w).sign() < 0)
188        w= -w;
189      F.append( CFFactor( w, i ) );
190    }
191    if ( ! cont.isOne() )
192    {
193        CFFList buf= sqrFreeZ (cont);
194        buf.removeFirst();
195        F = Union( F, buf );
196    }
197    F.insert (CFFactor (LcA, 1));
198    return F;
199}
200
201CanonicalForm
202sqrfPart (const CanonicalForm& F)
203{
204  if (F.inCoeffDomain())
205    return F;
206  CFMap M;
207  CanonicalForm A= compress (F, M);
208  CanonicalForm w, v, b;
209  CanonicalForm result;
210  int i= 1;
211  for (; i <= A.level(); i++)
212  {
213    if (!deriv (A, Variable (i)).isZero())
214      break;
215  }
216
217  w= gcd (A, deriv (A, Variable (i)));
218  b= A/w;
219  result= b;
220  if (degree (w) < 1)
221    return M (result);
222  i++;
223  for (; i <= A.level(); i++)
224  {
225    if (!deriv (w, Variable (i)).isZero())
226    {
227      b= w;
228      w= gcd (w, deriv (w, Variable (i)));
229      b /= w;
230      if (degree (b) < 1)
231        break;
232      CanonicalForm g= gcd (b, result);
233      if (degree (g) > 0)
234        result *= b/g;
235      if (degree (g) <= 0)
236        result *= b;
237    }
238  }
239  result= M (result);
240  return result;
241}
242
Note: See TracBrowser for help on using the repository browser.