[493c477] | 1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
[2dd068] | 2 | |
---|
[9f7665] | 3 | |
---|
[e4fe2b] | 4 | #include "config.h" |
---|
[9f7665] | 5 | |
---|
[e9de47] | 6 | |
---|
[650f2d8] | 7 | #include "cf_assert.h" |
---|
[daa556] | 8 | #include "cf_factory.h" |
---|
| 9 | |
---|
[2dd068] | 10 | #include "cf_defs.h" |
---|
| 11 | #include "cf_globals.h" |
---|
| 12 | #include "canonicalform.h" |
---|
| 13 | #include "cf_iter.h" |
---|
| 14 | #include "int_cf.h" |
---|
[dad0bc5] | 15 | #include "cf_algorithm.h" |
---|
[2dd068] | 16 | #include "imm.h" |
---|
| 17 | #include "gfops.h" |
---|
[c22249] | 18 | #include "facMul.h" |
---|
[9c9ed17] | 19 | #include "FLINTconvert.h" |
---|
[e4fe2b] | 20 | |
---|
[ee668e] | 21 | #include <factory/cf_gmp.h> |
---|
[e4fe2b] | 22 | |
---|
[c5323e] | 23 | #ifndef NOSTREAMIO |
---|
[181148] | 24 | CanonicalForm readCF( ISTREAM& ); |
---|
[c5323e] | 25 | #endif /* NOSTREAMIO */ |
---|
[2dd068] | 26 | |
---|
[b60ef7] | 27 | //{{{ constructors, destructors, selectors |
---|
[d07137] | 28 | CanonicalForm::CanonicalForm( const char * str, const int base ) : value( CFFactory::basic( str, base ) ) |
---|
[2dd068] | 29 | { |
---|
| 30 | } |
---|
| 31 | |
---|
| 32 | InternalCF* |
---|
| 33 | CanonicalForm::getval() const |
---|
| 34 | { |
---|
| 35 | if ( is_imm( value ) ) |
---|
[094eed] | 36 | return value; |
---|
[2dd068] | 37 | else |
---|
[094eed] | 38 | return value->copyObject(); |
---|
[2dd068] | 39 | } |
---|
| 40 | |
---|
[b60ef7] | 41 | CanonicalForm |
---|
| 42 | CanonicalForm::deepCopy() const |
---|
| 43 | { |
---|
| 44 | if ( is_imm( value ) ) |
---|
[094eed] | 45 | return *this; |
---|
[b60ef7] | 46 | else |
---|
[094eed] | 47 | return CanonicalForm( value->deepCopyObject() ); |
---|
[b60ef7] | 48 | } |
---|
[b15cf85] | 49 | |
---|
| 50 | void |
---|
| 51 | CanonicalForm::mpzval(mpz_t val) const |
---|
| 52 | { |
---|
| 53 | ASSERT (!is_imm (value) && value->levelcoeff() == IntegerDomain, "non-immediate integer expected"); |
---|
| 54 | getmpi (value, val); |
---|
| 55 | } |
---|
[b60ef7] | 56 | //}}} |
---|
| 57 | |
---|
| 58 | //{{{ predicates |
---|
[9c3bc93] | 59 | #if 0 |
---|
[2dd068] | 60 | bool |
---|
| 61 | CanonicalForm::isImm() const |
---|
| 62 | { |
---|
| 63 | return is_imm( value ); |
---|
| 64 | } |
---|
[9c3bc93] | 65 | #endif |
---|
[2dd068] | 66 | |
---|
| 67 | bool |
---|
| 68 | CanonicalForm::inZ() const |
---|
| 69 | { |
---|
| 70 | if ( is_imm( value ) == INTMARK ) |
---|
[094eed] | 71 | return true; |
---|
[2dd068] | 72 | else if ( is_imm( value ) ) |
---|
[094eed] | 73 | return false; |
---|
[2dd068] | 74 | else |
---|
[094eed] | 75 | return value->levelcoeff() == IntegerDomain; |
---|
[2dd068] | 76 | } |
---|
| 77 | |
---|
| 78 | bool |
---|
| 79 | CanonicalForm::inQ() const |
---|
| 80 | { |
---|
| 81 | if ( is_imm( value ) == INTMARK ) |
---|
[094eed] | 82 | return true; |
---|
[2dd068] | 83 | else if ( is_imm( value ) ) |
---|
[094eed] | 84 | return false; |
---|
[2dd068] | 85 | else |
---|
[094eed] | 86 | return value->levelcoeff() == IntegerDomain || |
---|
| 87 | value->levelcoeff() == RationalDomain; |
---|
[2dd068] | 88 | } |
---|
| 89 | |
---|
| 90 | bool |
---|
| 91 | CanonicalForm::inFF() const |
---|
| 92 | { |
---|
| 93 | return is_imm( value ) == FFMARK; |
---|
| 94 | } |
---|
| 95 | |
---|
| 96 | bool |
---|
| 97 | CanonicalForm::inGF() const |
---|
| 98 | { |
---|
| 99 | return is_imm( value ) == GFMARK; |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | bool |
---|
| 103 | CanonicalForm::inBaseDomain() const |
---|
| 104 | { |
---|
| 105 | if ( is_imm( value ) ) |
---|
[094eed] | 106 | return true; |
---|
[2dd068] | 107 | else |
---|
[094eed] | 108 | return value->inBaseDomain(); |
---|
[2dd068] | 109 | } |
---|
| 110 | |
---|
| 111 | bool |
---|
| 112 | CanonicalForm::inExtension() const |
---|
| 113 | { |
---|
| 114 | if ( is_imm( value ) ) |
---|
[094eed] | 115 | return false; |
---|
[2dd068] | 116 | else |
---|
[094eed] | 117 | return value->inExtension(); |
---|
[2dd068] | 118 | } |
---|
| 119 | |
---|
| 120 | bool |
---|
| 121 | CanonicalForm::inCoeffDomain() const |
---|
| 122 | { |
---|
| 123 | if ( is_imm( value ) ) |
---|
[094eed] | 124 | return true; |
---|
[2dd068] | 125 | else |
---|
[094eed] | 126 | return value->inCoeffDomain(); |
---|
[2dd068] | 127 | } |
---|
| 128 | |
---|
| 129 | bool |
---|
| 130 | CanonicalForm::inPolyDomain() const |
---|
| 131 | { |
---|
| 132 | if ( is_imm( value ) ) |
---|
[094eed] | 133 | return false; |
---|
[2dd068] | 134 | else |
---|
[094eed] | 135 | return value->inPolyDomain(); |
---|
[2dd068] | 136 | } |
---|
| 137 | |
---|
| 138 | bool |
---|
| 139 | CanonicalForm::inQuotDomain() const |
---|
| 140 | { |
---|
| 141 | if ( is_imm( value ) ) |
---|
[094eed] | 142 | return false; |
---|
[2dd068] | 143 | else |
---|
[094eed] | 144 | return value->inQuotDomain(); |
---|
[2dd068] | 145 | } |
---|
| 146 | |
---|
[b60ef7] | 147 | bool |
---|
| 148 | CanonicalForm::isFFinGF() const |
---|
| 149 | { |
---|
| 150 | return is_imm( value ) == GFMARK && gf_isff( imm2int( value ) ); |
---|
| 151 | } |
---|
| 152 | |
---|
| 153 | bool |
---|
| 154 | CanonicalForm::isUnivariate() const |
---|
| 155 | { |
---|
| 156 | if ( is_imm( value ) ) |
---|
[094eed] | 157 | return false; |
---|
[b60ef7] | 158 | else |
---|
[094eed] | 159 | return value->isUnivariate(); |
---|
[b60ef7] | 160 | } |
---|
[dad0bc5] | 161 | |
---|
| 162 | // is_homogeneous returns 1 iff f is homogeneous, 0 otherwise// |
---|
| 163 | bool |
---|
| 164 | CanonicalForm::isHomogeneous() const |
---|
| 165 | { |
---|
| 166 | if (this->isZero()) return true; |
---|
| 167 | else if (this->inCoeffDomain()) return true; |
---|
| 168 | else |
---|
| 169 | { |
---|
| 170 | #if 0 |
---|
| 171 | CFIterator i; |
---|
| 172 | int cdeg = -2, dummy; |
---|
| 173 | for ( i = *this; i.hasTerms(); i++ ) |
---|
| 174 | { |
---|
| 175 | if (!(i.coeff().isHomogeneous())) return false; |
---|
| 176 | if ( (dummy = totaldegree( i.coeff() ) + i.exp()) != cdeg ) |
---|
| 177 | { |
---|
| 178 | if (cdeg == -2) cdeg = dummy; |
---|
| 179 | else return false; |
---|
| 180 | } |
---|
| 181 | } |
---|
| 182 | return true; |
---|
| 183 | #else |
---|
| 184 | CFList termlist= get_Terms(*this); |
---|
| 185 | CFListIterator i; |
---|
| 186 | int deg= totaldegree(termlist.getFirst()); |
---|
| 187 | |
---|
| 188 | for ( i=termlist; i.hasItem(); i++ ) |
---|
| 189 | if ( totaldegree(i.getItem()) != deg ) return false; |
---|
| 190 | return true; |
---|
| 191 | #endif |
---|
| 192 | } |
---|
| 193 | } |
---|
| 194 | |
---|
[b60ef7] | 195 | //}}} |
---|
| 196 | |
---|
| 197 | //{{{ conversion functions |
---|
[8710ff0] | 198 | long |
---|
[2dd068] | 199 | CanonicalForm::intval() const |
---|
| 200 | { |
---|
| 201 | if ( is_imm( value ) ) |
---|
[094eed] | 202 | return imm_intval( value ); |
---|
[2dd068] | 203 | else |
---|
[094eed] | 204 | return value->intval(); |
---|
[2dd068] | 205 | } |
---|
| 206 | |
---|
| 207 | CanonicalForm |
---|
[b60ef7] | 208 | CanonicalForm::mapinto () const |
---|
| 209 | { |
---|
[184f44] | 210 | //ASSERT( is_imm( value ) || ! value->inExtension(), "cannot map into different Extension" ); |
---|
[b60ef7] | 211 | if ( is_imm( value ) ) |
---|
[094eed] | 212 | if ( getCharacteristic() == 0 ) |
---|
| 213 | if ( is_imm( value ) == FFMARK ) |
---|
| 214 | return CanonicalForm( int2imm( ff_symmetric( imm2int( value ) ) ) ); |
---|
| 215 | else if ( is_imm( value ) == GFMARK ) |
---|
| 216 | return CanonicalForm( int2imm( ff_symmetric( gf_gf2ff( imm2int( value ) ) ) ) ); |
---|
| 217 | else |
---|
| 218 | return *this; |
---|
| 219 | else if ( getGFDegree() == 1 ) |
---|
| 220 | return CanonicalForm( int2imm_p( ff_norm( imm2int( value ) ) ) ); |
---|
| 221 | else |
---|
| 222 | return CanonicalForm( int2imm_gf( gf_int2gf( imm2int( value ) ) ) ); |
---|
[b60ef7] | 223 | else if ( value->inBaseDomain() ) |
---|
[094eed] | 224 | if ( getCharacteristic() == 0 ) |
---|
[928fb6] | 225 | return *this; |
---|
[94a967] | 226 | else |
---|
| 227 | { |
---|
[094eed] | 228 | int val; |
---|
| 229 | if ( value->levelcoeff() == IntegerDomain ) |
---|
| 230 | val = value->intmod( ff_prime ); |
---|
| 231 | else if ( value->levelcoeff() == RationalDomain ) |
---|
| 232 | return num().mapinto() / den().mapinto(); |
---|
| 233 | else { |
---|
| 234 | ASSERT( 0, "illegal domain" ); |
---|
| 235 | return 0; |
---|
| 236 | } |
---|
| 237 | if ( getGFDegree() > 1 ) |
---|
| 238 | return CanonicalForm( int2imm_gf( gf_int2gf( val ) ) ); |
---|
| 239 | else |
---|
| 240 | return CanonicalForm( int2imm_p( val ) ); |
---|
| 241 | } |
---|
[94a967] | 242 | else |
---|
| 243 | { |
---|
[094eed] | 244 | Variable x = value->variable(); |
---|
| 245 | CanonicalForm result; |
---|
| 246 | for ( CFIterator i = *this; i.hasTerms(); i++ ) |
---|
[94a967] | 247 | result += (power( x, i.exp() ) * i.coeff().mapinto()); |
---|
[094eed] | 248 | return result; |
---|
[b60ef7] | 249 | } |
---|
| 250 | } |
---|
| 251 | //}}} |
---|
| 252 | |
---|
| 253 | //{{{ CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const |
---|
| 254 | //{{{ docu |
---|
| 255 | // |
---|
| 256 | // lc(), Lc(), LC() - leading coefficient functions. |
---|
| 257 | // |
---|
| 258 | // All methods return CO if CO is in a base domain. |
---|
| 259 | // |
---|
| 260 | // lc() returns the leading coefficient of CO with respect to |
---|
| 261 | // lexicographic ordering. Elements in an algebraic extension |
---|
| 262 | // are considered polynomials so lc() always returns a leading |
---|
| 263 | // coefficient in a base domain. This method is useful to get |
---|
| 264 | // the base domain over which CO is defined. |
---|
| 265 | // |
---|
| 266 | // Lc() returns the leading coefficient of CO with respect to |
---|
| 267 | // lexicographic ordering. In contrast to lc() elements in an |
---|
| 268 | // algebraic extension are considered coefficients so Lc() always |
---|
| 269 | // returns a leading coefficient in a coefficient domain. |
---|
[094eed] | 270 | // |
---|
[b60ef7] | 271 | // LC() returns the leading coefficient of CO where CO is |
---|
| 272 | // considered a univariate polynomial in its main variable. An |
---|
| 273 | // element of an algebraic extension is considered an univariate |
---|
| 274 | // polynomial, too. |
---|
| 275 | // |
---|
| 276 | // LC( v ) returns the leading coefficient of CO where CO is |
---|
| 277 | // considered an univariate polynomial in the polynomial variable |
---|
| 278 | // v. |
---|
| 279 | // Note: If v is less than the main variable of CO we have to |
---|
| 280 | // swap variables which may be quite expensive. |
---|
| 281 | // |
---|
| 282 | // Examples: |
---|
| 283 | // Let x < y be polynomial variables, a an algebraic variable. |
---|
| 284 | // |
---|
| 285 | // (3*a*x*y^2+y+x).lc() = 3 |
---|
| 286 | // (3*a*x*y^2+y+x).Lc() = 3*a |
---|
| 287 | // (3*a*x*y^2+y+x).LC() = 3*a*x |
---|
| 288 | // (3*a*x*y^2+y+x).LC( x ) = 3*a*y^2+1 |
---|
| 289 | // |
---|
| 290 | // (3*a^2+4*a).lc() = 3 |
---|
| 291 | // (3*a^2+4*a).Lc() = 3*a^2+4*a |
---|
| 292 | // (3*a^2+4*a).LC() = 3 |
---|
| 293 | // (3*a^2+4*a).LC( x ) = 3*a^2+4*a |
---|
| 294 | // |
---|
| 295 | // See also: InternalCF::lc(), InternalCF::Lc(), InternalCF::LC(), |
---|
| 296 | // InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), |
---|
| 297 | // ::lc(), ::Lc(), ::LC(), ::LC( v ) |
---|
| 298 | // |
---|
| 299 | //}}} |
---|
| 300 | CanonicalForm |
---|
| 301 | CanonicalForm::lc () const |
---|
[2dd068] | 302 | { |
---|
| 303 | if ( is_imm( value ) ) |
---|
[094eed] | 304 | return *this; |
---|
[2dd068] | 305 | else |
---|
[094eed] | 306 | return value->lc(); |
---|
[2dd068] | 307 | } |
---|
| 308 | |
---|
| 309 | CanonicalForm |
---|
[b60ef7] | 310 | CanonicalForm::Lc () const |
---|
[2dd068] | 311 | { |
---|
[b60ef7] | 312 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
[094eed] | 313 | return *this; |
---|
[b60ef7] | 314 | else |
---|
[094eed] | 315 | return value->Lc(); |
---|
[b60ef7] | 316 | } |
---|
| 317 | |
---|
| 318 | CanonicalForm |
---|
| 319 | CanonicalForm::LC () const |
---|
| 320 | { |
---|
| 321 | if ( is_imm( value ) ) |
---|
[094eed] | 322 | return *this; |
---|
[2dd068] | 323 | else |
---|
[094eed] | 324 | return value->LC(); |
---|
[2dd068] | 325 | } |
---|
| 326 | |
---|
| 327 | CanonicalForm |
---|
[b60ef7] | 328 | CanonicalForm::LC ( const Variable & v ) const |
---|
[2dd068] | 329 | { |
---|
[b60ef7] | 330 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
[094eed] | 331 | return *this; |
---|
[b60ef7] | 332 | |
---|
| 333 | Variable x = value->variable(); |
---|
| 334 | if ( v > x ) |
---|
[094eed] | 335 | return *this; |
---|
[b60ef7] | 336 | else if ( v == x ) |
---|
[094eed] | 337 | return value->LC(); |
---|
[2dd068] | 338 | else { |
---|
[094eed] | 339 | CanonicalForm f = swapvar( *this, v, x ); |
---|
| 340 | if ( f.mvar() == x ) |
---|
| 341 | return swapvar( f.value->LC(), v, x ); |
---|
| 342 | else |
---|
| 343 | // v did not occur in f |
---|
| 344 | return *this; |
---|
[2dd068] | 345 | } |
---|
| 346 | } |
---|
[b60ef7] | 347 | //}}} |
---|
[2dd068] | 348 | |
---|
[b60ef7] | 349 | //{{{ int CanonicalForm::degree (), degree ( v ) const |
---|
[78e2fd] | 350 | //{{{ docu |
---|
| 351 | // |
---|
[b60ef7] | 352 | // degree() - degree methods. |
---|
| 353 | // |
---|
| 354 | // Both methods returns -1 for the zero polynomial and 0 if |
---|
| 355 | // CO is in a base domain. |
---|
[78e2fd] | 356 | // |
---|
[b60ef7] | 357 | // degree() returns the degree of CO in its main variable. |
---|
| 358 | // Elements in an algebraic extension are considered polynomials. |
---|
[45911d] | 359 | // |
---|
[b60ef7] | 360 | // degree( v ) returns the degree of CO with respect to v. |
---|
| 361 | // Elements in an algebraic extension are considered polynomials, |
---|
| 362 | // and v may be algebraic. |
---|
| 363 | // |
---|
| 364 | // See also: InternalCf::degree(), InternalPoly::degree(), |
---|
| 365 | // ::degree(), ::degree( v ) |
---|
[78e2fd] | 366 | // |
---|
| 367 | //}}} |
---|
[2dd068] | 368 | int |
---|
| 369 | CanonicalForm::degree() const |
---|
| 370 | { |
---|
[45911d] | 371 | int what = is_imm( value ); |
---|
| 372 | if ( what ) |
---|
[094eed] | 373 | if ( what == FFMARK ) |
---|
| 374 | return imm_iszero_p( value ) ? -1 : 0; |
---|
| 375 | else if ( what == INTMARK ) |
---|
| 376 | return imm_iszero( value ) ? -1 : 0; |
---|
| 377 | else |
---|
| 378 | return imm_iszero_gf( value ) ? -1 : 0; |
---|
[2dd068] | 379 | else |
---|
[094eed] | 380 | return value->degree(); |
---|
[2dd068] | 381 | } |
---|
[78e2fd] | 382 | |
---|
[2dd068] | 383 | int |
---|
| 384 | CanonicalForm::degree( const Variable & v ) const |
---|
| 385 | { |
---|
[45911d] | 386 | int what = is_imm( value ); |
---|
[6db552] | 387 | #if 0 |
---|
[45911d] | 388 | if ( what ) |
---|
[094eed] | 389 | if ( what == FFMARK ) |
---|
| 390 | return imm_iszero_p( value ) ? -1 : 0; |
---|
| 391 | else if ( what == INTMARK ) |
---|
| 392 | return imm_iszero( value ) ? -1 : 0; |
---|
| 393 | else |
---|
| 394 | return imm_iszero_gf( value ) ? -1 : 0; |
---|
[45911d] | 395 | else if ( value->inBaseDomain() ) |
---|
[094eed] | 396 | return value->degree(); |
---|
[6db552] | 397 | #else |
---|
| 398 | switch(what) |
---|
| 399 | { |
---|
| 400 | case FFMARK: return imm_iszero_p( value ) ? -1 : 0; |
---|
| 401 | case INTMARK: return imm_iszero( value ) ? -1 : 0; |
---|
| 402 | case GFMARK: return imm_iszero_gf( value ) ? -1 : 0; |
---|
| 403 | case 0: if ( value->inBaseDomain() ) |
---|
| 404 | return value->degree(); |
---|
| 405 | break; |
---|
| 406 | } |
---|
| 407 | #endif |
---|
[45448d] | 408 | |
---|
[b60ef7] | 409 | Variable x = value->variable(); |
---|
[45448d] | 410 | if ( v == x ) |
---|
[094eed] | 411 | return value->degree(); |
---|
[45448d] | 412 | else if ( v > x ) |
---|
[094eed] | 413 | // relatively to v, f is in a coefficient ring |
---|
| 414 | return 0; |
---|
[2dd068] | 415 | else { |
---|
[094eed] | 416 | int coeffdeg, result = 0; |
---|
| 417 | // search for maximum of coefficient degree |
---|
| 418 | for ( CFIterator i = *this; i.hasTerms(); i++ ) { |
---|
| 419 | coeffdeg = i.coeff().degree( v ); |
---|
| 420 | if ( coeffdeg > result ) |
---|
| 421 | result = coeffdeg; |
---|
| 422 | } |
---|
| 423 | return result; |
---|
[2dd068] | 424 | } |
---|
| 425 | } |
---|
[78e2fd] | 426 | //}}} |
---|
[2dd068] | 427 | |
---|
[b60ef7] | 428 | //{{{ CanonicalForm CanonicalForm::tailcoeff (), int CanonicalForm::taildegree () const |
---|
| 429 | //{{{ docu |
---|
| 430 | // |
---|
[45911d] | 431 | // tailcoeff(), taildegree() - return least coefficient and |
---|
[b60ef7] | 432 | // degree, resp. |
---|
| 433 | // |
---|
| 434 | // tailcoeff() returns the coefficient of the term with the least |
---|
[45911d] | 435 | // degree in CO where CO is considered an univariate polynomial |
---|
| 436 | // in its main variable. Elements in an algebraic extension are |
---|
[b60ef7] | 437 | // considered coefficients. |
---|
| 438 | // |
---|
| 439 | // taildegree() returns -1 for the zero polynomial, 0 if CO is in |
---|
[45911d] | 440 | // a base domain, otherwise the least degree of CO where CO is |
---|
| 441 | // considered a univariate polynomial in its main variable. In |
---|
| 442 | // contrast to tailcoeff(), elements in an algebraic extension |
---|
| 443 | // are considered polynomials, not coefficients, and such may |
---|
| 444 | // have a taildegree larger than zero. |
---|
[b60ef7] | 445 | // |
---|
[3ace5b6] | 446 | // tailcoeff( v ) returns the tail coefficient of CO where CO is |
---|
| 447 | // considered an univariate polynomial in the polynomial variable |
---|
| 448 | // v. |
---|
| 449 | // Note: If v is less than the main variable of CO we have to |
---|
| 450 | // swap variables which may be quite expensive. |
---|
| 451 | // |
---|
[b60ef7] | 452 | // See also: InternalCF::tailcoeff(), InternalCF::tailcoeff(), |
---|
| 453 | // InternalPoly::tailcoeff(), InternalPoly::taildegree, |
---|
| 454 | // ::tailcoeff(), ::taildegree() |
---|
| 455 | // |
---|
| 456 | //}}} |
---|
| 457 | CanonicalForm |
---|
| 458 | CanonicalForm::tailcoeff () const |
---|
| 459 | { |
---|
| 460 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
[094eed] | 461 | return *this; |
---|
[b60ef7] | 462 | else |
---|
[094eed] | 463 | return value->tailcoeff(); |
---|
[b60ef7] | 464 | } |
---|
| 465 | |
---|
[3ace5b6] | 466 | CanonicalForm |
---|
| 467 | CanonicalForm::tailcoeff (const Variable& v) const |
---|
| 468 | { |
---|
| 469 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
| 470 | return *this; |
---|
| 471 | |
---|
| 472 | Variable x = value->variable(); |
---|
| 473 | if ( v > x ) |
---|
| 474 | return *this; |
---|
| 475 | else if ( v == x ) |
---|
| 476 | return value->tailcoeff(); |
---|
| 477 | else { |
---|
| 478 | CanonicalForm f = swapvar( *this, v, x ); |
---|
| 479 | if ( f.mvar() == x ) |
---|
| 480 | return swapvar( f.value->tailcoeff(), v, x ); |
---|
| 481 | else |
---|
| 482 | // v did not occur in f |
---|
| 483 | return *this; |
---|
| 484 | } |
---|
| 485 | } |
---|
| 486 | |
---|
[2dd068] | 487 | int |
---|
[b60ef7] | 488 | CanonicalForm::taildegree () const |
---|
[2dd068] | 489 | { |
---|
[45911d] | 490 | int what = is_imm( value ); |
---|
| 491 | if ( what ) |
---|
[094eed] | 492 | if ( what == FFMARK ) |
---|
| 493 | return imm_iszero_p( value ) ? -1 : 0; |
---|
| 494 | else if ( what == INTMARK ) |
---|
| 495 | return imm_iszero( value ) ? -1 : 0; |
---|
| 496 | else |
---|
| 497 | return imm_iszero_gf( value ) ? -1 : 0; |
---|
[2dd068] | 498 | else |
---|
[094eed] | 499 | return value->taildegree(); |
---|
[2dd068] | 500 | } |
---|
[b60ef7] | 501 | //}}} |
---|
[2dd068] | 502 | |
---|
[b60ef7] | 503 | //{{{ int CanonicalForm::level (), Variable CanonicalForm::mvar () const |
---|
| 504 | //{{{ docu |
---|
| 505 | // |
---|
| 506 | // level(), mvar() - return level and main variable of CO. |
---|
| 507 | // |
---|
[45911d] | 508 | // level() returns the level of CO. For a list of the levels and |
---|
| 509 | // their meanings, see cf_defs.h. |
---|
[b60ef7] | 510 | // |
---|
| 511 | // mvar() returns the main variable of CO or Variable() if CO is |
---|
| 512 | // in a base domain. |
---|
| 513 | // |
---|
| 514 | // See also: InternalCF::level(), InternalCF::variable(), |
---|
| 515 | // InternalPoly::level(), InternalPoly::variable(), ::level(), |
---|
| 516 | // ::mvar() |
---|
[094eed] | 517 | // |
---|
[b60ef7] | 518 | //}}} |
---|
[2dd068] | 519 | int |
---|
[b60ef7] | 520 | CanonicalForm::level () const |
---|
[2dd068] | 521 | { |
---|
| 522 | if ( is_imm( value ) ) |
---|
[094eed] | 523 | return LEVELBASE; |
---|
[2dd068] | 524 | else |
---|
[094eed] | 525 | return value->level(); |
---|
[2dd068] | 526 | } |
---|
| 527 | |
---|
| 528 | Variable |
---|
[b60ef7] | 529 | CanonicalForm::mvar () const |
---|
[2dd068] | 530 | { |
---|
[45911d] | 531 | if ( is_imm( value ) ) |
---|
[094eed] | 532 | return Variable(); |
---|
[2dd068] | 533 | else |
---|
[094eed] | 534 | return value->variable(); |
---|
[2dd068] | 535 | } |
---|
[b60ef7] | 536 | //}}} |
---|
[2dd068] | 537 | |
---|
[b60ef7] | 538 | //{{{ CanonicalForm CanonicalForm::num (), den () const |
---|
| 539 | //{{{ docu |
---|
| 540 | // |
---|
| 541 | // num(), den() - return numinator and denominator of CO. |
---|
| 542 | // |
---|
| 543 | // num() returns the numinator of CO if CO is a rational number, |
---|
| 544 | // CO itself otherwise. |
---|
| 545 | // |
---|
| 546 | // den() returns the denominator of CO if CO is a rational |
---|
| 547 | // number, 1 (from the current domain!) otherwise. |
---|
| 548 | // |
---|
| 549 | // See also: InternalCF::num(), InternalCF::den(), |
---|
| 550 | // InternalRational::num(), InternalRational::den(), ::num(), |
---|
| 551 | // ::den() |
---|
| 552 | // |
---|
| 553 | //}}} |
---|
[2dd068] | 554 | CanonicalForm |
---|
[b60ef7] | 555 | CanonicalForm::num () const |
---|
[2dd068] | 556 | { |
---|
| 557 | if ( is_imm( value ) ) |
---|
[094eed] | 558 | return *this; |
---|
[2dd068] | 559 | else |
---|
[094eed] | 560 | return CanonicalForm( value->num() ); |
---|
[2dd068] | 561 | } |
---|
| 562 | |
---|
| 563 | CanonicalForm |
---|
[b60ef7] | 564 | CanonicalForm::den () const |
---|
[2dd068] | 565 | { |
---|
| 566 | if ( is_imm( value ) ) |
---|
[094eed] | 567 | return CanonicalForm( 1 ); |
---|
[2dd068] | 568 | else |
---|
[094eed] | 569 | return CanonicalForm( value->den() ); |
---|
[2dd068] | 570 | } |
---|
[b60ef7] | 571 | //}}} |
---|
[2dd068] | 572 | |
---|
[b60ef7] | 573 | //{{{ assignment operators |
---|
[45911d] | 574 | CanonicalForm & |
---|
[b60ef7] | 575 | CanonicalForm::operator += ( const CanonicalForm & cf ) |
---|
[2dd068] | 576 | { |
---|
[b60ef7] | 577 | int what = is_imm( value ); |
---|
| 578 | if ( what ) { |
---|
[094eed] | 579 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 580 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 581 | value = imm_add_p( value, cf.value ); |
---|
| 582 | else if ( what == GFMARK ) |
---|
| 583 | value = imm_add_gf( value, cf.value ); |
---|
| 584 | else if ( what ) |
---|
| 585 | value = imm_add( value, cf.value ); |
---|
| 586 | else { |
---|
| 587 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 588 | value = dummy->addcoeff( value ); |
---|
| 589 | } |
---|
[b60ef7] | 590 | } |
---|
| 591 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 592 | value = value->addcoeff( cf.value ); |
---|
[b60ef7] | 593 | else if ( value->level() == cf.value->level() ) { |
---|
[094eed] | 594 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 595 | value = value->addsame( cf.value ); |
---|
| 596 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 597 | value = value->addcoeff( cf.value ); |
---|
| 598 | else { |
---|
| 599 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 600 | dummy = dummy->addcoeff( value ); |
---|
| 601 | if ( value->deleteObject() ) delete value; |
---|
| 602 | value = dummy; |
---|
| 603 | } |
---|
[b60ef7] | 604 | } |
---|
| 605 | else if ( level() > cf.level() ) |
---|
[094eed] | 606 | value = value->addcoeff( cf.value ); |
---|
[2dd068] | 607 | else { |
---|
[094eed] | 608 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 609 | dummy = dummy->addcoeff( value ); |
---|
| 610 | if ( value->deleteObject() ) delete value; |
---|
| 611 | value = dummy; |
---|
[2dd068] | 612 | } |
---|
[b60ef7] | 613 | return *this; |
---|
[2dd068] | 614 | } |
---|
| 615 | |
---|
[45911d] | 616 | CanonicalForm & |
---|
[2dd068] | 617 | CanonicalForm::operator -= ( const CanonicalForm & cf ) |
---|
| 618 | { |
---|
| 619 | int what = is_imm( value ); |
---|
| 620 | if ( what ) { |
---|
[094eed] | 621 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 622 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 623 | value = imm_sub_p( value, cf.value ); |
---|
| 624 | else if ( what == GFMARK ) |
---|
| 625 | value = imm_sub_gf( value, cf.value ); |
---|
| 626 | else if ( what ) |
---|
| 627 | value = imm_sub( value, cf.value ); |
---|
| 628 | else { |
---|
| 629 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 630 | value = dummy->subcoeff( value, true ); |
---|
| 631 | } |
---|
[2dd068] | 632 | } |
---|
| 633 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 634 | value = value->subcoeff( cf.value, false ); |
---|
[2dd068] | 635 | else if ( value->level() == cf.value->level() ) { |
---|
[094eed] | 636 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 637 | value = value->subsame( cf.value ); |
---|
| 638 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 639 | value = value->subcoeff( cf.value, false ); |
---|
| 640 | else { |
---|
| 641 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 642 | dummy = dummy->subcoeff( value, true ); |
---|
| 643 | if ( value->deleteObject() ) delete value; |
---|
| 644 | value = dummy; |
---|
| 645 | } |
---|
[2dd068] | 646 | } |
---|
| 647 | else if ( level() > cf.level() ) |
---|
[094eed] | 648 | value = value->subcoeff( cf.value, false ); |
---|
[2dd068] | 649 | else { |
---|
[094eed] | 650 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 651 | dummy = dummy->subcoeff( value, true ); |
---|
| 652 | if ( value->deleteObject() ) delete value; |
---|
| 653 | value = dummy; |
---|
[2dd068] | 654 | } |
---|
| 655 | return *this; |
---|
| 656 | } |
---|
| 657 | |
---|
[45911d] | 658 | CanonicalForm & |
---|
[2dd068] | 659 | CanonicalForm::operator *= ( const CanonicalForm & cf ) |
---|
| 660 | { |
---|
| 661 | int what = is_imm( value ); |
---|
| 662 | if ( what ) { |
---|
[094eed] | 663 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 664 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 665 | value = imm_mul_p( value, cf.value ); |
---|
| 666 | else if ( what == GFMARK ) |
---|
| 667 | value = imm_mul_gf( value, cf.value ); |
---|
| 668 | else if ( what ) |
---|
| 669 | value = imm_mul( value, cf.value ); |
---|
| 670 | else { |
---|
| 671 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 672 | value = dummy->mulcoeff( value ); |
---|
| 673 | } |
---|
[2dd068] | 674 | } |
---|
| 675 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 676 | value = value->mulcoeff( cf.value ); |
---|
[2dd068] | 677 | else if ( value->level() == cf.value->level() ) { |
---|
[31bb7a] | 678 | #if (HAVE_NTL && HAVE_FLINT && __FLINT_VERSION_MINOR >= 4) |
---|
[c22249] | 679 | if (value->levelcoeff() == cf.value->levelcoeff() && cf.isUnivariate() && (*this).isUnivariate()) |
---|
| 680 | { |
---|
| 681 | if (value->level() < 0 || CFFactory::gettype() == GaloisFieldDomain || (size (cf) <= 10 || size (*this) <= 10) ) |
---|
| 682 | value = value->mulsame( cf.value ); |
---|
| 683 | else |
---|
| 684 | *this= mulNTL (*this, cf); |
---|
| 685 | } |
---|
| 686 | else if (value->levelcoeff() == cf.value->levelcoeff() && (!cf.isUnivariate() || !(*this).isUnivariate())) |
---|
[094eed] | 687 | value = value->mulsame( cf.value ); |
---|
[31bb7a] | 688 | #else |
---|
| 689 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 690 | value = value->mulsame( cf.value ); |
---|
| 691 | #endif |
---|
[094eed] | 692 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 693 | value = value->mulcoeff( cf.value ); |
---|
| 694 | else { |
---|
| 695 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 696 | dummy = dummy->mulcoeff( value ); |
---|
| 697 | if ( value->deleteObject() ) delete value; |
---|
| 698 | value = dummy; |
---|
| 699 | } |
---|
[2dd068] | 700 | } |
---|
| 701 | else if ( level() > cf.level() ) |
---|
[094eed] | 702 | value = value->mulcoeff( cf.value ); |
---|
[2dd068] | 703 | else { |
---|
[094eed] | 704 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 705 | dummy = dummy->mulcoeff( value ); |
---|
| 706 | if ( value->deleteObject() ) delete value; |
---|
| 707 | value = dummy; |
---|
[2dd068] | 708 | } |
---|
| 709 | return *this; |
---|
| 710 | } |
---|
| 711 | |
---|
[45911d] | 712 | CanonicalForm & |
---|
[2dd068] | 713 | CanonicalForm::operator /= ( const CanonicalForm & cf ) |
---|
| 714 | { |
---|
| 715 | int what = is_imm( value ); |
---|
| 716 | if ( what ) { |
---|
[094eed] | 717 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 718 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 719 | value = imm_div_p( value, cf.value ); |
---|
| 720 | else if ( what == GFMARK ) |
---|
| 721 | value = imm_div_gf( value, cf.value ); |
---|
| 722 | else if ( what ) |
---|
| 723 | value = imm_divrat( value, cf.value ); |
---|
| 724 | else { |
---|
| 725 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 726 | value = dummy->dividecoeff( value, true ); |
---|
| 727 | } |
---|
[2dd068] | 728 | } |
---|
| 729 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 730 | value = value->dividecoeff( cf.value, false ); |
---|
[2dd068] | 731 | else if ( value->level() == cf.value->level() ) { |
---|
[31bb7a] | 732 | #if (HAVE_NTL && HAVE_FLINT && __FLINT_VERSION_MINOR >= 4) |
---|
| 733 | if ( value->levelcoeff() == cf.value->levelcoeff() && (*this).isUnivariate() && cf.isUnivariate()) |
---|
| 734 | { |
---|
| 735 | if (value->level() < 0 || CFFactory::gettype() == GaloisFieldDomain) |
---|
| 736 | value = value->dividesame( cf.value ); |
---|
| 737 | else |
---|
| 738 | *this= divNTL (*this, cf); |
---|
| 739 | } |
---|
| 740 | else if (value->levelcoeff() == cf.value->levelcoeff() && (!cf.isUnivariate() || !(*this).isUnivariate())) |
---|
[094eed] | 741 | value = value->dividesame( cf.value ); |
---|
[31bb7a] | 742 | #else |
---|
| 743 | if (value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 744 | value = value->dividesame( cf.value ); |
---|
| 745 | #endif |
---|
[094eed] | 746 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 747 | value = value->dividecoeff( cf.value, false ); |
---|
| 748 | else { |
---|
| 749 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 750 | dummy = dummy->dividecoeff( value, true ); |
---|
| 751 | if ( value->deleteObject() ) delete value; |
---|
| 752 | value = dummy; |
---|
| 753 | } |
---|
[2dd068] | 754 | } |
---|
| 755 | else if ( level() > cf.level() ) |
---|
[094eed] | 756 | value = value->dividecoeff( cf.value, false ); |
---|
[2dd068] | 757 | else { |
---|
[094eed] | 758 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 759 | dummy = dummy->dividecoeff( value, true ); |
---|
| 760 | if ( value->deleteObject() ) delete value; |
---|
| 761 | value = dummy; |
---|
[2dd068] | 762 | } |
---|
| 763 | return *this; |
---|
| 764 | } |
---|
| 765 | |
---|
[45911d] | 766 | CanonicalForm & |
---|
[2dd068] | 767 | CanonicalForm::div ( const CanonicalForm & cf ) |
---|
| 768 | { |
---|
| 769 | int what = is_imm( value ); |
---|
| 770 | if ( what ) { |
---|
[094eed] | 771 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 772 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 773 | value = imm_div_p( value, cf.value ); |
---|
| 774 | else if ( what == GFMARK ) |
---|
| 775 | value = imm_div_gf( value, cf.value ); |
---|
| 776 | else if ( what ) |
---|
| 777 | value = imm_div( value, cf.value ); |
---|
| 778 | else { |
---|
| 779 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 780 | value = dummy->divcoeff( value, true ); |
---|
| 781 | } |
---|
[2dd068] | 782 | } |
---|
| 783 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 784 | value = value->divcoeff( cf.value, false ); |
---|
[2dd068] | 785 | else if ( value->level() == cf.value->level() ) { |
---|
[094eed] | 786 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 787 | value = value->divsame( cf.value ); |
---|
| 788 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 789 | value = value->divcoeff( cf.value, false ); |
---|
| 790 | else { |
---|
| 791 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 792 | dummy = dummy->divcoeff( value, true ); |
---|
| 793 | if ( value->deleteObject() ) delete value; |
---|
| 794 | value = dummy; |
---|
| 795 | } |
---|
[2dd068] | 796 | } |
---|
| 797 | else if ( level() > cf.level() ) |
---|
[094eed] | 798 | value = value->divcoeff( cf.value, false ); |
---|
[2dd068] | 799 | else { |
---|
[094eed] | 800 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 801 | dummy = dummy->divcoeff( value, true ); |
---|
| 802 | if ( value->deleteObject() ) delete value; |
---|
| 803 | value = dummy; |
---|
[2dd068] | 804 | } |
---|
| 805 | return *this; |
---|
| 806 | } |
---|
| 807 | |
---|
[e28e6d] | 808 | //same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible |
---|
| 809 | CanonicalForm & |
---|
| 810 | CanonicalForm::tryDiv ( const CanonicalForm & cf, const CanonicalForm& M, bool& fail ) |
---|
| 811 | { |
---|
| 812 | ASSERT (getCharacteristic() > 0, "expected positive characteristic"); |
---|
| 813 | ASSERT (!getReduce (M.mvar()), "do not reduce modulo M"); |
---|
| 814 | fail= false; |
---|
| 815 | int what = is_imm( value ); |
---|
| 816 | if ( what ) { |
---|
| 817 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 818 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 819 | value = imm_div_p( value, cf.value ); |
---|
| 820 | else if ( what == GFMARK ) |
---|
| 821 | value = imm_div_gf( value, cf.value ); |
---|
| 822 | else { |
---|
| 823 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 824 | value = dummy->divcoeff( value, true ); |
---|
| 825 | } |
---|
| 826 | } |
---|
| 827 | else if ( is_imm( cf.value ) ) |
---|
| 828 | value = value->tryDivcoeff (cf.value, false, M, fail); |
---|
| 829 | else if ( value->level() == cf.value->level() ) { |
---|
| 830 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 831 | value = value->tryDivsame( cf.value, M, fail ); |
---|
| 832 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 833 | value = value->tryDivcoeff( cf.value, false, M, fail ); |
---|
| 834 | else { |
---|
| 835 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 836 | dummy = dummy->tryDivcoeff( value, true, M, fail ); |
---|
| 837 | if ( value->deleteObject() ) delete value; |
---|
| 838 | value = dummy; |
---|
| 839 | } |
---|
| 840 | } |
---|
| 841 | else if ( level() > cf.level() ) |
---|
| 842 | value = value->tryDivcoeff( cf.value, false, M, fail ); |
---|
| 843 | else { |
---|
| 844 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 845 | dummy = dummy->tryDivcoeff( value, true, M, fail ); |
---|
| 846 | if ( value->deleteObject() ) delete value; |
---|
| 847 | value = dummy; |
---|
| 848 | } |
---|
| 849 | return *this; |
---|
| 850 | } |
---|
| 851 | |
---|
[45911d] | 852 | CanonicalForm & |
---|
| 853 | CanonicalForm::operator %= ( const CanonicalForm & cf ) |
---|
[2dd068] | 854 | { |
---|
| 855 | int what = is_imm( value ); |
---|
| 856 | if ( what ) { |
---|
[094eed] | 857 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 858 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 859 | value = imm_mod_p( value, cf.value ); |
---|
| 860 | else if ( what == GFMARK ) |
---|
| 861 | value = imm_mod_gf( value, cf.value ); |
---|
| 862 | else if ( what ) |
---|
| 863 | value = imm_mod( value, cf.value ); |
---|
| 864 | else { |
---|
| 865 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 866 | value = dummy->modulocoeff( value, true ); |
---|
| 867 | } |
---|
[2dd068] | 868 | } |
---|
| 869 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 870 | value = value->modulocoeff( cf.value, false ); |
---|
[2dd068] | 871 | else if ( value->level() == cf.value->level() ) { |
---|
[094eed] | 872 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 873 | value = value->modulosame( cf.value ); |
---|
| 874 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 875 | value = value->modulocoeff( cf.value, false ); |
---|
| 876 | else { |
---|
| 877 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 878 | dummy = dummy->modulocoeff( value, true ); |
---|
| 879 | if ( value->deleteObject() ) delete value; |
---|
| 880 | value = dummy; |
---|
| 881 | } |
---|
[2dd068] | 882 | } |
---|
| 883 | else if ( level() > cf.level() ) |
---|
[094eed] | 884 | value = value->modulocoeff( cf.value, false ); |
---|
[2dd068] | 885 | else { |
---|
[094eed] | 886 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 887 | dummy = dummy->modulocoeff( value, true ); |
---|
| 888 | if ( value->deleteObject() ) delete value; |
---|
| 889 | value = dummy; |
---|
[2dd068] | 890 | } |
---|
| 891 | return *this; |
---|
| 892 | } |
---|
| 893 | |
---|
[45911d] | 894 | CanonicalForm & |
---|
| 895 | CanonicalForm::mod ( const CanonicalForm & cf ) |
---|
[2dd068] | 896 | { |
---|
| 897 | int what = is_imm( value ); |
---|
| 898 | if ( what ) { |
---|
[094eed] | 899 | ASSERT ( ! is_imm( cf.value ) || (what==is_imm( cf.value )), "illegal base coefficients" ); |
---|
| 900 | if ( (what = is_imm( cf.value )) == FFMARK ) |
---|
| 901 | value = imm_mod_p( value, cf.value ); |
---|
| 902 | else if ( what == GFMARK ) |
---|
| 903 | value = imm_mod_gf( value, cf.value ); |
---|
| 904 | else if ( what ) |
---|
| 905 | value = imm_mod( value, cf.value ); |
---|
| 906 | else { |
---|
| 907 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 908 | value = dummy->modcoeff( value, true ); |
---|
| 909 | } |
---|
[2dd068] | 910 | } |
---|
| 911 | else if ( is_imm( cf.value ) ) |
---|
[094eed] | 912 | value = value->modcoeff( cf.value, false ); |
---|
[2dd068] | 913 | else if ( value->level() == cf.value->level() ) { |
---|
[094eed] | 914 | if ( value->levelcoeff() == cf.value->levelcoeff() ) |
---|
| 915 | value = value->modsame( cf.value ); |
---|
| 916 | else if ( value->levelcoeff() > cf.value->levelcoeff() ) |
---|
| 917 | value = value->modcoeff( cf.value, false ); |
---|
| 918 | else { |
---|
| 919 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 920 | dummy = dummy->modcoeff( value, true ); |
---|
| 921 | if ( value->deleteObject() ) delete value; |
---|
| 922 | value = dummy; |
---|
| 923 | } |
---|
[2dd068] | 924 | } |
---|
| 925 | else if ( level() > cf.level() ) |
---|
[094eed] | 926 | value = value->modcoeff( cf.value, false ); |
---|
[2dd068] | 927 | else { |
---|
[094eed] | 928 | InternalCF * dummy = cf.value->copyObject(); |
---|
| 929 | dummy = dummy->modcoeff( value, true ); |
---|
| 930 | if ( value->deleteObject() ) delete value; |
---|
| 931 | value = dummy; |
---|
[2dd068] | 932 | } |
---|
| 933 | return *this; |
---|
| 934 | } |
---|
[ba02b1] | 935 | |
---|
| 936 | void |
---|
| 937 | divrem ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r ) |
---|
| 938 | { |
---|
| 939 | InternalCF * qq = 0, * rr = 0; |
---|
| 940 | int what = is_imm( f.value ); |
---|
| 941 | if ( what ) |
---|
[094eed] | 942 | if ( is_imm( g.value ) ) { |
---|
| 943 | if ( what == FFMARK ) |
---|
| 944 | imm_divrem_p( f.value, g.value, qq, rr ); |
---|
| 945 | else if ( what == GFMARK ) |
---|
| 946 | imm_divrem_gf( f.value, g.value, qq, rr ); |
---|
| 947 | else |
---|
| 948 | imm_divrem( f.value, g.value, qq, rr ); |
---|
| 949 | } |
---|
| 950 | else |
---|
| 951 | g.value->divremcoeff( f.value, qq, rr, true ); |
---|
[ba02b1] | 952 | else if ( (what=is_imm( g.value )) ) |
---|
[094eed] | 953 | f.value->divremcoeff( g.value, qq, rr, false ); |
---|
[ba02b1] | 954 | else if ( f.value->level() == g.value->level() ) |
---|
[094eed] | 955 | if ( f.value->levelcoeff() == g.value->levelcoeff() ) |
---|
| 956 | f.value->divremsame( g.value, qq, rr ); |
---|
| 957 | else if ( f.value->levelcoeff() > g.value->levelcoeff() ) |
---|
| 958 | f.value->divremcoeff( g.value, qq, rr, false ); |
---|
| 959 | else |
---|
| 960 | g.value->divremcoeff( f.value, qq, rr, true ); |
---|
[ba02b1] | 961 | else if ( f.value->level() > g.value->level() ) |
---|
[094eed] | 962 | f.value->divremcoeff( g.value, qq, rr, false ); |
---|
[ba02b1] | 963 | else |
---|
[094eed] | 964 | g.value->divremcoeff( f.value, qq, rr, true ); |
---|
[ba02b1] | 965 | ASSERT( qq != 0 && rr != 0, "error in divrem" ); |
---|
| 966 | q = CanonicalForm( qq ); |
---|
| 967 | r = CanonicalForm( rr ); |
---|
| 968 | } |
---|
| 969 | |
---|
| 970 | bool |
---|
| 971 | divremt ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r ) |
---|
| 972 | { |
---|
| 973 | InternalCF * qq = 0, * rr = 0; |
---|
| 974 | int what = is_imm( f.value ); |
---|
| 975 | bool result = true; |
---|
| 976 | if ( what ) |
---|
[094eed] | 977 | if ( is_imm( g.value ) ) { |
---|
| 978 | if ( what == FFMARK ) |
---|
| 979 | imm_divrem_p( f.value, g.value, qq, rr ); |
---|
| 980 | else if ( what == GFMARK ) |
---|
| 981 | imm_divrem_gf( f.value, g.value, qq, rr ); |
---|
| 982 | else |
---|
| 983 | imm_divrem( f.value, g.value, qq, rr ); |
---|
| 984 | } |
---|
| 985 | else |
---|
| 986 | result = g.value->divremcoefft( f.value, qq, rr, true ); |
---|
[ba02b1] | 987 | else if ( (what=is_imm( g.value )) ) |
---|
[094eed] | 988 | result = f.value->divremcoefft( g.value, qq, rr, false ); |
---|
[ba02b1] | 989 | else if ( f.value->level() == g.value->level() ) |
---|
[094eed] | 990 | if ( f.value->levelcoeff() == g.value->levelcoeff() ) |
---|
| 991 | result = f.value->divremsamet( g.value, qq, rr ); |
---|
| 992 | else if ( f.value->levelcoeff() > g.value->levelcoeff() ) |
---|
| 993 | result = f.value->divremcoefft( g.value, qq, rr, false ); |
---|
| 994 | else |
---|
| 995 | result = g.value->divremcoefft( f.value, qq, rr, true ); |
---|
[ba02b1] | 996 | else if ( f.value->level() > g.value->level() ) |
---|
[094eed] | 997 | result = f.value->divremcoefft( g.value, qq, rr, false ); |
---|
[ba02b1] | 998 | else |
---|
[094eed] | 999 | result = g.value->divremcoefft( f.value, qq, rr, true ); |
---|
[ba02b1] | 1000 | if ( result ) { |
---|
[094eed] | 1001 | ASSERT( qq != 0 && rr != 0, "error in divrem" ); |
---|
| 1002 | q = CanonicalForm( qq ); |
---|
| 1003 | r = CanonicalForm( rr ); |
---|
[ba02b1] | 1004 | } |
---|
| 1005 | else { |
---|
[094eed] | 1006 | q = 0; r = 0; |
---|
[ba02b1] | 1007 | } |
---|
| 1008 | return result; |
---|
| 1009 | } |
---|
[e28e6d] | 1010 | |
---|
| 1011 | //same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible |
---|
| 1012 | bool |
---|
| 1013 | tryDivremt ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const CanonicalForm& M, bool& fail ) |
---|
| 1014 | { |
---|
| 1015 | ASSERT (getCharacteristic() > 0, "expected positive characteristic"); |
---|
| 1016 | ASSERT (!getReduce (M.mvar()), "do not reduce modulo M"); |
---|
| 1017 | fail= false; |
---|
| 1018 | InternalCF * qq = 0, * rr = 0; |
---|
| 1019 | int what = is_imm( f.value ); |
---|
| 1020 | bool result = true; |
---|
| 1021 | if ( what ) |
---|
| 1022 | if ( is_imm( g.value ) ) { |
---|
| 1023 | if ( what == FFMARK ) |
---|
| 1024 | imm_divrem_p( f.value, g.value, qq, rr ); |
---|
| 1025 | else if ( what == GFMARK ) |
---|
| 1026 | imm_divrem_gf( f.value, g.value, qq, rr ); |
---|
| 1027 | } |
---|
| 1028 | else |
---|
| 1029 | result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail ); |
---|
| 1030 | else if ( (what=is_imm( g.value )) ) |
---|
| 1031 | result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail ); |
---|
| 1032 | else if ( f.value->level() == g.value->level() ) |
---|
| 1033 | if ( f.value->levelcoeff() == g.value->levelcoeff() ) |
---|
| 1034 | result = f.value->tryDivremsamet( g.value, qq, rr, M, fail ); |
---|
| 1035 | else if ( f.value->levelcoeff() > g.value->levelcoeff() ) |
---|
| 1036 | result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail ); |
---|
| 1037 | else |
---|
| 1038 | result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail ); |
---|
| 1039 | else if ( f.value->level() > g.value->level() ) |
---|
| 1040 | result = f.value->tryDivremcoefft( g.value, qq, rr, false, M, fail ); |
---|
| 1041 | else |
---|
| 1042 | result = g.value->tryDivremcoefft( f.value, qq, rr, true, M, fail ); |
---|
| 1043 | if (fail) |
---|
| 1044 | { |
---|
| 1045 | q= 0; |
---|
| 1046 | r= 0; |
---|
| 1047 | return false; |
---|
| 1048 | } |
---|
| 1049 | if ( result ) { |
---|
| 1050 | ASSERT( qq != 0 && rr != 0, "error in divrem" ); |
---|
| 1051 | q = CanonicalForm( qq ); |
---|
| 1052 | r = CanonicalForm( rr ); |
---|
| 1053 | q= reduce (q, M); |
---|
| 1054 | r= reduce (r, M); |
---|
| 1055 | } |
---|
| 1056 | else { |
---|
| 1057 | q = 0; r = 0; |
---|
| 1058 | } |
---|
| 1059 | return result; |
---|
| 1060 | } |
---|
| 1061 | |
---|
[b60ef7] | 1062 | //}}} |
---|
[2dd068] | 1063 | |
---|
[45911d] | 1064 | //{{{ CanonicalForm CanonicalForm::operator () ( f ), operator () ( f, v ) const |
---|
| 1065 | //{{{ docu |
---|
| 1066 | // |
---|
| 1067 | // operator ()() - evaluation operator. |
---|
| 1068 | // |
---|
| 1069 | // Both operators return CO if CO is in a base domain. |
---|
| 1070 | // |
---|
| 1071 | // operator () ( f ) returns CO with f inserted for the main |
---|
| 1072 | // variable. Elements in an algebraic extension are considered |
---|
| 1073 | // polynomials. |
---|
| 1074 | // |
---|
| 1075 | // operator () ( f, v ) returns CO with f inserted for v. |
---|
| 1076 | // Elements in an algebraic extension are considered polynomials |
---|
| 1077 | // and v may be an algebraic variable. |
---|
| 1078 | // |
---|
| 1079 | //}}} |
---|
| 1080 | CanonicalForm |
---|
| 1081 | CanonicalForm::operator () ( const CanonicalForm & f ) const |
---|
| 1082 | { |
---|
| 1083 | if ( is_imm( value ) || value->inBaseDomain() ) |
---|
[094eed] | 1084 | return *this; |
---|
[45911d] | 1085 | else { |
---|
[9c3bc93] | 1086 | #if 0 |
---|
[094eed] | 1087 | CFIterator i = *this; |
---|
| 1088 | int lastExp = i.exp(); |
---|
| 1089 | CanonicalForm result = i.coeff(); |
---|
| 1090 | i++; |
---|
| 1091 | while ( i.hasTerms() ) { |
---|
| 1092 | if ( (lastExp - i.exp()) == 1 ) |
---|
| 1093 | result *= f; |
---|
| 1094 | else |
---|
| 1095 | result *= power( f, lastExp - i.exp() ); |
---|
| 1096 | result += i.coeff(); |
---|
| 1097 | lastExp = i.exp(); |
---|
| 1098 | i++; |
---|
| 1099 | } |
---|
| 1100 | if ( lastExp != 0 ) |
---|
| 1101 | result *= power( f, lastExp ); |
---|
[9c3bc93] | 1102 | #else |
---|
[094eed] | 1103 | CFIterator i = *this; |
---|
| 1104 | int lastExp = i.exp(); |
---|
| 1105 | CanonicalForm result = i.coeff(); |
---|
| 1106 | i++; |
---|
| 1107 | while ( i.hasTerms() ) |
---|
[9c3bc93] | 1108 | { |
---|
| 1109 | int i_exp=i.exp(); |
---|
[094eed] | 1110 | if ( (lastExp - i_exp /* i.exp()*/) == 1 ) |
---|
| 1111 | result *= f; |
---|
| 1112 | else |
---|
| 1113 | result *= power( f, lastExp - i_exp /*i.exp()*/ ); |
---|
| 1114 | result += i.coeff(); |
---|
| 1115 | lastExp = i_exp /*i.exp()*/; |
---|
| 1116 | i++; |
---|
| 1117 | } |
---|
| 1118 | if ( lastExp != 0 ) |
---|
| 1119 | result *= power( f, lastExp ); |
---|
[9c3bc93] | 1120 | #endif |
---|
[094eed] | 1121 | return result; |
---|
[45911d] | 1122 | } |
---|
| 1123 | } |
---|
[b60ef7] | 1124 | |
---|
[45911d] | 1125 | CanonicalForm |
---|
| 1126 | CanonicalForm::operator () ( const CanonicalForm & f, const Variable & v ) const |
---|
| 1127 | { |
---|
| 1128 | if ( is_imm( value ) || value->inBaseDomain() ) |
---|
[094eed] | 1129 | return *this; |
---|
[45911d] | 1130 | |
---|
| 1131 | Variable x = value->variable(); |
---|
| 1132 | if ( v > x ) |
---|
[094eed] | 1133 | return *this; |
---|
[45911d] | 1134 | else if ( v == x ) |
---|
[094eed] | 1135 | return (*this)( f ); |
---|
[45911d] | 1136 | else { |
---|
[094eed] | 1137 | // v is less than main variable of f |
---|
| 1138 | CanonicalForm result = 0; |
---|
| 1139 | for ( CFIterator i = *this; i.hasTerms(); i++ ) |
---|
| 1140 | result += i.coeff()( f, v ) * power( x, i.exp() ); |
---|
| 1141 | return result; |
---|
[45911d] | 1142 | } |
---|
| 1143 | } |
---|
[b60ef7] | 1144 | //}}} |
---|
| 1145 | |
---|
[45911d] | 1146 | //{{{ CanonicalForm CanonicalForm::operator [] ( int i ) const |
---|
| 1147 | //{{{ docu |
---|
| 1148 | // |
---|
| 1149 | // operator []() - return i'th coefficient from CO. |
---|
| 1150 | // |
---|
| 1151 | // Returns CO if CO is in a base domain and i equals zero. |
---|
| 1152 | // Returns zero (from the current domain) if CO is in a base |
---|
| 1153 | // domain and i is larger than zero. Otherwise, returns the |
---|
| 1154 | // coefficient to x^i in CO (if x denotes the main variable of |
---|
| 1155 | // CO) or zero if CO does not contain x^i. Elements in an |
---|
| 1156 | // algebraic extension are considered polynomials. i should be |
---|
| 1157 | // larger or equal zero. |
---|
| 1158 | // |
---|
| 1159 | // Note: Never use a loop like |
---|
| 1160 | // |
---|
| 1161 | // for ( int i = degree( f ); i >= 0; i-- ) |
---|
| 1162 | // foo( i, f[ i ] ); |
---|
| 1163 | // |
---|
[77aa42] | 1164 | // which is much slower than |
---|
[45911d] | 1165 | // |
---|
| 1166 | // for ( int i = degree( f ), CFIterator I = f; I.hasTerms(); I++ ) { |
---|
| 1167 | // // fill gap with zeroes |
---|
| 1168 | // for ( ; i > I.exp(); i-- ) |
---|
| 1169 | // foo( i, 0 ); |
---|
| 1170 | // // at this point, i == I.exp() |
---|
| 1171 | // foo( i, i.coeff() ); |
---|
| 1172 | // i--; |
---|
| 1173 | // } |
---|
| 1174 | // // work through trailing zeroes |
---|
| 1175 | // for ( ; i >= 0; i-- ) |
---|
| 1176 | // foo( i, 0 ); |
---|
| 1177 | // |
---|
| 1178 | //}}} |
---|
[b60ef7] | 1179 | CanonicalForm |
---|
[45911d] | 1180 | CanonicalForm::operator [] ( int i ) const |
---|
[b60ef7] | 1181 | { |
---|
[45911d] | 1182 | ASSERT( i >= 0, "index to operator [] less than zero" ); |
---|
| 1183 | if ( is_imm( value ) ) |
---|
[094eed] | 1184 | if ( i == 0 ) |
---|
| 1185 | return *this; |
---|
| 1186 | else |
---|
| 1187 | return CanonicalForm( 0 ); |
---|
[45911d] | 1188 | else |
---|
[094eed] | 1189 | return value->coeff( i ); |
---|
[b60ef7] | 1190 | } |
---|
| 1191 | //}}} |
---|
| 1192 | |
---|
| 1193 | //{{{ CanonicalForm CanonicalForm::deriv (), deriv ( x ) |
---|
| 1194 | //{{{ docu |
---|
| 1195 | // |
---|
| 1196 | // deriv() - return the formal derivation of CO. |
---|
| 1197 | // |
---|
| 1198 | // deriv() derives CO with respect to its main variable. Returns |
---|
[32a335b] | 1199 | // zero from the current domain if f is in a coefficient domain. |
---|
[b60ef7] | 1200 | // |
---|
| 1201 | // deriv( x ) derives CO with respect to x. x should be a |
---|
[32a335b] | 1202 | // polynomial variable. Returns zero from the current domain if |
---|
| 1203 | // f is in a coefficient domain. |
---|
[b60ef7] | 1204 | // |
---|
| 1205 | // See also: ::deriv() |
---|
| 1206 | // |
---|
| 1207 | //}}} |
---|
| 1208 | CanonicalForm |
---|
| 1209 | CanonicalForm::deriv () const |
---|
| 1210 | { |
---|
| 1211 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
[094eed] | 1212 | return CanonicalForm( 0 ); |
---|
[b60ef7] | 1213 | else { |
---|
[094eed] | 1214 | CanonicalForm result = 0; |
---|
| 1215 | Variable x = value->variable(); |
---|
| 1216 | for ( CFIterator i = *this; i.hasTerms(); i++ ) |
---|
| 1217 | if ( i.exp() > 0 ) |
---|
| 1218 | result += power( x, i.exp()-1 ) * i.coeff() * i.exp(); |
---|
| 1219 | return result; |
---|
[b60ef7] | 1220 | } |
---|
| 1221 | } |
---|
| 1222 | |
---|
| 1223 | CanonicalForm |
---|
| 1224 | CanonicalForm::deriv ( const Variable & x ) const |
---|
| 1225 | { |
---|
| 1226 | ASSERT( x.level() > 0, "cannot derive with respect to algebraic variables" ); |
---|
| 1227 | if ( is_imm( value ) || value->inCoeffDomain() ) |
---|
[094eed] | 1228 | return CanonicalForm( 0 ); |
---|
[b60ef7] | 1229 | |
---|
| 1230 | Variable y = value->variable(); |
---|
| 1231 | if ( x > y ) |
---|
[094eed] | 1232 | return CanonicalForm( 0 ); |
---|
[b60ef7] | 1233 | else if ( x == y ) |
---|
[094eed] | 1234 | return deriv(); |
---|
[b60ef7] | 1235 | else { |
---|
[094eed] | 1236 | CanonicalForm result = 0; |
---|
| 1237 | for ( CFIterator i = *this; i.hasTerms(); i++ ) |
---|
| 1238 | result += i.coeff().deriv( x ) * power( y, i.exp() ); |
---|
| 1239 | return result; |
---|
[b60ef7] | 1240 | } |
---|
| 1241 | } |
---|
| 1242 | //}}} |
---|
| 1243 | |
---|
| 1244 | //{{{ int CanonicalForm::sign () const |
---|
| 1245 | //{{{ docu |
---|
| 1246 | // |
---|
| 1247 | // sign() - return sign of CO. |
---|
| 1248 | // |
---|
| 1249 | // If CO is an integer or a rational number, the sign is defined |
---|
[32a335b] | 1250 | // as usual. If CO is an element of a prime power domain or of |
---|
| 1251 | // FF(p) and SW_SYMMETRIC_FF is on, the sign of CO is the sign of |
---|
| 1252 | // the symmetric representation of CO. If CO is in GF(q) or in |
---|
| 1253 | // FF(p) and SW_SYMMETRIC_FF is off, the sign of CO is zero iff |
---|
| 1254 | // CO is zero, otherwise the sign is one. |
---|
[b60ef7] | 1255 | // |
---|
| 1256 | // If CO is a polynomial or in an extension of one of the base |
---|
| 1257 | // domains, the sign of CO is the sign of its leading |
---|
| 1258 | // coefficient. |
---|
| 1259 | // |
---|
| 1260 | // See also: InternalCF::sign(), InternalInteger::sign(), |
---|
| 1261 | // InternalPrimePower::sign(), InternalRational::sign(), |
---|
| 1262 | // InternalPoly::sign(), imm_sign(), gf_sign() |
---|
| 1263 | // |
---|
| 1264 | //}}} |
---|
| 1265 | int |
---|
| 1266 | CanonicalForm::sign () const |
---|
| 1267 | { |
---|
| 1268 | if ( is_imm( value ) ) |
---|
[094eed] | 1269 | return imm_sign( value ); |
---|
[b60ef7] | 1270 | else |
---|
[094eed] | 1271 | return value->sign(); |
---|
[b60ef7] | 1272 | } |
---|
| 1273 | //}}} |
---|
| 1274 | |
---|
| 1275 | //{{{ CanonicalForm CanonicalForm::sqrt () const |
---|
| 1276 | //{{{ docu |
---|
| 1277 | // |
---|
| 1278 | // sqrt() - calculate integer square root. |
---|
| 1279 | // |
---|
| 1280 | // CO has to be an integer greater or equal zero. Returns the |
---|
| 1281 | // largest integer less or equal sqrt(CO). |
---|
| 1282 | // |
---|
| 1283 | // In the immediate case, we use the newton method to find the |
---|
| 1284 | // root. The algorithm is from H. Cohen - 'A Course in |
---|
| 1285 | // Computational Algebraic Number Theory', ch. 1.7.1. |
---|
| 1286 | // |
---|
| 1287 | // See also: InternalCF::sqrt(), InternalInteger::sqrt(), ::sqrt() |
---|
| 1288 | // |
---|
| 1289 | //}}} |
---|
| 1290 | CanonicalForm |
---|
| 1291 | CanonicalForm::sqrt () const |
---|
| 1292 | { |
---|
| 1293 | if ( is_imm( value ) ) { |
---|
[094eed] | 1294 | ASSERT( is_imm( value ) == INTMARK, "sqrt() not implemented" ); |
---|
[8710ff0] | 1295 | long n = imm2int( value ); |
---|
[094eed] | 1296 | ASSERT( n >= 0, "arg to sqrt() less than zero" ); |
---|
| 1297 | if ( n == 0 || n == 1 ) |
---|
| 1298 | return CanonicalForm( n ); |
---|
| 1299 | else { |
---|
[8710ff0] | 1300 | long x, y = n; |
---|
[094eed] | 1301 | do { |
---|
| 1302 | x = y; |
---|
| 1303 | // the intermediate result may not fit into an |
---|
| 1304 | // integer, but the result does |
---|
[8710ff0] | 1305 | y = (unsigned long)(x + n/x)/2; |
---|
[094eed] | 1306 | } while ( y < x ); |
---|
| 1307 | return CanonicalForm( x ); |
---|
| 1308 | } |
---|
[b60ef7] | 1309 | } |
---|
| 1310 | else |
---|
[094eed] | 1311 | return CanonicalForm( value->sqrt() ); |
---|
[b60ef7] | 1312 | } |
---|
| 1313 | //}}} |
---|
| 1314 | |
---|
| 1315 | //{{{ int CanonicalForm::ilog2 () const |
---|
| 1316 | //{{{ docu |
---|
| 1317 | // |
---|
| 1318 | // ilog2() - integer logarithm to base 2. |
---|
| 1319 | // |
---|
| 1320 | // Returns the largest integer less or equal logarithm of CO to |
---|
| 1321 | // base 2. CO should be a positive integer. |
---|
| 1322 | // |
---|
| 1323 | // See also: InternalCF::ilog2(), InternalInteger::ilog2(), ::ilog2() |
---|
| 1324 | // |
---|
| 1325 | //}}} |
---|
| 1326 | int |
---|
| 1327 | CanonicalForm::ilog2 () const |
---|
| 1328 | { |
---|
[d4932a] | 1329 | if ( is_imm( value ) ) |
---|
| 1330 | { |
---|
[094eed] | 1331 | ASSERT( is_imm( value ) == INTMARK, "ilog2() not implemented" ); |
---|
[8710ff0] | 1332 | long a = imm2int( value ); |
---|
[094eed] | 1333 | ASSERT( a > 0, "arg to ilog2() less or equal zero" ); |
---|
[81e336] | 1334 | int n = -1; |
---|
| 1335 | while ( a > 0 ) |
---|
| 1336 | { |
---|
| 1337 | n++; |
---|
| 1338 | a /=2; |
---|
| 1339 | } |
---|
| 1340 | return n; |
---|
[b60ef7] | 1341 | } |
---|
| 1342 | else |
---|
[094eed] | 1343 | return value->ilog2(); |
---|
[b60ef7] | 1344 | } |
---|
| 1345 | //}}} |
---|
| 1346 | |
---|
[32a335b] | 1347 | //{{{ bool operator ==, operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1348 | //{{{ docu |
---|
| 1349 | // |
---|
| 1350 | // operator ==(), operator !=() - compare canonical forms on |
---|
| 1351 | // (in)equality. |
---|
| 1352 | // |
---|
| 1353 | // operator ==() returns true iff lhs equals rhs. |
---|
| 1354 | // operator !=() returns true iff lhs does not equal rhs. |
---|
| 1355 | // |
---|
| 1356 | // This is the point in factory where we essentially use that |
---|
| 1357 | // CanonicalForms in fact are canonical. There must not be two |
---|
| 1358 | // different representations of the same mathematical object, |
---|
| 1359 | // otherwise, such (in)equality will not be recognized by these |
---|
| 1360 | // operators. In other word, we rely on the fact that structural |
---|
| 1361 | // different factory objects in any case represent different |
---|
| 1362 | // mathematical objects. |
---|
| 1363 | // |
---|
| 1364 | // So we use the following procedure to test on equality (and |
---|
| 1365 | // analogously on inequality). First, we check whether lhs.value |
---|
| 1366 | // equals rhs.value. If so we are ready and return true. |
---|
| 1367 | // Second, if one of the operands is immediate, but the other one |
---|
| 1368 | // not, we return false. Third, if the operand's levels differ |
---|
| 1369 | // we return false. Fourth, if the operand's levelcoeffs differ |
---|
| 1370 | // we return false. At last, we call the corresponding internal |
---|
| 1371 | // method to compare both operands. |
---|
| 1372 | // |
---|
| 1373 | // Both operands should have coefficients from the same base domain. |
---|
| 1374 | // |
---|
| 1375 | // Note: To compare with the zero or the unit of the current domain, |
---|
| 1376 | // you better use the methods `CanonicalForm::isZero()' or |
---|
| 1377 | // `CanonicalForm::isOne()', resp., than something like `f == 0', |
---|
| 1378 | // since the latter is quite a lot slower. |
---|
| 1379 | // |
---|
| 1380 | // See also: InternalCF::comparesame(), |
---|
| 1381 | // InternalInteger::comparesame(), InternalRational::comparesame(), |
---|
| 1382 | // InternalPrimePower::comparesame(), InternalPoly::comparesame() |
---|
| 1383 | // |
---|
[b60ef7] | 1384 | //}}} |
---|
| 1385 | bool |
---|
| 1386 | operator == ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1387 | { |
---|
[32a335b] | 1388 | if ( lhs.value == rhs.value ) |
---|
[094eed] | 1389 | return true; |
---|
[32a335b] | 1390 | else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) { |
---|
[094eed] | 1391 | ASSERT( ! is_imm( rhs.value ) || |
---|
| 1392 | ! is_imm( lhs.value ) || |
---|
| 1393 | is_imm( rhs.value ) == is_imm( lhs.value ), |
---|
| 1394 | "incompatible operands" ); |
---|
| 1395 | return false; |
---|
[32a335b] | 1396 | } |
---|
| 1397 | else if ( lhs.value->level() != rhs.value->level() ) |
---|
[094eed] | 1398 | return false; |
---|
[32a335b] | 1399 | else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() ) |
---|
[094eed] | 1400 | return false; |
---|
[32a335b] | 1401 | else |
---|
[094eed] | 1402 | return rhs.value->comparesame( lhs.value ) == 0; |
---|
[b60ef7] | 1403 | } |
---|
| 1404 | |
---|
| 1405 | bool |
---|
| 1406 | operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1407 | { |
---|
[32a335b] | 1408 | if ( lhs.value == rhs.value ) |
---|
[094eed] | 1409 | return false; |
---|
[32a335b] | 1410 | else if ( is_imm( rhs.value ) || is_imm( lhs.value ) ) { |
---|
[094eed] | 1411 | ASSERT( ! is_imm( rhs.value ) || |
---|
| 1412 | ! is_imm( lhs.value ) || |
---|
| 1413 | is_imm( rhs.value ) == is_imm( lhs.value ), |
---|
| 1414 | "incompatible operands" ); |
---|
| 1415 | return true; |
---|
[32a335b] | 1416 | } |
---|
| 1417 | else if ( lhs.value->level() != rhs.value->level() ) |
---|
[094eed] | 1418 | return true; |
---|
[32a335b] | 1419 | else if ( lhs.value->levelcoeff() != rhs.value->levelcoeff() ) |
---|
[094eed] | 1420 | return true; |
---|
| 1421 | else return rhs.value->comparesame( lhs.value ) != 0; |
---|
[b60ef7] | 1422 | } |
---|
[32a335b] | 1423 | //}}} |
---|
[b60ef7] | 1424 | |
---|
[32a335b] | 1425 | //{{{ bool operator >, operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1426 | //{{{ docu |
---|
| 1427 | // |
---|
| 1428 | // operator >(), operator <() - compare canonical forms. on size or |
---|
| 1429 | // level. |
---|
| 1430 | // |
---|
| 1431 | // The most common and most useful application of these operators |
---|
| 1432 | // is to compare two integers or rationals, of course. However, |
---|
| 1433 | // these operators are defined on all other base domains and on |
---|
| 1434 | // polynomials, too. From a mathematical point of view this may |
---|
| 1435 | // seem meaningless, since there is no ordering on finite fields |
---|
| 1436 | // or on polynomials respecting the algebraic structure. |
---|
| 1437 | // Nevertheless, from a programmer's point of view it may be |
---|
| 1438 | // sensible to order these objects, e.g. to sort them. |
---|
| 1439 | // |
---|
[77aa42] | 1440 | // Therefore, the ordering defined by these operators in any case |
---|
| 1441 | // is a total ordering which fulfills the law of trichotomy. |
---|
[32a335b] | 1442 | // |
---|
| 1443 | // It is clear how this is done in the case of the integers and |
---|
| 1444 | // the rationals. For finite fields, all you can say is that |
---|
| 1445 | // zero is the minimal element w.r.t. the ordering, the other |
---|
| 1446 | // elements are ordered in an arbitrary (but total!) way. For |
---|
| 1447 | // polynomials, you have an ordering derived from the |
---|
| 1448 | // lexicographical ordering of monomials. E.g. if lm(f) < lm(g) |
---|
| 1449 | // w.r.t. lexicographic ordering, then f < g. For more details, |
---|
| 1450 | // refer to the documentation of `InternalPoly::operator <()'. |
---|
[094eed] | 1451 | // |
---|
[32a335b] | 1452 | // Both operands should have coefficients from the same base domain. |
---|
| 1453 | // |
---|
| 1454 | // The scheme how both operators are implemented is allmost the |
---|
| 1455 | // same as for the assignment operators (check for immediates, |
---|
| 1456 | // then check levels, then check levelcoeffs, then call the |
---|
| 1457 | // appropriate internal comparesame()/comparecoeff() method). |
---|
| 1458 | // For more information, confer to the overview for the |
---|
| 1459 | // arithmetic operators. |
---|
| 1460 | // |
---|
| 1461 | // See also: InternalCF::comparesame(), |
---|
| 1462 | // InternalInteger::comparesame(), InternalRational::comparesame(), |
---|
| 1463 | // InternalPrimePower::comparesame(), InternalPoly::comparesame(), |
---|
| 1464 | // InternalCF::comparecoeff(), InternalInteger::comparecoeff(), |
---|
| 1465 | // InternalRational::comparecoeff(), |
---|
| 1466 | // InternalPrimePower::comparecoeff(), InternalPoly::comparecoeff(), |
---|
| 1467 | // imm_cmp(), imm_cmp_p(), imm_cmp_gf() |
---|
| 1468 | // |
---|
| 1469 | //}}} |
---|
[b60ef7] | 1470 | bool |
---|
| 1471 | operator > ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1472 | { |
---|
[32a335b] | 1473 | int what = is_imm( rhs.value ); |
---|
| 1474 | if ( is_imm( lhs.value ) ) { |
---|
[094eed] | 1475 | ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" ); |
---|
| 1476 | if ( what == 0 ) |
---|
| 1477 | return rhs.value->comparecoeff( lhs.value ) < 0; |
---|
| 1478 | else if ( what == INTMARK ) |
---|
| 1479 | return imm_cmp( lhs.value, rhs.value ) > 0; |
---|
| 1480 | else if ( what == FFMARK ) |
---|
| 1481 | return imm_cmp_p( lhs.value, rhs.value ) > 0; |
---|
| 1482 | else |
---|
| 1483 | return imm_cmp_gf( lhs.value, rhs.value ) > 0; |
---|
[b60ef7] | 1484 | } |
---|
[32a335b] | 1485 | else if ( what ) |
---|
[094eed] | 1486 | return lhs.value->comparecoeff( rhs.value ) > 0; |
---|
[32a335b] | 1487 | else if ( lhs.value->level() == rhs.value->level() ) |
---|
[094eed] | 1488 | if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() ) |
---|
| 1489 | return lhs.value->comparesame( rhs.value ) > 0; |
---|
| 1490 | else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() ) |
---|
| 1491 | return lhs.value->comparecoeff( rhs.value ) > 0; |
---|
| 1492 | else |
---|
| 1493 | return rhs.value->comparecoeff( lhs.value ) < 0; |
---|
[b60ef7] | 1494 | else |
---|
[094eed] | 1495 | return lhs.value->level() > rhs.value->level(); |
---|
[b60ef7] | 1496 | } |
---|
| 1497 | |
---|
| 1498 | bool |
---|
| 1499 | operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs ) |
---|
| 1500 | { |
---|
[32a335b] | 1501 | int what = is_imm( rhs.value ); |
---|
| 1502 | if ( is_imm( lhs.value ) ) { |
---|
[094eed] | 1503 | ASSERT( ! what || (what == is_imm( lhs.value )), "incompatible operands" ); |
---|
| 1504 | if ( what == 0 ) |
---|
| 1505 | return rhs.value->comparecoeff( lhs.value ) > 0; |
---|
| 1506 | else if ( what == INTMARK ) |
---|
| 1507 | return imm_cmp( lhs.value, rhs.value ) < 0; |
---|
| 1508 | else if ( what == FFMARK ) |
---|
| 1509 | return imm_cmp_p( lhs.value, rhs.value ) < 0; |
---|
| 1510 | else |
---|
| 1511 | return imm_cmp_gf( lhs.value, rhs.value ) < 0; |
---|
[b60ef7] | 1512 | } |
---|
[32a335b] | 1513 | else if ( what ) |
---|
[094eed] | 1514 | return lhs.value->comparecoeff( rhs.value ) < 0; |
---|
[32a335b] | 1515 | else if ( lhs.value->level() == rhs.value->level() ) |
---|
[094eed] | 1516 | if ( lhs.value->levelcoeff() == rhs.value->levelcoeff() ) |
---|
| 1517 | return lhs.value->comparesame( rhs.value ) < 0; |
---|
| 1518 | else if ( lhs.value->levelcoeff() > rhs.value->levelcoeff() ) |
---|
| 1519 | return lhs.value->comparecoeff( rhs.value ) < 0; |
---|
| 1520 | else |
---|
| 1521 | return rhs.value->comparecoeff( lhs.value ) > 0; |
---|
[b60ef7] | 1522 | else |
---|
[094eed] | 1523 | return lhs.value->level() < rhs.value->level(); |
---|
[b60ef7] | 1524 | } |
---|
| 1525 | //}}} |
---|
| 1526 | |
---|
[77aa42] | 1527 | //{{{ CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ) |
---|
| 1528 | //{{{ docu |
---|
| 1529 | // |
---|
| 1530 | // bgcd() - return base coefficient gcd. |
---|
| 1531 | // |
---|
| 1532 | // If both f and g are integers and `SW_RATIONAL' is off the |
---|
| 1533 | // positive greatest common divisor of f and g is returned. |
---|
| 1534 | // Otherwise, if `SW_RATIONAL' is on or one of f and g is not an |
---|
| 1535 | // integer, the greatest common divisor is trivial: either zero |
---|
| 1536 | // if f and g equal zero or one (both from the current domain). |
---|
| 1537 | // |
---|
| 1538 | // f and g should come from one base domain which should be not |
---|
| 1539 | // the prime power domain. |
---|
| 1540 | // |
---|
[094eed] | 1541 | // Implementation: |
---|
[77aa42] | 1542 | // |
---|
| 1543 | // CanonicalForm::bgcd() handles the immediate case with a |
---|
| 1544 | // standard euclidean algorithm. For the non-immediate cases |
---|
| 1545 | // `InternalCF::bgcdsame()' or `InternalCF::bgcdcoeff()', resp. are |
---|
| 1546 | // called following the usual level/levelcoeff approach. |
---|
| 1547 | // |
---|
| 1548 | // InternalCF::bgcdsame() and |
---|
| 1549 | // InternalCF::bgcdcoeff() throw an assertion ("not implemented") |
---|
| 1550 | // |
---|
| 1551 | // InternalInteger::bgcdsame() is a wrapper around `mpz_gcd()' |
---|
| 1552 | // which takes some care about immediate results and the sign |
---|
| 1553 | // of the result |
---|
| 1554 | // InternalInteger::bgcdcoeff() is a wrapper around |
---|
| 1555 | // `mpz_gcd_ui()' which takes some care about the sign |
---|
| 1556 | // of the result |
---|
| 1557 | // |
---|
| 1558 | // InternalRational::bgcdsame() and |
---|
| 1559 | // InternalRational::bgcdcoeff() always return one |
---|
| 1560 | // |
---|
| 1561 | //}}} |
---|
| 1562 | CanonicalForm |
---|
| 1563 | bgcd ( const CanonicalForm & f, const CanonicalForm & g ) |
---|
| 1564 | { |
---|
| 1565 | // check immediate cases |
---|
| 1566 | int what = is_imm( g.value ); |
---|
[2b44a1] | 1567 | if ( is_imm( f.value ) ) |
---|
| 1568 | { |
---|
[094eed] | 1569 | ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" ); |
---|
| 1570 | if ( what == 0 ) |
---|
| 1571 | return g.value->bgcdcoeff( f.value ); |
---|
[2b44a1] | 1572 | else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) |
---|
[806c18] | 1573 | { |
---|
[094eed] | 1574 | // calculate gcd using standard integer |
---|
| 1575 | // arithmetic |
---|
[8710ff0] | 1576 | long fInt = imm2int( f.value ); |
---|
| 1577 | long gInt = imm2int( g.value ); |
---|
[094eed] | 1578 | |
---|
| 1579 | if ( fInt < 0 ) fInt = -fInt; |
---|
| 1580 | if ( gInt < 0 ) gInt = -gInt; |
---|
| 1581 | // swap fInt and gInt |
---|
[2b44a1] | 1582 | if ( gInt > fInt ) |
---|
[806c18] | 1583 | { |
---|
[8710ff0] | 1584 | long swap = gInt; |
---|
[094eed] | 1585 | gInt = fInt; |
---|
| 1586 | fInt = swap; |
---|
| 1587 | } |
---|
| 1588 | |
---|
| 1589 | // now, 0 <= gInt <= fInt. Start the loop. |
---|
[2b44a1] | 1590 | while ( gInt ) |
---|
[806c18] | 1591 | { |
---|
[094eed] | 1592 | // calculate (fInt, gInt) = (gInt, fInt%gInt) |
---|
[8710ff0] | 1593 | long r = fInt % gInt; |
---|
[094eed] | 1594 | fInt = gInt; |
---|
| 1595 | gInt = r; |
---|
| 1596 | } |
---|
| 1597 | |
---|
| 1598 | return CanonicalForm( fInt ); |
---|
[2b44a1] | 1599 | } |
---|
[806c18] | 1600 | else |
---|
[094eed] | 1601 | // we do not go for maximal speed for these stupid |
---|
| 1602 | // special cases |
---|
| 1603 | return CanonicalForm( f.isZero() && g.isZero() ? 0 : 1 ); |
---|
[77aa42] | 1604 | } |
---|
| 1605 | else if ( what ) |
---|
[094eed] | 1606 | return f.value->bgcdcoeff( g.value ); |
---|
[77aa42] | 1607 | |
---|
| 1608 | int fLevel = f.value->level(); |
---|
| 1609 | int gLevel = g.value->level(); |
---|
| 1610 | |
---|
| 1611 | // check levels |
---|
[2b44a1] | 1612 | if ( fLevel == gLevel ) |
---|
| 1613 | { |
---|
[094eed] | 1614 | fLevel = f.value->levelcoeff(); |
---|
| 1615 | gLevel = g.value->levelcoeff(); |
---|
| 1616 | |
---|
| 1617 | // check levelcoeffs |
---|
| 1618 | if ( fLevel == gLevel ) |
---|
| 1619 | return f.value->bgcdsame( g.value ); |
---|
| 1620 | else if ( fLevel < gLevel ) |
---|
| 1621 | return g.value->bgcdcoeff( f.value ); |
---|
| 1622 | else |
---|
| 1623 | return f.value->bgcdcoeff( g.value ); |
---|
[77aa42] | 1624 | } |
---|
| 1625 | else if ( fLevel < gLevel ) |
---|
[094eed] | 1626 | return g.value->bgcdcoeff( f.value ); |
---|
[77aa42] | 1627 | else |
---|
[094eed] | 1628 | return f.value->bgcdcoeff( g.value ); |
---|
[77aa42] | 1629 | } |
---|
| 1630 | //}}} |
---|
| 1631 | |
---|
| 1632 | //{{{ CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) |
---|
| 1633 | //{{{ docu |
---|
| 1634 | // |
---|
| 1635 | // bextgcd() - return base coefficient extended gcd. |
---|
| 1636 | // |
---|
| 1637 | //}}} |
---|
| 1638 | CanonicalForm |
---|
| 1639 | bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) |
---|
| 1640 | { |
---|
| 1641 | // check immediate cases |
---|
| 1642 | int what = is_imm( g.value ); |
---|
| 1643 | if ( is_imm( f.value ) ) { |
---|
[094eed] | 1644 | ASSERT( ! what || (what == is_imm( f.value )), "incompatible operands" ); |
---|
| 1645 | if ( what == 0 ) |
---|
| 1646 | return g.value->bextgcdcoeff( f.value, b, a ); |
---|
| 1647 | else if ( what == INTMARK && ! cf_glob_switches.isOn( SW_RATIONAL ) ) { |
---|
| 1648 | // calculate extended gcd using standard integer |
---|
| 1649 | // arithmetic |
---|
[8710ff0] | 1650 | long fInt = imm2int( f.value ); |
---|
| 1651 | long gInt = imm2int( g.value ); |
---|
[094eed] | 1652 | |
---|
| 1653 | // to avoid any system dpendencies with `%', we work |
---|
| 1654 | // with positive numbers only. To a pity, we have to |
---|
| 1655 | // redo all the checks when assigning to a and b. |
---|
| 1656 | if ( fInt < 0 ) fInt = -fInt; |
---|
| 1657 | if ( gInt < 0 ) gInt = -gInt; |
---|
| 1658 | // swap fInt and gInt |
---|
| 1659 | if ( gInt > fInt ) { |
---|
[8710ff0] | 1660 | long swap = gInt; |
---|
[094eed] | 1661 | gInt = fInt; |
---|
| 1662 | fInt = swap; |
---|
| 1663 | } |
---|
| 1664 | |
---|
[8710ff0] | 1665 | long u = 1; long v = 0; |
---|
| 1666 | long uNext = 0; long vNext = 1; |
---|
[094eed] | 1667 | |
---|
| 1668 | // at any step, we have: |
---|
| 1669 | // fInt_0 * u + gInt_0 * v = fInt |
---|
| 1670 | // fInt_0 * uNext + gInt_0 * vNext = gInt |
---|
| 1671 | // where fInt_0 and gInt_0 denote the values of fint |
---|
| 1672 | // and gInt, resp., at the beginning |
---|
| 1673 | while ( gInt ) { |
---|
[8710ff0] | 1674 | long r = fInt % gInt; |
---|
| 1675 | long q = fInt / gInt; |
---|
| 1676 | long uSwap = u - q * uNext; |
---|
| 1677 | long vSwap = v - q * vNext; |
---|
[094eed] | 1678 | |
---|
| 1679 | // update variables |
---|
| 1680 | fInt = gInt; |
---|
| 1681 | gInt = r; |
---|
| 1682 | u = uNext; v = vNext; |
---|
| 1683 | uNext = uSwap; vNext = vSwap; |
---|
| 1684 | } |
---|
| 1685 | |
---|
| 1686 | // now, assign to a and b |
---|
[8710ff0] | 1687 | long fTest = imm2int( f.value ); |
---|
| 1688 | long gTest = imm2int( g.value ); |
---|
[094eed] | 1689 | if ( gTest > fTest ) { |
---|
| 1690 | a = v; b = u; |
---|
| 1691 | } else { |
---|
| 1692 | a = u; b = v; |
---|
| 1693 | } |
---|
| 1694 | if ( fTest < 0 ) a = -a; |
---|
| 1695 | if ( gTest < 0 ) b = -b; |
---|
| 1696 | return CanonicalForm( fInt ); |
---|
| 1697 | } else |
---|
| 1698 | // stupid special cases |
---|
| 1699 | if ( ! f.isZero() ) { |
---|
| 1700 | a = 1/f; b = 0; return CanonicalForm( 1 ); |
---|
| 1701 | } else if ( ! g.isZero() ) { |
---|
| 1702 | a = 0; b = 1/g; return CanonicalForm( 1 ); |
---|
| 1703 | } else { |
---|
| 1704 | a = 0; b = 0; return CanonicalForm( 0 ); |
---|
| 1705 | } |
---|
[77aa42] | 1706 | } |
---|
| 1707 | else if ( what ) |
---|
[094eed] | 1708 | return f.value->bextgcdcoeff( g.value, a, b ); |
---|
[77aa42] | 1709 | |
---|
| 1710 | int fLevel = f.value->level(); |
---|
| 1711 | int gLevel = g.value->level(); |
---|
| 1712 | |
---|
| 1713 | // check levels |
---|
| 1714 | if ( fLevel == gLevel ) { |
---|
[094eed] | 1715 | fLevel = f.value->levelcoeff(); |
---|
| 1716 | gLevel = g.value->levelcoeff(); |
---|
| 1717 | |
---|
| 1718 | // check levelcoeffs |
---|
| 1719 | if ( fLevel == gLevel ) |
---|
| 1720 | return f.value->bextgcdsame( g.value, a, b ); |
---|
| 1721 | else if ( fLevel < gLevel ) |
---|
| 1722 | return g.value->bextgcdcoeff( f.value, b, a ); |
---|
| 1723 | else |
---|
| 1724 | return f.value->bextgcdcoeff( g.value, a, b ); |
---|
[77aa42] | 1725 | } |
---|
| 1726 | else if ( fLevel < gLevel ) |
---|
[094eed] | 1727 | return g.value->bextgcdcoeff( f.value, b, a ); |
---|
[77aa42] | 1728 | else |
---|
[094eed] | 1729 | return f.value->bextgcdcoeff( g.value, a, b ); |
---|
[77aa42] | 1730 | } |
---|
| 1731 | //}}} |
---|
| 1732 | |
---|
[d74a8b] | 1733 | CanonicalForm |
---|
| 1734 | blcm ( const CanonicalForm & f, const CanonicalForm & g ) |
---|
| 1735 | { |
---|
| 1736 | if ( f.isZero() || g.isZero() ) |
---|
[094eed] | 1737 | return CanonicalForm( 0 ); |
---|
[77f483] | 1738 | /* |
---|
| 1739 | else if (f.isOne()) |
---|
| 1740 | return g; |
---|
| 1741 | else if (g.isOne()) |
---|
| 1742 | return f; |
---|
| 1743 | */ |
---|
[d74a8b] | 1744 | else |
---|
[094eed] | 1745 | return (f / bgcd( f, g )) * g; |
---|
[d74a8b] | 1746 | } |
---|
| 1747 | |
---|
[b60ef7] | 1748 | //{{{ input/output |
---|
[c5323e] | 1749 | #ifndef NOSTREAMIO |
---|
[b60ef7] | 1750 | void |
---|
[181148] | 1751 | CanonicalForm::print( OSTREAM & os, char * str ) const |
---|
[b60ef7] | 1752 | { |
---|
| 1753 | if ( is_imm( value ) ) |
---|
[094eed] | 1754 | imm_print( os, value, str ); |
---|
[b60ef7] | 1755 | else |
---|
[094eed] | 1756 | value->print( os, str ); |
---|
[b60ef7] | 1757 | } |
---|
| 1758 | |
---|
[6400f5] | 1759 | void |
---|
[181148] | 1760 | CanonicalForm::print( OSTREAM & os ) const |
---|
[6400f5] | 1761 | { |
---|
| 1762 | if ( is_imm( value ) ) |
---|
[094eed] | 1763 | imm_print( os, value, "" ); |
---|
[6400f5] | 1764 | else |
---|
[094eed] | 1765 | value->print( os, "" ); |
---|
[6400f5] | 1766 | } |
---|
| 1767 | |
---|
[181148] | 1768 | OSTREAM& |
---|
| 1769 | operator << ( OSTREAM & os, const CanonicalForm & cf ) |
---|
[2dd068] | 1770 | { |
---|
| 1771 | cf.print( os, "" ); |
---|
| 1772 | return os; |
---|
| 1773 | } |
---|
| 1774 | |
---|
[181148] | 1775 | ISTREAM& |
---|
| 1776 | operator >> ( ISTREAM & is, CanonicalForm & cf ) |
---|
[2dd068] | 1777 | { |
---|
| 1778 | cf = readCF( is ); |
---|
| 1779 | return is; |
---|
| 1780 | } |
---|
[c5323e] | 1781 | #endif /* NOSTREAMIO */ |
---|
[b60ef7] | 1782 | //}}} |
---|
[2dd068] | 1783 | |
---|
[b79ed5] | 1784 | //{{{ genOne(), genZero() |
---|
[2dd068] | 1785 | CanonicalForm |
---|
[b60ef7] | 1786 | CanonicalForm::genZero() const |
---|
[2dd068] | 1787 | { |
---|
[b60ef7] | 1788 | int what = is_imm( value ); |
---|
| 1789 | if ( what == FFMARK ) |
---|
[8710ff0] | 1790 | return CanonicalForm( CFFactory::basic( FiniteFieldDomain, 0L ) ); |
---|
[b60ef7] | 1791 | else if ( what == GFMARK ) |
---|
[8710ff0] | 1792 | return CanonicalForm( CFFactory::basic( GaloisFieldDomain, 0L ) ); |
---|
[b60ef7] | 1793 | else if ( what ) |
---|
[8710ff0] | 1794 | return CanonicalForm( CFFactory::basic( IntegerDomain, 0L ) ); |
---|
[b60ef7] | 1795 | else |
---|
[094eed] | 1796 | return CanonicalForm( value->genZero() ); |
---|
[2dd068] | 1797 | } |
---|
| 1798 | |
---|
| 1799 | CanonicalForm |
---|
[b60ef7] | 1800 | CanonicalForm::genOne() const |
---|
[2dd068] | 1801 | { |
---|
[b60ef7] | 1802 | int what = is_imm( value ); |
---|
| 1803 | if ( what == FFMARK ) |
---|
[8710ff0] | 1804 | return CanonicalForm( CFFactory::basic( FiniteFieldDomain, 1L ) ); |
---|
[b60ef7] | 1805 | else if ( what == GFMARK ) |
---|
[8710ff0] | 1806 | return CanonicalForm( CFFactory::basic( GaloisFieldDomain, 1L ) ); |
---|
[b60ef7] | 1807 | else if ( what ) |
---|
[8710ff0] | 1808 | return CanonicalForm( CFFactory::basic( IntegerDomain, 1L ) ); |
---|
[2dd068] | 1809 | else |
---|
[094eed] | 1810 | return CanonicalForm( value->genOne() ); |
---|
[2dd068] | 1811 | } |
---|
[38c0795] | 1812 | //}}} |
---|
[2dd068] | 1813 | |
---|
[b60ef7] | 1814 | //{{{ exponentiation |
---|
[2dd068] | 1815 | CanonicalForm |
---|
| 1816 | power ( const CanonicalForm & f, int n ) |
---|
| 1817 | { |
---|
[9b8fb3a] | 1818 | ASSERT( n >= 0, "illegal exponent" ); |
---|
| 1819 | if ( f.isZero() ) |
---|
| 1820 | return 0; |
---|
| 1821 | else if ( f.isOne() ) |
---|
| 1822 | return f; |
---|
| 1823 | else if ( f == -1 ) |
---|
| 1824 | { |
---|
| 1825 | if ( n % 2 == 0 ) |
---|
| 1826 | return 1; |
---|
| 1827 | else |
---|
| 1828 | return -1; |
---|
| 1829 | } |
---|
| 1830 | else if ( n == 0 ) |
---|
| 1831 | return 1; |
---|
| 1832 | |
---|
| 1833 | //else if (f.inGF()) |
---|
| 1834 | //{ |
---|
| 1835 | //} |
---|
| 1836 | else |
---|
| 1837 | { |
---|
| 1838 | CanonicalForm g,h; |
---|
| 1839 | h=f; |
---|
| 1840 | while(n%2==0) |
---|
[094eed] | 1841 | { |
---|
[9b8fb3a] | 1842 | h*=h; |
---|
| 1843 | n/=2; |
---|
[2dd068] | 1844 | } |
---|
[9b8fb3a] | 1845 | g=h; |
---|
| 1846 | while(1) |
---|
[094eed] | 1847 | { |
---|
[9b8fb3a] | 1848 | n/=2; |
---|
| 1849 | if(n==0) |
---|
| 1850 | return g; |
---|
| 1851 | h*=h; |
---|
| 1852 | if(n%2!=0) g*=h; |
---|
[2dd068] | 1853 | } |
---|
[9b8fb3a] | 1854 | } |
---|
[2dd068] | 1855 | } |
---|
| 1856 | |
---|
| 1857 | CanonicalForm |
---|
| 1858 | power ( const Variable & v, int n ) |
---|
| 1859 | { |
---|
[57daf8] | 1860 | //ASSERT( n >= 0, "illegal exponent" ); |
---|
[2dd068] | 1861 | if ( n == 0 ) |
---|
[094eed] | 1862 | return 1; |
---|
[2dd068] | 1863 | else if ( n == 1 ) |
---|
[094eed] | 1864 | return v; |
---|
[6981f1] | 1865 | else if (( v.level() < 0 ) && (hasMipo(v))) |
---|
[094eed] | 1866 | { |
---|
| 1867 | CanonicalForm result( v, n-1 ); |
---|
| 1868 | return result * v; |
---|
[2dd068] | 1869 | } |
---|
| 1870 | else |
---|
[094eed] | 1871 | return CanonicalForm( v, n ); |
---|
[2dd068] | 1872 | } |
---|
[b60ef7] | 1873 | //}}} |
---|
[2dd068] | 1874 | |
---|
[b60ef7] | 1875 | //{{{ switches |
---|
[2dd068] | 1876 | void |
---|
| 1877 | On( int sw ) |
---|
| 1878 | { |
---|
| 1879 | cf_glob_switches.On( sw ); |
---|
| 1880 | } |
---|
| 1881 | |
---|
| 1882 | void |
---|
| 1883 | Off( int sw ) |
---|
| 1884 | { |
---|
| 1885 | cf_glob_switches.Off( sw ); |
---|
| 1886 | } |
---|
| 1887 | |
---|
| 1888 | bool |
---|
| 1889 | isOn( int sw ) |
---|
| 1890 | { |
---|
| 1891 | return cf_glob_switches.isOn( sw ); |
---|
| 1892 | } |
---|
[8d5d47] | 1893 | //}}} |
---|