source: git/factory/fac_sqrfree.cc @ 8d2c11

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