[493c477] | 1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
[173e86] | 2 | |
---|
[e4fe2b] | 3 | #include "config.h" |
---|
[2dd068] | 4 | |
---|
[650f2d8] | 5 | #include "cf_assert.h" |
---|
[173e86] | 6 | |
---|
[2dd068] | 7 | #include "cf_defs.h" |
---|
| 8 | #include "canonicalform.h" |
---|
[6f30b8f] | 9 | #include "cf_map.h" |
---|
[f78374] | 10 | #include "cf_algorithm.h" |
---|
[2dd068] | 11 | |
---|
| 12 | static int divexp = 1; |
---|
| 13 | |
---|
| 14 | static void divexpfunc ( CanonicalForm &, int & e ) |
---|
| 15 | { |
---|
| 16 | e /= divexp; |
---|
| 17 | } |
---|
| 18 | |
---|
[e89e56] | 19 | static int |
---|
| 20 | compareFactors( const CFFactor & f, const CFFactor & g ) |
---|
[0d500e] | 21 | { |
---|
| 22 | return f.exp() > g.exp(); |
---|
| 23 | } |
---|
| 24 | |
---|
[e89e56] | 25 | CFFList |
---|
| 26 | sortCFFList( CFFList & F ) |
---|
[0d500e] | 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 |
---|
[e89e56] | 36 | while ( I.hasItem() ) { |
---|
[d4932a] | 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 ) ); |
---|
[0d500e] | 45 | } |
---|
| 46 | |
---|
| 47 | return result; |
---|
| 48 | } |
---|
| 49 | |
---|
[e89e56] | 50 | CFFList sqrFreeFp ( const CanonicalForm & f ) |
---|
[2dd068] | 51 | { |
---|
| 52 | CanonicalForm t0 = f, t, v, w, h; |
---|
[d6b072c] | 53 | CanonicalForm leadcf = t0.lc(); |
---|
[2dd068] | 54 | Variable x = f.mvar(); |
---|
| 55 | CFFList F; |
---|
| 56 | int p = getCharacteristic(); |
---|
| 57 | int k, e = 1; |
---|
| 58 | |
---|
[d6b072c] | 59 | if ( ! leadcf.isOne() ) |
---|
[d4932a] | 60 | t0 /= leadcf; |
---|
[d6b072c] | 61 | |
---|
[2dd068] | 62 | divexp = p; |
---|
[434e415] | 63 | while ( t0.degree(x) > 0 ) |
---|
| 64 | { |
---|
[d4932a] | 65 | t = gcd( t0, t0.deriv() ); |
---|
| 66 | v = t0 / t; |
---|
| 67 | k = 0; |
---|
| 68 | while ( v.degree(x) > 0 ) |
---|
[434e415] | 69 | { |
---|
[d4932a] | 70 | k = k+1; |
---|
| 71 | if ( k % p == 0 ) |
---|
[434e415] | 72 | { |
---|
[d4932a] | 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; |
---|
[2dd068] | 85 | } |
---|
[434e415] | 86 | if ( ! leadcf.isOne() ) |
---|
| 87 | { |
---|
[d4932a] | 88 | if ( !F.isEmpty() && (F.getFirst().exp() == 1) ) |
---|
[434e415] | 89 | { |
---|
[d4932a] | 90 | leadcf = F.getFirst().factor() * leadcf; |
---|
| 91 | F.removeFirst(); |
---|
| 92 | } |
---|
| 93 | F.insert( CFFactor( leadcf, 1 ) ); |
---|
[d6b072c] | 94 | } |
---|
[2dd068] | 95 | return F; |
---|
| 96 | } |
---|
[ef9d6b] | 97 | |
---|
[e89e56] | 98 | bool isSqrFreeFp( const CanonicalForm & f ) |
---|
[ef9d6b] | 99 | { |
---|
[e89e56] | 100 | CFFList F = sqrFreeFp( f ); |
---|
| 101 | return ( F.length() == 1 && F.getFirst().exp() == 1 ); |
---|
[ef9d6b] | 102 | } |
---|
| 103 | |
---|
[e89e56] | 104 | bool isSqrFreeZ ( const CanonicalForm & f ) |
---|
[ef9d6b] | 105 | { |
---|
[e89e56] | 106 | return gcd( f, f.deriv() ).degree() == 0; |
---|
[ef9d6b] | 107 | } |
---|
[2dd068] | 108 | |
---|
| 109 | /* |
---|
| 110 | |
---|
| 111 | CFFList 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 | |
---|
[ee586a] | 118 | while ( ! c.degree() == 0 ) |
---|
| 119 | { |
---|
[d4932a] | 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; |
---|
[2dd068] | 128 | } |
---|
| 129 | if ( degree( w ) > 0 ) |
---|
[d4932a] | 130 | if ( lc( w ).sign() < 0 ) |
---|
| 131 | F.append( CFFactor( -w, i ) ); |
---|
| 132 | else |
---|
| 133 | F.append( CFFactor( w, i ) ); |
---|
[2dd068] | 134 | return F; |
---|
| 135 | } |
---|
| 136 | */ |
---|
| 137 | |
---|
[e89e56] | 138 | CFFList sqrFreeZ ( const CanonicalForm & a ) |
---|
[2dd068] | 139 | { |
---|
| 140 | if ( a.inCoeffDomain() ) |
---|
[d4932a] | 141 | return CFFactor( a, 1 ); |
---|
[f78374] | 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; |
---|
[2dd068] | 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(); |
---|
[ee586a] | 162 | while ( ! c.degree(v) == 0 ) |
---|
| 163 | { |
---|
[d4932a] | 164 | y = gcd( w, c ); z = w / y; |
---|
| 165 | if ( degree( z, v ) > 0 ) |
---|
[c1b9927] | 166 | { |
---|
[f78374] | 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 ) ); |
---|
[c1b9927] | 175 | } |
---|
[d4932a] | 176 | i++; |
---|
| 177 | w = y; c = c / y; |
---|
[2dd068] | 178 | } |
---|
| 179 | if ( degree( w,v ) > 0 ) |
---|
[c1b9927] | 180 | { |
---|
[f78374] | 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 ) ); |
---|
[c1b9927] | 189 | } |
---|
[e074407] | 190 | if ( ! cont.isOne() ) |
---|
[ee586a] | 191 | { |
---|
[f78374] | 192 | CFFList buf= sqrFreeZ (cont); |
---|
| 193 | buf.removeFirst(); |
---|
| 194 | F = Union( F, buf ); |
---|
[36652d8] | 195 | } |
---|
[f78374] | 196 | F.insert (CFFactor (LcA, 1)); |
---|
[36652d8] | 197 | return F; |
---|
[2dd068] | 198 | } |
---|
[6f30b8f] | 199 | |
---|
| 200 | CanonicalForm |
---|
| 201 | sqrfPart (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 | |
---|