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