1 | // emacs edit mode for this file is -*- C++ -*- |
---|
2 | // $Id: fac_sqrfree.cc,v 1.0 1996-05-17 10:59:45 stobbe Exp $ |
---|
3 | |
---|
4 | #include "assert.h" |
---|
5 | #include "cf_defs.h" |
---|
6 | #include "canonicalform.h" |
---|
7 | |
---|
8 | /* |
---|
9 | $Log: not supported by cvs2svn $ |
---|
10 | */ |
---|
11 | |
---|
12 | static int divexp = 1; |
---|
13 | |
---|
14 | static void divexpfunc ( CanonicalForm &, int & e ) |
---|
15 | { |
---|
16 | e /= divexp; |
---|
17 | } |
---|
18 | |
---|
19 | CFFList sqrFreeFp ( const CanonicalForm & f ) |
---|
20 | { |
---|
21 | CanonicalForm t0 = f, t, v, w, h; |
---|
22 | Variable x = f.mvar(); |
---|
23 | CFFList F; |
---|
24 | int p = getCharacteristic(); |
---|
25 | int k, e = 1; |
---|
26 | |
---|
27 | divexp = p; |
---|
28 | while ( t0.degree(x) > 0 ) { |
---|
29 | t = gcd( t0, t0.deriv() ); |
---|
30 | v = t0 / t; |
---|
31 | k = 0; |
---|
32 | while ( v.degree(x) > 0 ) { |
---|
33 | k = k+1; |
---|
34 | if ( k % p == 0 ) { |
---|
35 | t /= v; |
---|
36 | k = k+1; |
---|
37 | } |
---|
38 | w = gcd( t, v ); |
---|
39 | h = v / w; |
---|
40 | v = w; |
---|
41 | t /= v; |
---|
42 | if ( h.degree(x) > 0 ) |
---|
43 | F.append( CFFactor( h, e*k ) ); |
---|
44 | } |
---|
45 | t0 = apply( t, divexpfunc ); |
---|
46 | e = p * e; |
---|
47 | } |
---|
48 | return F; |
---|
49 | } |
---|
50 | |
---|
51 | bool isSqrFreeFp( const CanonicalForm & f ) |
---|
52 | { |
---|
53 | CFFList F = sqrFreeFp( f ); |
---|
54 | return ( F.length() == 1 && F.getFirst().exp() == 1 ); |
---|
55 | } |
---|
56 | |
---|
57 | int isSqrFreeZ ( const CanonicalForm & f ) |
---|
58 | { |
---|
59 | return gcd( f, f.deriv() ).degree() == 0; |
---|
60 | } |
---|
61 | |
---|
62 | /* |
---|
63 | |
---|
64 | CFFList sqrFreeZ ( const CanonicalForm & a ) |
---|
65 | { |
---|
66 | CanonicalForm b = a.deriv(), c = gcd( a, b ); |
---|
67 | CanonicalForm y, z, w = a / c; |
---|
68 | int i = 1; |
---|
69 | CFFList F; |
---|
70 | |
---|
71 | while ( ! c.degree() == 0 ) { |
---|
72 | y = gcd( w, c ); z = w / y; |
---|
73 | if ( degree( z ) > 0 ) |
---|
74 | if ( lc( z ).sign() < 0 ) |
---|
75 | F.append( CFFactor( -z, i ) ); |
---|
76 | else |
---|
77 | F.append( CFFactor( z, i ) ); |
---|
78 | i++; |
---|
79 | w = y; c = c / y; |
---|
80 | } |
---|
81 | if ( degree( w ) > 0 ) |
---|
82 | if ( lc( w ).sign() < 0 ) |
---|
83 | F.append( CFFactor( -w, i ) ); |
---|
84 | else |
---|
85 | F.append( CFFactor( w, i ) ); |
---|
86 | return F; |
---|
87 | } |
---|
88 | */ |
---|
89 | |
---|
90 | CFFList sqrFreeZ ( const CanonicalForm & a ) |
---|
91 | { |
---|
92 | if ( a.inCoeffDomain() ) |
---|
93 | return CFFactor( a, 1 ); |
---|
94 | CanonicalForm cont = content( a ); |
---|
95 | CanonicalForm aa = a / cont; |
---|
96 | CanonicalForm b = aa.deriv(), c = gcd( aa, b ); |
---|
97 | CanonicalForm y, z, w = aa / c; |
---|
98 | int i = 1; |
---|
99 | CFFList F; |
---|
100 | Variable v = aa.mvar(); |
---|
101 | while ( ! c.degree(v) == 0 ) { |
---|
102 | y = gcd( w, c ); z = w / y; |
---|
103 | if ( degree( z, v ) > 0 ) |
---|
104 | if ( lc( z ).sign() < 0 ) |
---|
105 | F.append( CFFactor( -z, i ) ); |
---|
106 | else |
---|
107 | F.append( CFFactor( z, i ) ); |
---|
108 | i++; |
---|
109 | w = y; c = c / y; |
---|
110 | } |
---|
111 | if ( degree( w,v ) > 0 ) |
---|
112 | if ( lc( w ).sign() < 0 ) |
---|
113 | F.append( CFFactor( -w, i ) ); |
---|
114 | else |
---|
115 | F.append( CFFactor( w, i ) ); |
---|
116 | if ( ! cont.isOne() ) |
---|
117 | return Union( F, sqrFreeZ( cont ) ); |
---|
118 | else |
---|
119 | return F; |
---|
120 | } |
---|