source: git/factory/fac_sqrfree.cc @ a52291

spielwiese
Last change on this file since a52291 was e4fe2b, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
FIX: Fixed huge BUG in cf_gmp.h CHG: starting to cleanup factory
  • Property mode set to 100644
File size: 4.7 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
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 cont = content( a );
143    CanonicalForm aa = a / cont;
144    CanonicalForm b = aa.deriv(), c = gcd( aa, b );
145    CanonicalForm y, z, w = aa / c;
146    int i = 1;
147    CFFList F;
148    Variable v = aa.mvar();
149    while ( ! c.degree(v) == 0 )
150    {
151        y = gcd( w, c ); z = w / y;
152        if ( degree( z, v ) > 0 )
153        {
154            if ( lc( z ).sign() < 0 )
155                F.append( CFFactor( -z, i ) );
156            else
157                F.append( CFFactor( z, i ) );
158        }
159        i++;
160        w = y; c = c / y;
161    }
162    if ( degree( w,v ) > 0 )
163    {
164        if ( lc( w ).sign() < 0 )
165            F.append( CFFactor( -w, i ) );
166        else
167            F.append( CFFactor( w, i ) );
168    }
169    if ( ! cont.isOne() )
170        F = Union( F, sqrFreeZ( cont ) );
171    if ( lc( a ).sign() < 0 )
172    {
173        if ( F.getFirst().exp() == 1 )
174        {
175            CanonicalForm f = F.getFirst().factor();
176            CFFListIterator(F).getItem() = CFFactor( -f, 1 );
177        }
178        else
179            F.insert( CFFactor( -1, 1 ) );
180    }
181    return F;
182}
183
184CanonicalForm
185sqrfPart (const CanonicalForm& F)
186{
187  if (F.inCoeffDomain())
188    return F;
189  CFMap M;
190  CanonicalForm A= compress (F, M);
191  CanonicalForm w, v, b;
192  CanonicalForm result;
193  int i= 1;
194  for (; i <= A.level(); i++)
195  {
196    if (!deriv (A, Variable (i)).isZero())
197      break;
198  }
199
200  w= gcd (A, deriv (A, Variable (i)));
201  b= A/w;
202  result= b;
203  if (degree (w) < 1)
204    return M (result);
205  i++;
206  for (; i <= A.level(); i++)
207  {
208    if (!deriv (w, Variable (i)).isZero())
209    {
210      b= w;
211      w= gcd (w, deriv (w, Variable (i)));
212      b /= w;
213      if (degree (b) < 1)
214        break;
215      CanonicalForm g= gcd (b, result);
216      if (degree (g) > 0)
217        result *= b/g;
218      if (degree (g) <= 0)
219        result *= b;
220    }
221  }
222  result= M (result);
223  return result;
224}
225
Note: See TracBrowser for help on using the repository browser.