[493c477] | 1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
[2dd068] | 2 | |
---|
[e4fe2b] | 3 | #include "config.h" |
---|
[9d7aaa] | 4 | |
---|
[32e9cd7] | 5 | #ifndef NOSTREAMIO |
---|
[2dd068] | 6 | #include <string.h> |
---|
[049c4f] | 7 | #if defined(WINNT) && ! defined(__GNUC__) |
---|
[4e8da2] | 8 | #include <strstrea.h> |
---|
| 9 | #else |
---|
[22347b6] | 10 | #if __GNUC__ < 3 |
---|
[2dd068] | 11 | #include <strstream.h> |
---|
[22347b6] | 12 | #else |
---|
| 13 | #include <strstream> |
---|
| 14 | using namespace std; |
---|
| 15 | #endif |
---|
[4e8da2] | 16 | #endif |
---|
[32e9cd7] | 17 | #endif /* NOSTREAMIO */ |
---|
[2dd068] | 18 | |
---|
[650f2d8] | 19 | #include "cf_assert.h" |
---|
[32e9cd7] | 20 | |
---|
[2dd068] | 21 | #include "cf_defs.h" |
---|
| 22 | #include "cf_factory.h" |
---|
| 23 | #include "int_cf.h" |
---|
[778a4e] | 24 | #include "int_int.h" |
---|
[2dd068] | 25 | #include "int_poly.h" |
---|
| 26 | #include "canonicalform.h" |
---|
| 27 | #include "variable.h" |
---|
| 28 | #include "imm.h" |
---|
| 29 | |
---|
[f79b94c] | 30 | #ifdef HAVE_OMALLOC |
---|
| 31 | const omBin term::term_bin = omGetSpecBin(sizeof(term)); |
---|
| 32 | const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly)); |
---|
| 33 | #endif |
---|
[2dd068] | 34 | |
---|
| 35 | InternalPoly::InternalPoly( termList first, termList last, const Variable & v ) |
---|
| 36 | { |
---|
| 37 | firstTerm = first; |
---|
| 38 | lastTerm = last; |
---|
| 39 | var = v; |
---|
| 40 | } |
---|
| 41 | |
---|
| 42 | InternalPoly::InternalPoly() |
---|
| 43 | { |
---|
| 44 | ASSERT( 0, "ups, why do you initialize an empty poly" ); |
---|
| 45 | } |
---|
| 46 | |
---|
| 47 | InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c ) |
---|
| 48 | { |
---|
| 49 | var = v; |
---|
| 50 | firstTerm = new term( 0, c, e ); |
---|
| 51 | lastTerm = firstTerm; |
---|
| 52 | } |
---|
| 53 | |
---|
[c4682e0] | 54 | InternalPoly::InternalPoly( const InternalPoly& ):InternalCF() |
---|
[2dd068] | 55 | { |
---|
[32e9cd7] | 56 | ASSERT( 0, "ups there is something wrong in your code" ); |
---|
[e76d7a6] | 57 | } |
---|
[2dd068] | 58 | |
---|
| 59 | InternalPoly::~InternalPoly() |
---|
| 60 | { |
---|
| 61 | freeTermList( firstTerm ); |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | InternalCF* |
---|
| 65 | InternalPoly::deepCopyObject() const |
---|
| 66 | { |
---|
| 67 | termList first, last; |
---|
| 68 | first = deepCopyTermList( firstTerm, last ); |
---|
| 69 | return new InternalPoly( first, last, var ); |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | InternalCF* |
---|
| 73 | InternalPoly::genZero() |
---|
| 74 | { |
---|
| 75 | return firstTerm->coeff.genZero().getval(); |
---|
| 76 | } |
---|
| 77 | |
---|
| 78 | InternalCF* |
---|
| 79 | InternalPoly::genOne() |
---|
| 80 | { |
---|
| 81 | return firstTerm->coeff.genOne().getval(); |
---|
| 82 | } |
---|
| 83 | |
---|
| 84 | bool |
---|
| 85 | InternalPoly::isUnivariate() const |
---|
| 86 | { |
---|
| 87 | termList cursor = firstTerm; |
---|
[4ccbc25] | 88 | while ( cursor ) |
---|
| 89 | { |
---|
[a29d092] | 90 | if ( ! cursor->coeff.inCoeffDomain() ) |
---|
| 91 | return false; |
---|
| 92 | cursor = cursor->next; |
---|
[2dd068] | 93 | } |
---|
| 94 | return true; |
---|
| 95 | } |
---|
| 96 | |
---|
[791c0a] | 97 | //{{{ int InternalPoly::degree () |
---|
| 98 | // docu: see CanonicalForm::sign () |
---|
[2dd068] | 99 | int |
---|
[791c0a] | 100 | InternalPoly::degree () |
---|
[2dd068] | 101 | { |
---|
| 102 | return firstTerm->exp; |
---|
| 103 | } |
---|
[791c0a] | 104 | //}}} |
---|
[2dd068] | 105 | |
---|
[b761b9] | 106 | //{{{ int InternalPoly::sign () const |
---|
| 107 | // docu: see CanonicalForm::sign() |
---|
[2dd068] | 108 | int |
---|
[b761b9] | 109 | InternalPoly::sign () const |
---|
[2dd068] | 110 | { |
---|
| 111 | return firstTerm->coeff.sign(); |
---|
| 112 | } |
---|
[b761b9] | 113 | //}}} |
---|
[2dd068] | 114 | |
---|
[791c0a] | 115 | //{{{ CanonicalForm InternalPoly::lc (), Lc (), LC () |
---|
| 116 | // docu: see CanonicalForm::lc(), Lc(), LC() |
---|
[2dd068] | 117 | CanonicalForm |
---|
[791c0a] | 118 | InternalPoly::lc () |
---|
[2dd068] | 119 | { |
---|
| 120 | return firstTerm->coeff.lc(); |
---|
| 121 | } |
---|
| 122 | |
---|
| 123 | CanonicalForm |
---|
[791c0a] | 124 | InternalPoly::Lc () |
---|
[2dd068] | 125 | { |
---|
[791c0a] | 126 | return firstTerm->coeff.Lc(); |
---|
[2dd068] | 127 | } |
---|
| 128 | |
---|
[791c0a] | 129 | CanonicalForm |
---|
| 130 | InternalPoly::LC () |
---|
[2dd068] | 131 | { |
---|
[791c0a] | 132 | return firstTerm->coeff; |
---|
[2dd068] | 133 | } |
---|
[791c0a] | 134 | //}}} |
---|
[2dd068] | 135 | |
---|
[791c0a] | 136 | //{{{ CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree () |
---|
| 137 | // docu: see CanonicalForm::tailcoeff(), taildegree() |
---|
[2dd068] | 138 | CanonicalForm |
---|
[791c0a] | 139 | InternalPoly::tailcoeff () |
---|
[2dd068] | 140 | { |
---|
| 141 | return lastTerm->coeff; |
---|
| 142 | } |
---|
| 143 | |
---|
[791c0a] | 144 | int |
---|
| 145 | InternalPoly::taildegree () |
---|
| 146 | { |
---|
| 147 | return lastTerm->exp; |
---|
| 148 | } |
---|
| 149 | //}}} |
---|
| 150 | |
---|
[4e8da2] | 151 | //{{{ CanonicalForm InternalPoly::coeff ( int i ) |
---|
| 152 | // docu: see CanonicalForm::operator []() |
---|
[2dd068] | 153 | CanonicalForm |
---|
[4e8da2] | 154 | InternalPoly::coeff ( int i ) |
---|
[2dd068] | 155 | { |
---|
| 156 | termList theCursor = firstTerm; |
---|
[4ccbc25] | 157 | while ( theCursor ) |
---|
| 158 | { |
---|
[a29d092] | 159 | if ( theCursor->exp == i ) |
---|
| 160 | return theCursor->coeff; |
---|
| 161 | else if ( theCursor->exp < i ) |
---|
| 162 | return CanonicalForm( 0 ); |
---|
| 163 | else |
---|
| 164 | theCursor = theCursor->next; |
---|
[2dd068] | 165 | } |
---|
[4e8da2] | 166 | return CanonicalForm( 0 ); |
---|
[2dd068] | 167 | } |
---|
[4e8da2] | 168 | //}}} |
---|
[2dd068] | 169 | |
---|
[32e9cd7] | 170 | #ifndef NOSTREAMIO |
---|
[2dd068] | 171 | void |
---|
[181148] | 172 | InternalPoly::print(OSTREAM &aStream, char * aString ) |
---|
[2dd068] | 173 | { |
---|
[32e9cd7] | 174 | if ( ! firstTerm ) |
---|
[a29d092] | 175 | aStream << 0 << aString; |
---|
[4ccbc25] | 176 | else |
---|
| 177 | { |
---|
[a29d092] | 178 | char * theString; |
---|
| 179 | termList theCursor = firstTerm; |
---|
[4ccbc25] | 180 | while ( theCursor ) |
---|
| 181 | { |
---|
[a29d092] | 182 | ostrstream theStream; |
---|
| 183 | if ( theCursor->exp == 0 ) |
---|
| 184 | theCursor->coeff.print( aStream, aString ); |
---|
[4ccbc25] | 185 | else if ( theCursor->coeff.isOne() ) |
---|
| 186 | { |
---|
[a29d092] | 187 | aStream << var; |
---|
| 188 | if ( theCursor->exp != 1 ) |
---|
| 189 | aStream << '^' << theCursor->exp << aString; |
---|
| 190 | else |
---|
| 191 | aStream << aString; |
---|
| 192 | } |
---|
[4ccbc25] | 193 | else if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() ) |
---|
| 194 | { |
---|
[a29d092] | 195 | aStream << '-' << var; |
---|
| 196 | if ( theCursor->exp != 1 ) |
---|
| 197 | aStream << '^' << theCursor->exp << aString; |
---|
| 198 | else |
---|
| 199 | aStream << aString; |
---|
| 200 | } |
---|
[4ccbc25] | 201 | else |
---|
| 202 | { |
---|
[a29d092] | 203 | theStream << '*' << var; |
---|
| 204 | if ( theCursor->exp != 1 ) |
---|
| 205 | theStream << '^' << theCursor->exp << aString << ends; |
---|
| 206 | else |
---|
| 207 | theStream << aString << ends; // results from error in GNU strstream |
---|
| 208 | theString = theStream.str(); |
---|
| 209 | theCursor->coeff.print( aStream, theString ); |
---|
[8d1ad78] | 210 | theStream.freeze(0);//delete [] theString; |
---|
[a29d092] | 211 | } |
---|
| 212 | theCursor = theCursor->next; |
---|
| 213 | if ( theCursor && ( theCursor->coeff.sign() >= 0 ) ) |
---|
| 214 | aStream << '+'; |
---|
| 215 | } |
---|
[2dd068] | 216 | } |
---|
| 217 | } |
---|
[32e9cd7] | 218 | #endif /* NOSTREAMIO */ |
---|
[2dd068] | 219 | |
---|
[43a44b] | 220 | //{{{ InternalCF * InternalPoly::neg () |
---|
| 221 | // docu: see CanonicalForm::operator -() |
---|
| 222 | InternalCF * |
---|
| 223 | InternalPoly::neg () |
---|
[2dd068] | 224 | { |
---|
[8ce2d8c] | 225 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 226 | { |
---|
[a29d092] | 227 | negateTermList( firstTerm ); |
---|
| 228 | return this; |
---|
[4ccbc25] | 229 | } |
---|
| 230 | else |
---|
| 231 | { |
---|
[a29d092] | 232 | decRefCount(); |
---|
| 233 | termList last, first = copyTermList( firstTerm, last, true ); |
---|
| 234 | return new InternalPoly( first, last, var ); |
---|
[2dd068] | 235 | } |
---|
| 236 | } |
---|
[43a44b] | 237 | //}}} |
---|
[2dd068] | 238 | |
---|
| 239 | InternalCF* |
---|
| 240 | InternalPoly::invert() |
---|
| 241 | { |
---|
[4ccbc25] | 242 | if ( inExtension() && getReduce( var ) ) |
---|
| 243 | { |
---|
[a29d092] | 244 | setReduce( var, false ); |
---|
| 245 | CanonicalForm a( this->copyObject() ); |
---|
| 246 | CanonicalForm b = getMipo( var ); |
---|
| 247 | CanonicalForm u, v; |
---|
| 248 | CanonicalForm g = extgcd( a, b, u, v ); |
---|
| 249 | setReduce( var, true ); |
---|
| 250 | return u.getval(); |
---|
[2dd068] | 251 | } |
---|
| 252 | else |
---|
[a29d092] | 253 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 254 | } |
---|
| 255 | |
---|
[ec970e] | 256 | InternalCF* |
---|
| 257 | InternalPoly::tryInvert ( const CanonicalForm& M, bool& fail) |
---|
| 258 | { |
---|
| 259 | if ( inExtension() && !getReduce ( var ) ) |
---|
| 260 | { |
---|
| 261 | CanonicalForm b, inverse; |
---|
| 262 | CanonicalForm F ( this ->copyObject() ); |
---|
| 263 | Variable a = M.mvar(); |
---|
| 264 | Variable x = Variable(1); |
---|
| 265 | F= mod (F, M); //reduce mod M |
---|
| 266 | CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b ); |
---|
| 267 | if(!g.isOne()) |
---|
| 268 | fail = true; |
---|
| 269 | else |
---|
| 270 | inverse = replacevar( inverse, x, a ); // change back to alg var |
---|
| 271 | CanonicalForm test= mod (inverse*F, M); |
---|
| 272 | return inverse.getval(); |
---|
| 273 | } |
---|
| 274 | else |
---|
| 275 | return CFFactory::basic( 0 ); |
---|
| 276 | } |
---|
| 277 | |
---|
[2dd068] | 278 | InternalCF* |
---|
| 279 | InternalPoly::addsame( InternalCF* aCoeff ) |
---|
| 280 | { |
---|
| 281 | InternalPoly * aPoly = (InternalPoly*)aCoeff; |
---|
[8ce2d8c] | 282 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 283 | { |
---|
[a29d092] | 284 | firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false ); |
---|
| 285 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 286 | return this; |
---|
[4ccbc25] | 287 | else if ( firstTerm ) |
---|
| 288 | { |
---|
[a29d092] | 289 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 290 | delete this; |
---|
| 291 | return res; |
---|
| 292 | } |
---|
[4ccbc25] | 293 | else |
---|
| 294 | { |
---|
[a29d092] | 295 | delete this; |
---|
| 296 | return CFFactory::basic( 0 ); |
---|
| 297 | } |
---|
[2dd068] | 298 | } |
---|
[4ccbc25] | 299 | else |
---|
| 300 | { |
---|
[a29d092] | 301 | decRefCount(); |
---|
| 302 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 303 | first = addTermList( first, aPoly->firstTerm, last, false ); |
---|
| 304 | if ( first && first->exp != 0 ) |
---|
| 305 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 306 | else if ( first ) |
---|
| 307 | { |
---|
[a29d092] | 308 | InternalCF * res = first->coeff.getval(); |
---|
| 309 | delete first; |
---|
| 310 | return res; |
---|
| 311 | } |
---|
| 312 | else |
---|
| 313 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 314 | |
---|
| 315 | } |
---|
| 316 | } |
---|
| 317 | |
---|
| 318 | InternalCF* |
---|
| 319 | InternalPoly::subsame( InternalCF* aCoeff ) |
---|
| 320 | { |
---|
| 321 | InternalPoly * aPoly = (InternalPoly*)aCoeff; |
---|
[8ce2d8c] | 322 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 323 | { |
---|
[a29d092] | 324 | firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true ); |
---|
| 325 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 326 | return this; |
---|
[4ccbc25] | 327 | else if ( firstTerm ) |
---|
| 328 | { |
---|
[a29d092] | 329 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 330 | delete this; |
---|
| 331 | return res; |
---|
| 332 | } |
---|
[4ccbc25] | 333 | else |
---|
| 334 | { |
---|
[a29d092] | 335 | delete this; |
---|
| 336 | return CFFactory::basic( 0 ); |
---|
| 337 | } |
---|
[2dd068] | 338 | } |
---|
[4ccbc25] | 339 | else |
---|
| 340 | { |
---|
[a29d092] | 341 | decRefCount(); |
---|
| 342 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 343 | first = addTermList( first, aPoly->firstTerm, last, true ); |
---|
| 344 | if ( first && first->exp != 0 ) |
---|
| 345 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 346 | else if ( first ) |
---|
| 347 | { |
---|
[a29d092] | 348 | InternalCF * res = first->coeff.getval(); |
---|
| 349 | delete first; |
---|
| 350 | return res; |
---|
| 351 | } |
---|
| 352 | else |
---|
| 353 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 354 | |
---|
| 355 | } |
---|
| 356 | } |
---|
| 357 | |
---|
| 358 | InternalCF* |
---|
| 359 | InternalPoly::mulsame( InternalCF* aCoeff ) |
---|
| 360 | { |
---|
[778a4e] | 361 | if (is_imm(aCoeff)) return mulcoeff(aCoeff); |
---|
[2dd068] | 362 | InternalPoly *aPoly = (InternalPoly*)aCoeff; |
---|
| 363 | termList resultFirst = 0, resultLast = 0; |
---|
| 364 | termList theCursor = firstTerm; |
---|
| 365 | |
---|
[4ccbc25] | 366 | while ( theCursor ) |
---|
| 367 | { |
---|
| 368 | resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, |
---|
[778a4e] | 369 | theCursor->coeff, theCursor->exp, resultLast, false ); |
---|
[a29d092] | 370 | theCursor = theCursor->next; |
---|
[2dd068] | 371 | } |
---|
[4ccbc25] | 372 | if ( inExtension() && getReduce( var ) ) |
---|
| 373 | { |
---|
[a29d092] | 374 | resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast ); |
---|
| 375 | if ( resultFirst == 0 ) |
---|
[ac8e1a] | 376 | { |
---|
[8ce2d8c] | 377 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 378 | { |
---|
[a29d092] | 379 | delete this; |
---|
| 380 | return CFFactory::basic(0); |
---|
| 381 | } |
---|
[4ccbc25] | 382 | else |
---|
| 383 | { |
---|
[a29d092] | 384 | decRefCount(); |
---|
| 385 | return CFFactory::basic(0); |
---|
| 386 | } |
---|
[ac8e1a] | 387 | } |
---|
[a29d092] | 388 | else if ( resultFirst->exp == 0 ) |
---|
[ac8e1a] | 389 | { |
---|
[8ce2d8c] | 390 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 391 | { |
---|
[a29d092] | 392 | InternalCF * res = resultFirst->coeff.getval(); |
---|
| 393 | delete resultFirst; |
---|
| 394 | delete this; |
---|
| 395 | return res; |
---|
| 396 | } |
---|
[4ccbc25] | 397 | else |
---|
| 398 | { |
---|
[a29d092] | 399 | decRefCount(); |
---|
| 400 | InternalCF * res = resultFirst->coeff.getval(); |
---|
| 401 | delete resultFirst; |
---|
| 402 | return res; |
---|
| 403 | } |
---|
[ac8e1a] | 404 | } |
---|
[2dd068] | 405 | } |
---|
[8ce2d8c] | 406 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 407 | { |
---|
[a29d092] | 408 | freeTermList( firstTerm ); |
---|
| 409 | firstTerm = resultFirst; |
---|
| 410 | lastTerm = resultLast; |
---|
| 411 | return this; |
---|
[2dd068] | 412 | } |
---|
[4ccbc25] | 413 | else |
---|
| 414 | { |
---|
[a29d092] | 415 | decRefCount(); |
---|
| 416 | return new InternalPoly( resultFirst, resultLast, var ); |
---|
[2dd068] | 417 | } |
---|
| 418 | } |
---|
| 419 | |
---|
[ec970e] | 420 | InternalCF* |
---|
| 421 | InternalPoly::tryMulsame( InternalCF* aCoeff, const CanonicalForm& M) |
---|
| 422 | { |
---|
| 423 | if (is_imm(aCoeff)) |
---|
| 424 | return mulcoeff(aCoeff); |
---|
| 425 | InternalPoly *aPoly = (InternalPoly*)aCoeff; |
---|
| 426 | termList resultFirst = 0, resultLast = 0; |
---|
| 427 | termList theCursor = firstTerm; |
---|
| 428 | |
---|
| 429 | while ( theCursor ) |
---|
| 430 | { |
---|
| 431 | resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, |
---|
| 432 | theCursor->coeff, theCursor->exp, resultLast, false ); |
---|
| 433 | theCursor = theCursor->next; |
---|
| 434 | } |
---|
| 435 | if ( inExtension() && !getReduce( var ) ) |
---|
| 436 | { |
---|
| 437 | resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast); |
---|
| 438 | if ( resultFirst == 0 ) |
---|
| 439 | { |
---|
| 440 | if ( getRefCount() <= 1 ) |
---|
| 441 | { |
---|
| 442 | delete this; |
---|
| 443 | return CFFactory::basic(0); |
---|
| 444 | } |
---|
| 445 | else |
---|
| 446 | { |
---|
| 447 | decRefCount(); |
---|
| 448 | return CFFactory::basic(0); |
---|
| 449 | } |
---|
| 450 | } |
---|
| 451 | else if ( resultFirst->exp == 0 ) |
---|
| 452 | { |
---|
| 453 | if ( getRefCount() <= 1 ) |
---|
| 454 | { |
---|
| 455 | InternalCF * res = resultFirst->coeff.getval(); |
---|
| 456 | delete resultFirst; |
---|
| 457 | delete this; |
---|
| 458 | return res; |
---|
| 459 | } |
---|
| 460 | else |
---|
| 461 | { |
---|
| 462 | decRefCount(); |
---|
| 463 | InternalCF * res = resultFirst->coeff.getval(); |
---|
| 464 | delete resultFirst; |
---|
| 465 | return res; |
---|
| 466 | } |
---|
| 467 | } |
---|
| 468 | } |
---|
| 469 | if ( getRefCount() <= 1 ) |
---|
| 470 | { |
---|
| 471 | freeTermList( firstTerm ); |
---|
| 472 | firstTerm = resultFirst; |
---|
| 473 | lastTerm = resultLast; |
---|
| 474 | return this; |
---|
| 475 | } |
---|
| 476 | else |
---|
| 477 | { |
---|
| 478 | decRefCount(); |
---|
| 479 | return new InternalPoly( resultFirst, resultLast, var ); |
---|
| 480 | } |
---|
| 481 | } |
---|
| 482 | |
---|
[2dd068] | 483 | InternalCF* |
---|
| 484 | InternalPoly::dividesame( InternalCF* aCoeff ) |
---|
| 485 | { |
---|
| 486 | return divsame( aCoeff ); |
---|
| 487 | } |
---|
| 488 | |
---|
| 489 | |
---|
| 490 | InternalCF* |
---|
| 491 | InternalPoly::divsame( InternalCF* aCoeff ) |
---|
| 492 | { |
---|
[4ccbc25] | 493 | if ( inExtension() && getReduce( var ) ) |
---|
| 494 | { |
---|
[a29d092] | 495 | InternalCF * dummy = aCoeff->invert(); |
---|
[778a4e] | 496 | if (is_imm(dummy)) dummy=this->mulsame(dummy); |
---|
| 497 | else dummy = dummy->mulsame( this ); |
---|
[8ce2d8c] | 498 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 499 | { |
---|
[a29d092] | 500 | delete this; |
---|
| 501 | return dummy; |
---|
| 502 | } |
---|
[4ccbc25] | 503 | else |
---|
| 504 | { |
---|
[a29d092] | 505 | decRefCount(); |
---|
| 506 | return dummy; |
---|
| 507 | } |
---|
[2dd068] | 508 | } |
---|
| 509 | InternalPoly *aPoly = (InternalPoly*)aCoeff; |
---|
| 510 | termList dummy, first, last, resultfirst = 0, resultlast = 0; |
---|
| 511 | CanonicalForm coeff, newcoeff; |
---|
| 512 | int exp, newexp; |
---|
| 513 | bool singleObject; |
---|
| 514 | |
---|
[8ce2d8c] | 515 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 516 | { |
---|
[a29d092] | 517 | first = firstTerm; last = lastTerm; singleObject = true; |
---|
[2dd068] | 518 | } |
---|
[4ccbc25] | 519 | else |
---|
| 520 | { |
---|
[a29d092] | 521 | first = copyTermList( firstTerm, last ); singleObject = false; |
---|
| 522 | decRefCount(); |
---|
[2dd068] | 523 | } |
---|
| 524 | coeff = aPoly->firstTerm->coeff; |
---|
| 525 | exp = aPoly->firstTerm->exp; |
---|
[4ccbc25] | 526 | while (first && ( first->exp >= exp ) ) |
---|
| 527 | { |
---|
[a29d092] | 528 | newcoeff = first->coeff / coeff; |
---|
| 529 | newexp = first->exp - exp; |
---|
| 530 | dummy = first; |
---|
| 531 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 532 | delete dummy; |
---|
| 533 | appendTermList( resultfirst, resultlast, newcoeff, newexp ); |
---|
[2dd068] | 534 | } |
---|
| 535 | freeTermList( first ); |
---|
[4ccbc25] | 536 | if ( singleObject ) |
---|
| 537 | { |
---|
| 538 | if ( resultfirst && resultfirst->exp != 0 ) |
---|
| 539 | { |
---|
[a29d092] | 540 | firstTerm = resultfirst; |
---|
| 541 | lastTerm = resultlast; |
---|
| 542 | return this; |
---|
| 543 | } |
---|
[4ccbc25] | 544 | else if ( resultfirst ) |
---|
| 545 | { |
---|
[a29d092] | 546 | InternalCF * res = resultfirst->coeff.getval(); |
---|
| 547 | delete resultfirst; |
---|
| 548 | firstTerm = 0; |
---|
| 549 | delete this; |
---|
| 550 | return res; |
---|
| 551 | } |
---|
[4ccbc25] | 552 | else |
---|
| 553 | { |
---|
[a29d092] | 554 | // this should not happen (evtl use assertion) |
---|
| 555 | ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" ); |
---|
| 556 | firstTerm = 0; |
---|
| 557 | delete this; |
---|
| 558 | return CFFactory::basic( 0 ); |
---|
| 559 | } |
---|
[2dd068] | 560 | } |
---|
[4ccbc25] | 561 | else |
---|
| 562 | { |
---|
[a29d092] | 563 | if ( resultfirst && resultfirst->exp != 0 ) |
---|
| 564 | return new InternalPoly( resultfirst, resultlast, var ); |
---|
[4ccbc25] | 565 | else if ( resultfirst ) |
---|
| 566 | { |
---|
[a29d092] | 567 | InternalCF * res = resultfirst->coeff.getval(); |
---|
| 568 | delete resultfirst; |
---|
| 569 | return res; |
---|
| 570 | } |
---|
| 571 | else |
---|
| 572 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 573 | } |
---|
| 574 | } |
---|
| 575 | |
---|
[ec970e] | 576 | InternalCF* |
---|
| 577 | InternalPoly::tryDivsame( InternalCF* aCoeff, const CanonicalForm& M, bool& fail ) |
---|
| 578 | { |
---|
| 579 | if ( inExtension() && !getReduce( var ) ) |
---|
| 580 | { |
---|
| 581 | InternalCF * dummy = aCoeff->tryInvert(M, fail); |
---|
| 582 | if (fail) |
---|
| 583 | return CFFactory::basic( 0 ); |
---|
| 584 | if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M); |
---|
| 585 | else dummy = dummy->tryMulsame( this, M); |
---|
| 586 | if (fail) |
---|
| 587 | { |
---|
| 588 | if (getRefCount() <= 1) |
---|
| 589 | delete this; |
---|
| 590 | else |
---|
| 591 | decRefCount(); |
---|
| 592 | return dummy; |
---|
| 593 | } |
---|
| 594 | if ( getRefCount() <= 1 ) |
---|
| 595 | { |
---|
| 596 | delete this; |
---|
| 597 | return dummy; |
---|
| 598 | } |
---|
| 599 | else |
---|
| 600 | { |
---|
| 601 | decRefCount(); |
---|
| 602 | return dummy; |
---|
| 603 | } |
---|
| 604 | } |
---|
| 605 | InternalPoly *aPoly = (InternalPoly*)aCoeff; |
---|
| 606 | termList dummy, first, last, resultfirst = 0, resultlast = 0; |
---|
| 607 | CanonicalForm coeff, newcoeff; |
---|
| 608 | int exp, newexp; |
---|
| 609 | bool singleObject; |
---|
| 610 | |
---|
| 611 | if ( getRefCount() <= 1 ) |
---|
| 612 | { |
---|
| 613 | first = firstTerm; last = lastTerm; singleObject = true; |
---|
| 614 | } |
---|
| 615 | else |
---|
| 616 | { |
---|
| 617 | first = copyTermList( firstTerm, last ); singleObject = false; |
---|
| 618 | decRefCount(); |
---|
| 619 | } |
---|
| 620 | coeff = aPoly->firstTerm->coeff; |
---|
| 621 | exp = aPoly->firstTerm->exp; |
---|
| 622 | while (first && ( first->exp >= exp ) ) |
---|
| 623 | { |
---|
| 624 | newcoeff= first->coeff.tryDiv (coeff, M, fail); |
---|
| 625 | if (fail) |
---|
| 626 | { |
---|
| 627 | freeTermList (first); |
---|
| 628 | return CFFactory::basic (0); |
---|
| 629 | } |
---|
| 630 | newcoeff= reduce (newcoeff, M); |
---|
| 631 | newexp = first->exp - exp; |
---|
| 632 | dummy = first; |
---|
| 633 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 634 | delete dummy; |
---|
| 635 | if (!newcoeff.isZero()) |
---|
| 636 | appendTermList( resultfirst, resultlast, newcoeff, newexp ); |
---|
| 637 | } |
---|
| 638 | freeTermList( first ); |
---|
| 639 | if ( singleObject ) |
---|
| 640 | { |
---|
| 641 | if ( resultfirst && resultfirst->exp != 0 ) |
---|
| 642 | { |
---|
| 643 | firstTerm = resultfirst; |
---|
| 644 | lastTerm = resultlast; |
---|
| 645 | return this; |
---|
| 646 | } |
---|
| 647 | else if ( resultfirst ) |
---|
| 648 | { |
---|
| 649 | InternalCF * res = resultfirst->coeff.getval(); |
---|
| 650 | delete resultfirst; |
---|
| 651 | firstTerm = 0; |
---|
| 652 | delete this; |
---|
| 653 | return res; |
---|
| 654 | } |
---|
| 655 | else |
---|
| 656 | { |
---|
| 657 | // this should not happen (evtl use assertion) |
---|
| 658 | ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" ); |
---|
| 659 | firstTerm = 0; |
---|
| 660 | delete this; |
---|
| 661 | return CFFactory::basic( 0 ); |
---|
| 662 | } |
---|
| 663 | } |
---|
| 664 | else |
---|
| 665 | { |
---|
| 666 | if ( resultfirst && resultfirst->exp != 0 ) |
---|
| 667 | return new InternalPoly( resultfirst, resultlast, var ); |
---|
| 668 | else if ( resultfirst ) |
---|
| 669 | { |
---|
| 670 | InternalCF * res = resultfirst->coeff.getval(); |
---|
| 671 | delete resultfirst; |
---|
| 672 | return res; |
---|
| 673 | } |
---|
| 674 | else |
---|
| 675 | return CFFactory::basic( 0 ); |
---|
| 676 | } |
---|
| 677 | } |
---|
| 678 | |
---|
[2dd068] | 679 | InternalCF* |
---|
| 680 | InternalPoly::modulosame( InternalCF* aCoeff ) |
---|
| 681 | { |
---|
| 682 | return modsame( aCoeff ); |
---|
| 683 | } |
---|
| 684 | |
---|
| 685 | InternalCF* |
---|
| 686 | InternalPoly::modsame( InternalCF* aCoeff ) |
---|
| 687 | { |
---|
[4ccbc25] | 688 | if ( inExtension() && getReduce( var ) ) |
---|
| 689 | { |
---|
[a29d092] | 690 | if ( deleteObject() ) delete this; |
---|
| 691 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 692 | } |
---|
| 693 | InternalPoly *aPoly = (InternalPoly*)aCoeff; |
---|
| 694 | termList dummy, first, last; |
---|
| 695 | CanonicalForm coeff, newcoeff; |
---|
| 696 | int exp, newexp; |
---|
| 697 | bool singleObject; |
---|
| 698 | |
---|
[8ce2d8c] | 699 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 700 | { |
---|
[a29d092] | 701 | first = firstTerm; last = lastTerm; singleObject = true; |
---|
[2dd068] | 702 | } |
---|
[4ccbc25] | 703 | else |
---|
| 704 | { |
---|
[a29d092] | 705 | first = copyTermList( firstTerm, last ); singleObject = false; |
---|
| 706 | decRefCount(); |
---|
[2dd068] | 707 | } |
---|
| 708 | coeff = aPoly->firstTerm->coeff; |
---|
| 709 | exp = aPoly->firstTerm->exp; |
---|
[4ccbc25] | 710 | while (first && ( first->exp >= exp ) ) |
---|
| 711 | { |
---|
[a29d092] | 712 | newcoeff = first->coeff / coeff; |
---|
| 713 | newexp = first->exp - exp; |
---|
| 714 | dummy = first; |
---|
| 715 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 716 | delete dummy; |
---|
[2dd068] | 717 | } |
---|
[4ccbc25] | 718 | if ( singleObject ) |
---|
| 719 | { |
---|
| 720 | if ( first && first->exp != 0 ) |
---|
| 721 | { |
---|
[a29d092] | 722 | firstTerm = first; |
---|
| 723 | lastTerm = last; |
---|
| 724 | return this; |
---|
| 725 | } |
---|
[4ccbc25] | 726 | else if ( first ) |
---|
| 727 | { |
---|
[a29d092] | 728 | InternalCF * res = first->coeff.getval(); |
---|
| 729 | delete first; |
---|
| 730 | firstTerm = 0; |
---|
| 731 | delete this; |
---|
| 732 | return res; |
---|
| 733 | } |
---|
[4ccbc25] | 734 | else |
---|
| 735 | { |
---|
[a29d092] | 736 | firstTerm = 0; |
---|
| 737 | delete this; |
---|
| 738 | return CFFactory::basic( 0 ); |
---|
| 739 | } |
---|
[2dd068] | 740 | } |
---|
[4ccbc25] | 741 | else |
---|
| 742 | { |
---|
[a29d092] | 743 | if ( first && first->exp != 0 ) |
---|
| 744 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 745 | else if ( first ) |
---|
| 746 | { |
---|
[a29d092] | 747 | InternalCF * res = first->coeff.getval(); |
---|
| 748 | delete first; |
---|
| 749 | return res; |
---|
| 750 | } |
---|
| 751 | else |
---|
| 752 | return CFFactory::basic( 0 ); |
---|
[2dd068] | 753 | } |
---|
| 754 | } |
---|
| 755 | |
---|
| 756 | |
---|
| 757 | void |
---|
| 758 | InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem ) |
---|
| 759 | { |
---|
[4ccbc25] | 760 | if ( inExtension() && getReduce( var ) ) |
---|
| 761 | { |
---|
[a29d092] | 762 | InternalCF * dummy = acoeff->invert(); |
---|
| 763 | quot = dummy->mulsame( this ); |
---|
| 764 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 765 | } |
---|
[4ccbc25] | 766 | else |
---|
| 767 | { |
---|
[a29d092] | 768 | InternalPoly *aPoly = (InternalPoly*)acoeff; |
---|
| 769 | termList dummy, first, last, resultfirst = 0, resultlast = 0; |
---|
| 770 | CanonicalForm coeff, newcoeff; |
---|
| 771 | int exp, newexp; |
---|
| 772 | |
---|
| 773 | first = copyTermList( firstTerm, last ); |
---|
| 774 | |
---|
| 775 | coeff = aPoly->firstTerm->coeff; |
---|
| 776 | exp = aPoly->firstTerm->exp; |
---|
[4ccbc25] | 777 | while (first && ( first->exp >= exp ) ) |
---|
| 778 | { |
---|
[a29d092] | 779 | newcoeff = first->coeff / coeff; |
---|
| 780 | newexp = first->exp - exp; |
---|
| 781 | dummy = first; |
---|
| 782 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 783 | delete dummy; |
---|
| 784 | appendTermList( resultfirst, resultlast, newcoeff, newexp ); |
---|
| 785 | } |
---|
| 786 | if ( resultfirst ) |
---|
[4ccbc25] | 787 | if ( resultfirst->exp == 0 ) |
---|
| 788 | { |
---|
[a29d092] | 789 | quot = resultfirst->coeff.getval(); |
---|
| 790 | delete resultfirst; |
---|
| 791 | } |
---|
| 792 | else |
---|
| 793 | quot = new InternalPoly( resultfirst, resultlast, var ); |
---|
| 794 | else |
---|
| 795 | quot = CFFactory::basic( 0 ); |
---|
| 796 | if ( first ) |
---|
[4ccbc25] | 797 | if ( first->exp == 0 ) |
---|
| 798 | { |
---|
[a29d092] | 799 | rem = first->coeff.getval(); |
---|
| 800 | delete first; |
---|
| 801 | } |
---|
| 802 | else |
---|
| 803 | rem = new InternalPoly( first, last, var ); |
---|
| 804 | else |
---|
| 805 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 806 | } |
---|
| 807 | } |
---|
| 808 | |
---|
| 809 | bool |
---|
| 810 | InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem ) |
---|
| 811 | { |
---|
[4ccbc25] | 812 | if ( inExtension() && getReduce( var ) ) |
---|
| 813 | { |
---|
[a29d092] | 814 | divremsame( acoeff, quot, rem ); |
---|
| 815 | return true; |
---|
[2dd068] | 816 | } |
---|
| 817 | InternalPoly *aPoly = (InternalPoly*)acoeff; |
---|
| 818 | termList dummy, first, last, resultfirst = 0, resultlast = 0; |
---|
| 819 | CanonicalForm coeff, newcoeff, dummycoeff; |
---|
| 820 | int exp, newexp; |
---|
| 821 | bool divideok = true; |
---|
| 822 | |
---|
| 823 | // if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) ) |
---|
[a29d092] | 824 | // return false; |
---|
[2dd068] | 825 | |
---|
| 826 | first = copyTermList( firstTerm, last ); |
---|
| 827 | |
---|
| 828 | coeff = aPoly->firstTerm->coeff; |
---|
| 829 | exp = aPoly->firstTerm->exp; |
---|
[4ccbc25] | 830 | while (first && ( first->exp >= exp ) && divideok ) |
---|
| 831 | { |
---|
[6b503c] | 832 | divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff ); |
---|
[4ccbc25] | 833 | if ( divideok && dummycoeff.isZero() ) |
---|
| 834 | { |
---|
[a29d092] | 835 | newexp = first->exp - exp; |
---|
| 836 | dummy = first; |
---|
| 837 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 838 | delete dummy; |
---|
| 839 | appendTermList( resultfirst, resultlast, newcoeff, newexp ); |
---|
| 840 | } |
---|
| 841 | else |
---|
| 842 | divideok = false; |
---|
[2dd068] | 843 | } |
---|
[4ccbc25] | 844 | if ( divideok ) |
---|
| 845 | { |
---|
[a29d092] | 846 | if ( resultfirst ) |
---|
[4ccbc25] | 847 | if ( resultfirst->exp == 0 ) |
---|
| 848 | { |
---|
[a29d092] | 849 | quot = resultfirst->coeff.getval(); |
---|
| 850 | delete resultfirst; |
---|
| 851 | } |
---|
| 852 | else |
---|
| 853 | quot = new InternalPoly( resultfirst, resultlast, var ); |
---|
| 854 | else |
---|
| 855 | quot = CFFactory::basic( 0 ); |
---|
| 856 | if ( first ) |
---|
[4ccbc25] | 857 | if ( first->exp == 0 ) |
---|
| 858 | { |
---|
[a29d092] | 859 | rem = first->coeff.getval(); |
---|
| 860 | delete first; |
---|
| 861 | } |
---|
| 862 | else |
---|
| 863 | rem = new InternalPoly( first, last, var ); |
---|
| 864 | else |
---|
| 865 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 866 | } |
---|
[4ccbc25] | 867 | else |
---|
| 868 | { |
---|
[a29d092] | 869 | freeTermList( resultfirst ); |
---|
| 870 | freeTermList( first ); |
---|
[2dd068] | 871 | } |
---|
| 872 | return divideok; |
---|
| 873 | } |
---|
| 874 | |
---|
[ec970e] | 875 | bool |
---|
| 876 | InternalPoly::tryDivremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem, const CanonicalForm& M, bool& fail) |
---|
| 877 | { |
---|
| 878 | if (inExtension() && !getReduce (var)) |
---|
| 879 | { |
---|
| 880 | InternalCF * dummy = acoeff->tryInvert(M, fail); |
---|
| 881 | if (fail) |
---|
| 882 | return false; |
---|
| 883 | quot = dummy->tryMulsame( this, M); |
---|
| 884 | rem = CFFactory::basic( 0 ); |
---|
| 885 | if (fail) |
---|
| 886 | return false; |
---|
| 887 | return true; |
---|
| 888 | } |
---|
| 889 | InternalPoly *aPoly = (InternalPoly*)acoeff; |
---|
| 890 | termList dummy, first, last, resultfirst = 0, resultlast = 0; |
---|
| 891 | CanonicalForm coeff, newcoeff, dummycoeff; |
---|
| 892 | int exp, newexp; |
---|
| 893 | bool divideok = true; |
---|
| 894 | |
---|
| 895 | first = copyTermList( firstTerm, last ); |
---|
| 896 | |
---|
| 897 | coeff = aPoly->firstTerm->coeff; |
---|
| 898 | exp = aPoly->firstTerm->exp; |
---|
| 899 | while (first && ( first->exp >= exp ) && divideok ) |
---|
| 900 | { |
---|
| 901 | divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail ); |
---|
| 902 | if (fail) |
---|
| 903 | { |
---|
| 904 | freeTermList (first); |
---|
| 905 | return false; |
---|
| 906 | } |
---|
| 907 | if ( divideok && dummycoeff.isZero() ) |
---|
| 908 | { |
---|
| 909 | newexp = first->exp - exp; |
---|
| 910 | dummy = first; |
---|
| 911 | first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true ); |
---|
| 912 | delete dummy; |
---|
| 913 | if (!newcoeff.isZero()) |
---|
| 914 | appendTermList( resultfirst, resultlast, newcoeff, newexp ); |
---|
| 915 | } |
---|
| 916 | else |
---|
| 917 | divideok = false; |
---|
| 918 | } |
---|
| 919 | if ( divideok ) |
---|
| 920 | { |
---|
| 921 | if ( resultfirst ) |
---|
| 922 | if ( resultfirst->exp == 0 ) |
---|
| 923 | { |
---|
| 924 | quot = resultfirst->coeff.getval(); |
---|
| 925 | delete resultfirst; |
---|
| 926 | } |
---|
| 927 | else |
---|
| 928 | quot = new InternalPoly( resultfirst, resultlast, var ); |
---|
| 929 | else |
---|
| 930 | quot = CFFactory::basic( 0 ); |
---|
| 931 | if ( first ) |
---|
| 932 | if ( first->exp == 0 ) |
---|
| 933 | { |
---|
| 934 | rem = first->coeff.getval(); |
---|
| 935 | delete first; |
---|
| 936 | } |
---|
| 937 | else |
---|
| 938 | { |
---|
| 939 | if (first->coeff.isZero()) |
---|
| 940 | { |
---|
| 941 | rem= CFFactory::basic (0); |
---|
| 942 | delete first; |
---|
| 943 | } |
---|
| 944 | else |
---|
| 945 | rem = new InternalPoly( first, last, var ); |
---|
| 946 | } |
---|
| 947 | else |
---|
| 948 | rem = CFFactory::basic( 0 ); |
---|
| 949 | } |
---|
| 950 | else |
---|
| 951 | { |
---|
| 952 | freeTermList( resultfirst ); |
---|
| 953 | freeTermList( first ); |
---|
| 954 | } |
---|
| 955 | return divideok; |
---|
| 956 | } |
---|
| 957 | |
---|
[2085fc] | 958 | //{{{ int InternalPoly::comparesame, comparecoeff ( InternalCF * acoeff ) |
---|
| 959 | //{{{ docu |
---|
| 960 | // |
---|
| 961 | // comparesame(), comparecoeff() - compare with an |
---|
| 962 | // InternalPoly. |
---|
| 963 | // |
---|
| 964 | // comparecoeff() always returns 1 since CO is defined to be |
---|
| 965 | // larger than anything which is a coefficient w.r.t. CO. |
---|
| 966 | // |
---|
| 967 | // comparesame() compares the coefficient vectors of f=CO and |
---|
| 968 | // g=acoeff w.r.t to a lexicographic order in the following way: |
---|
[a29d092] | 969 | // f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t. |
---|
[2085fc] | 970 | // i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and |
---|
| 971 | // ii) g[i] occurs in g (i.e. is not equal to zero) and |
---|
| 972 | // f[i] does not occur in f or f[i] < g[i] if f[i] occurs |
---|
| 973 | // where f[i] denotes the coefficient to the power x^i of f. |
---|
| 974 | // |
---|
| 975 | // As usual, comparesame() returns 1 if CO is larger than c, 0 if |
---|
| 976 | // CO equals c, and -1 if CO is less than c. However, this |
---|
| 977 | // function is optimized to test on equality since this is its |
---|
| 978 | // most important and frequent usage. |
---|
| 979 | // |
---|
| 980 | // See the respective `CanonicalForm'-methods for an explanation |
---|
| 981 | // why we define such a strange (but total) ordering on |
---|
| 982 | // polynomials. |
---|
| 983 | // |
---|
[7d9585] | 984 | // See also: CanonicalForm::operator <(), CanonicalForm::operator ==() |
---|
| 985 | // |
---|
[2085fc] | 986 | //}}} |
---|
[2dd068] | 987 | int |
---|
[2085fc] | 988 | InternalPoly::comparesame ( InternalCF * acoeff ) |
---|
| 989 | { |
---|
| 990 | ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" ); |
---|
| 991 | InternalPoly* apoly = (InternalPoly*)acoeff; |
---|
| 992 | // check on triviality |
---|
| 993 | if ( this == apoly ) |
---|
[a29d092] | 994 | return 0; |
---|
[4ccbc25] | 995 | else |
---|
| 996 | { |
---|
[a29d092] | 997 | termList cursor1 = firstTerm; |
---|
| 998 | termList cursor2 = apoly->firstTerm; |
---|
| 999 | for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next ) |
---|
| 1000 | // we test on inequality of coefficients at this |
---|
| 1001 | // point instead of testing on "less than" at the |
---|
| 1002 | // last `else' in the enclosed `if' statement since a |
---|
| 1003 | // test on inequaltiy in general is cheaper |
---|
| 1004 | if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) ) |
---|
[ac8e1a] | 1005 | { |
---|
[a29d092] | 1006 | if ( cursor1->exp > cursor2->exp ) |
---|
| 1007 | return 1; |
---|
| 1008 | else if ( cursor1->exp < cursor2->exp ) |
---|
| 1009 | return -1; |
---|
| 1010 | else if ( cursor1->coeff > cursor2->coeff ) |
---|
| 1011 | return 1; |
---|
| 1012 | else |
---|
| 1013 | return -1; |
---|
[ac8e1a] | 1014 | } |
---|
[a29d092] | 1015 | // check trailing terms |
---|
| 1016 | if ( cursor1 == cursor2 ) |
---|
| 1017 | return 0; |
---|
| 1018 | else if ( cursor1 != 0 ) |
---|
| 1019 | return 1; |
---|
| 1020 | else |
---|
| 1021 | return -1; |
---|
[2085fc] | 1022 | } |
---|
| 1023 | } |
---|
| 1024 | |
---|
| 1025 | int |
---|
| 1026 | InternalPoly::comparecoeff ( InternalCF * ) |
---|
[2dd068] | 1027 | { |
---|
| 1028 | return 1; |
---|
| 1029 | } |
---|
[2085fc] | 1030 | //}}} |
---|
[2dd068] | 1031 | |
---|
| 1032 | InternalCF* |
---|
| 1033 | InternalPoly::addcoeff( InternalCF* cc ) |
---|
| 1034 | { |
---|
| 1035 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1036 | if ( c.isZero() ) |
---|
[a29d092] | 1037 | return this; |
---|
[4ccbc25] | 1038 | else |
---|
| 1039 | { |
---|
[8ce2d8c] | 1040 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1041 | { |
---|
| 1042 | if ( lastTerm->exp == 0 ) |
---|
| 1043 | { |
---|
[a29d092] | 1044 | lastTerm->coeff += c; |
---|
[4ccbc25] | 1045 | if ( lastTerm->coeff.isZero() ) |
---|
| 1046 | { |
---|
[a29d092] | 1047 | termList cursor = firstTerm; |
---|
| 1048 | while ( cursor->next != lastTerm ) |
---|
| 1049 | cursor = cursor->next; |
---|
| 1050 | delete lastTerm; |
---|
| 1051 | cursor->next = 0; |
---|
| 1052 | lastTerm = cursor; |
---|
| 1053 | } |
---|
| 1054 | } |
---|
[4ccbc25] | 1055 | else |
---|
| 1056 | { |
---|
[a29d092] | 1057 | lastTerm->next = new term( 0, c, 0 ); |
---|
| 1058 | lastTerm = lastTerm->next; |
---|
| 1059 | } |
---|
| 1060 | return this; |
---|
| 1061 | } |
---|
[4ccbc25] | 1062 | else |
---|
| 1063 | { |
---|
[a29d092] | 1064 | decRefCount(); |
---|
| 1065 | termList last, first = copyTermList( firstTerm, last, false ); |
---|
[4ccbc25] | 1066 | if ( last->exp == 0 ) |
---|
| 1067 | { |
---|
[a29d092] | 1068 | last->coeff += c; |
---|
[4ccbc25] | 1069 | if ( last->coeff.isZero() ) |
---|
| 1070 | { |
---|
[a29d092] | 1071 | termList cursor = first; |
---|
| 1072 | while ( cursor->next != last ) |
---|
| 1073 | cursor = cursor->next; |
---|
| 1074 | delete last; |
---|
| 1075 | cursor->next = 0; |
---|
| 1076 | last = cursor; |
---|
| 1077 | } |
---|
| 1078 | } |
---|
[4ccbc25] | 1079 | else |
---|
| 1080 | { |
---|
[a29d092] | 1081 | last->next = new term( 0, c, 0 ); |
---|
| 1082 | last = last->next; |
---|
| 1083 | } |
---|
| 1084 | return new InternalPoly( first, last, var ); |
---|
| 1085 | } |
---|
[2dd068] | 1086 | } |
---|
| 1087 | } |
---|
| 1088 | |
---|
| 1089 | InternalCF* |
---|
| 1090 | InternalPoly::subcoeff( InternalCF* cc, bool negate ) |
---|
| 1091 | { |
---|
| 1092 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1093 | if ( c.isZero() ) |
---|
[4ccbc25] | 1094 | if ( getRefCount() > 1 ) |
---|
| 1095 | { |
---|
[a29d092] | 1096 | decRefCount(); |
---|
| 1097 | termList last, first = copyTermList( firstTerm, last, negate ); |
---|
| 1098 | return new InternalPoly( first, last, var ); |
---|
| 1099 | } |
---|
[4ccbc25] | 1100 | else |
---|
| 1101 | { |
---|
[a29d092] | 1102 | if ( negate ) |
---|
| 1103 | negateTermList( firstTerm ); |
---|
| 1104 | return this; |
---|
| 1105 | } |
---|
[4ccbc25] | 1106 | else |
---|
| 1107 | { |
---|
[8ce2d8c] | 1108 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1109 | { |
---|
| 1110 | if ( lastTerm->exp == 0 ) |
---|
| 1111 | { |
---|
| 1112 | if ( negate ) |
---|
| 1113 | { |
---|
[a29d092] | 1114 | negateTermList( firstTerm ); |
---|
| 1115 | lastTerm->coeff += c; |
---|
| 1116 | } |
---|
| 1117 | else |
---|
| 1118 | lastTerm->coeff -= c; |
---|
[4ccbc25] | 1119 | if ( lastTerm->coeff.isZero() ) |
---|
| 1120 | { |
---|
[a29d092] | 1121 | termList cursor = firstTerm; |
---|
| 1122 | while ( cursor->next != lastTerm ) |
---|
| 1123 | cursor = cursor->next; |
---|
| 1124 | delete lastTerm; |
---|
| 1125 | cursor->next = 0; |
---|
| 1126 | lastTerm = cursor; |
---|
| 1127 | } |
---|
| 1128 | } |
---|
[4ccbc25] | 1129 | else |
---|
| 1130 | { |
---|
| 1131 | if ( negate ) |
---|
| 1132 | { |
---|
[a29d092] | 1133 | negateTermList( firstTerm ); |
---|
| 1134 | lastTerm->next = new term( 0, c, 0 ); |
---|
| 1135 | } |
---|
| 1136 | else |
---|
| 1137 | lastTerm->next = new term( 0, -c, 0 ); |
---|
| 1138 | lastTerm = lastTerm->next; |
---|
| 1139 | } |
---|
| 1140 | return this; |
---|
| 1141 | } |
---|
[4ccbc25] | 1142 | else |
---|
| 1143 | { |
---|
[a29d092] | 1144 | decRefCount(); |
---|
| 1145 | termList last, first = copyTermList( firstTerm, last, negate ); |
---|
[4ccbc25] | 1146 | if ( last->exp == 0 ) |
---|
| 1147 | { |
---|
[a29d092] | 1148 | if ( negate ) |
---|
| 1149 | last->coeff += c; |
---|
| 1150 | else |
---|
| 1151 | last->coeff -= c; |
---|
[4ccbc25] | 1152 | if ( last->coeff.isZero() ) |
---|
| 1153 | { |
---|
[a29d092] | 1154 | termList cursor = first; |
---|
| 1155 | while ( cursor->next != last ) |
---|
| 1156 | cursor = cursor->next; |
---|
| 1157 | delete last; |
---|
| 1158 | cursor->next = 0; |
---|
| 1159 | last = cursor; |
---|
| 1160 | } |
---|
| 1161 | } |
---|
[4ccbc25] | 1162 | else |
---|
| 1163 | { |
---|
[a29d092] | 1164 | if ( negate ) |
---|
| 1165 | last->next = new term( 0, c, 0 ); |
---|
| 1166 | else |
---|
| 1167 | last->next = new term( 0, -c, 0 ); |
---|
| 1168 | last = last->next; |
---|
| 1169 | } |
---|
| 1170 | return new InternalPoly( first, last, var ); |
---|
| 1171 | } |
---|
[2dd068] | 1172 | } |
---|
| 1173 | } |
---|
| 1174 | |
---|
| 1175 | InternalCF* |
---|
| 1176 | InternalPoly::mulcoeff( InternalCF* cc ) |
---|
| 1177 | { |
---|
| 1178 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
[4ccbc25] | 1179 | if ( c.isZero() ) |
---|
| 1180 | { |
---|
[8ce2d8c] | 1181 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1182 | { |
---|
[a29d092] | 1183 | delete this; |
---|
| 1184 | return CFFactory::basic( 0 ); |
---|
| 1185 | } |
---|
[4ccbc25] | 1186 | else |
---|
| 1187 | { |
---|
[a29d092] | 1188 | decRefCount(); |
---|
| 1189 | return CFFactory::basic( 0 ); |
---|
| 1190 | } |
---|
[2dd068] | 1191 | } |
---|
| 1192 | else if ( c.isOne() ) |
---|
[a29d092] | 1193 | return this; |
---|
[4ccbc25] | 1194 | else |
---|
| 1195 | { |
---|
[8ce2d8c] | 1196 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1197 | { |
---|
[a29d092] | 1198 | mulTermList( firstTerm, c, 0 ); |
---|
| 1199 | return this; |
---|
| 1200 | } |
---|
[4ccbc25] | 1201 | else |
---|
| 1202 | { |
---|
[a29d092] | 1203 | decRefCount(); |
---|
| 1204 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1205 | mulTermList( first, c, 0 ); |
---|
| 1206 | return new InternalPoly( first, last, var ); |
---|
| 1207 | } |
---|
[2dd068] | 1208 | } |
---|
| 1209 | } |
---|
| 1210 | |
---|
| 1211 | InternalCF* |
---|
[fc732a9] | 1212 | InternalPoly::dividecoeff( InternalCF* cc, bool invert ) |
---|
[2dd068] | 1213 | { |
---|
[fc732a9] | 1214 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
[4ccbc25] | 1215 | if ( inExtension() && getReduce( var ) && invert ) |
---|
| 1216 | { |
---|
[a29d092] | 1217 | InternalCF * dummy; |
---|
| 1218 | dummy = this->invert(); |
---|
[4ccbc25] | 1219 | if (is_imm(dummy)) |
---|
[778a4e] | 1220 | { |
---|
| 1221 | if (is_imm(cc)) |
---|
| 1222 | { |
---|
| 1223 | InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc)); |
---|
| 1224 | dummy=d; |
---|
| 1225 | } |
---|
| 1226 | else |
---|
| 1227 | dummy=cc->mulcoeff(dummy); |
---|
| 1228 | } |
---|
| 1229 | else dummy = dummy->mulcoeff( cc ); |
---|
[8ce2d8c] | 1230 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1231 | { |
---|
[a29d092] | 1232 | delete this; |
---|
| 1233 | return dummy; |
---|
| 1234 | } |
---|
[4ccbc25] | 1235 | else |
---|
| 1236 | { |
---|
[a29d092] | 1237 | decRefCount(); |
---|
| 1238 | return dummy; |
---|
| 1239 | } |
---|
[fc732a9] | 1240 | } |
---|
| 1241 | if ( invert ) |
---|
[ac8e1a] | 1242 | { |
---|
[8ce2d8c] | 1243 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1244 | { |
---|
[a29d092] | 1245 | delete this; |
---|
| 1246 | return CFFactory::basic( 0 ); |
---|
| 1247 | } |
---|
[4ccbc25] | 1248 | else |
---|
| 1249 | { |
---|
[a29d092] | 1250 | decRefCount(); |
---|
| 1251 | return CFFactory::basic( 0 ); |
---|
| 1252 | } |
---|
[ac8e1a] | 1253 | } |
---|
[fc732a9] | 1254 | if ( c.isOne() ) |
---|
[a29d092] | 1255 | return this; |
---|
[4ccbc25] | 1256 | else |
---|
| 1257 | { |
---|
[8ce2d8c] | 1258 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1259 | { |
---|
[a29d092] | 1260 | firstTerm = divideTermList( firstTerm, c, lastTerm ); |
---|
| 1261 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 1262 | return this; |
---|
[4ccbc25] | 1263 | else if ( firstTerm ) |
---|
| 1264 | { |
---|
[a29d092] | 1265 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 1266 | delete this; |
---|
| 1267 | return res; |
---|
| 1268 | } |
---|
[4ccbc25] | 1269 | else |
---|
| 1270 | { |
---|
[a29d092] | 1271 | delete this; |
---|
| 1272 | return CFFactory::basic( 0 ); |
---|
| 1273 | } |
---|
| 1274 | } |
---|
[4ccbc25] | 1275 | else |
---|
| 1276 | { |
---|
[a29d092] | 1277 | decRefCount(); |
---|
| 1278 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1279 | first = divideTermList( first, c, last ); |
---|
| 1280 | if ( first && first->exp != 0 ) |
---|
| 1281 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 1282 | else if ( first ) |
---|
| 1283 | { |
---|
[a29d092] | 1284 | InternalCF * res = first->coeff.getval(); |
---|
| 1285 | delete first; |
---|
| 1286 | return res; |
---|
| 1287 | } |
---|
[4ccbc25] | 1288 | else |
---|
| 1289 | { |
---|
[a29d092] | 1290 | delete first; |
---|
| 1291 | return CFFactory::basic( 0 ); |
---|
| 1292 | } |
---|
| 1293 | } |
---|
[fc732a9] | 1294 | } |
---|
[2dd068] | 1295 | } |
---|
| 1296 | |
---|
[ec970e] | 1297 | InternalCF* |
---|
| 1298 | InternalPoly::tryDividecoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail ) |
---|
| 1299 | { |
---|
| 1300 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1301 | if ( inExtension() && !getReduce( var ) && invert ) |
---|
| 1302 | { |
---|
| 1303 | InternalCF * dummy; |
---|
| 1304 | dummy = this->tryInvert(M, fail); |
---|
| 1305 | if (fail) |
---|
| 1306 | { |
---|
| 1307 | if (getRefCount() <= 1) |
---|
| 1308 | delete this; |
---|
| 1309 | else |
---|
| 1310 | decRefCount(); |
---|
| 1311 | return dummy; //is equal to CFFactory::basic (0) in this case |
---|
| 1312 | } |
---|
| 1313 | if (is_imm(dummy)) |
---|
| 1314 | { |
---|
| 1315 | if (is_imm(cc)) |
---|
| 1316 | { |
---|
| 1317 | InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc)); |
---|
| 1318 | dummy=d; |
---|
| 1319 | } |
---|
| 1320 | else |
---|
| 1321 | dummy=cc->mulcoeff(dummy); |
---|
| 1322 | } |
---|
| 1323 | else dummy = dummy->mulcoeff( cc ); |
---|
| 1324 | if ( getRefCount() <= 1 ) |
---|
| 1325 | { |
---|
| 1326 | delete this; |
---|
| 1327 | return dummy; |
---|
| 1328 | } |
---|
| 1329 | else |
---|
| 1330 | { |
---|
| 1331 | decRefCount(); |
---|
| 1332 | return dummy; |
---|
| 1333 | } |
---|
| 1334 | } |
---|
| 1335 | if ( invert ) |
---|
| 1336 | { |
---|
| 1337 | if ( getRefCount() <= 1 ) |
---|
| 1338 | { |
---|
| 1339 | delete this; |
---|
| 1340 | return CFFactory::basic( 0 ); |
---|
| 1341 | } |
---|
| 1342 | else |
---|
| 1343 | { |
---|
| 1344 | decRefCount(); |
---|
| 1345 | return CFFactory::basic( 0 ); |
---|
| 1346 | } |
---|
| 1347 | } |
---|
| 1348 | if ( c.isOne() ) |
---|
| 1349 | return this; |
---|
| 1350 | //one should never get here |
---|
| 1351 | else |
---|
| 1352 | { |
---|
| 1353 | if ( getRefCount() <= 1 ) |
---|
| 1354 | { |
---|
| 1355 | firstTerm = divideTermList( firstTerm, c, lastTerm ); |
---|
| 1356 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 1357 | return this; |
---|
| 1358 | else if ( firstTerm ) |
---|
| 1359 | { |
---|
| 1360 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 1361 | delete this; |
---|
| 1362 | return res; |
---|
| 1363 | } |
---|
| 1364 | else |
---|
| 1365 | { |
---|
| 1366 | delete this; |
---|
| 1367 | return CFFactory::basic( 0 ); |
---|
| 1368 | } |
---|
| 1369 | } |
---|
| 1370 | else |
---|
| 1371 | { |
---|
| 1372 | decRefCount(); |
---|
| 1373 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1374 | first = divideTermList( first, c, last ); |
---|
| 1375 | if ( first && first->exp != 0 ) |
---|
| 1376 | return new InternalPoly( first, last, var ); |
---|
| 1377 | else if ( first ) |
---|
| 1378 | { |
---|
| 1379 | InternalCF * res = first->coeff.getval(); |
---|
| 1380 | delete first; |
---|
| 1381 | return res; |
---|
| 1382 | } |
---|
| 1383 | else |
---|
| 1384 | { |
---|
| 1385 | delete first; |
---|
| 1386 | return CFFactory::basic( 0 ); |
---|
| 1387 | } |
---|
| 1388 | } |
---|
| 1389 | } |
---|
| 1390 | } |
---|
| 1391 | |
---|
| 1392 | |
---|
[2dd068] | 1393 | InternalCF* |
---|
| 1394 | InternalPoly::divcoeff( InternalCF* cc, bool invert ) |
---|
| 1395 | { |
---|
| 1396 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
[4ccbc25] | 1397 | if ( inExtension() && getReduce( var ) && invert ) |
---|
| 1398 | { |
---|
[a29d092] | 1399 | InternalCF * dummy; |
---|
| 1400 | dummy = this->invert(); |
---|
| 1401 | dummy = dummy->mulcoeff( cc ); |
---|
[8ce2d8c] | 1402 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1403 | { |
---|
[a29d092] | 1404 | delete this; |
---|
| 1405 | return dummy; |
---|
| 1406 | } |
---|
[4ccbc25] | 1407 | else |
---|
| 1408 | { |
---|
[a29d092] | 1409 | decRefCount(); |
---|
| 1410 | return dummy; |
---|
| 1411 | } |
---|
[2dd068] | 1412 | } |
---|
| 1413 | if ( invert ) |
---|
[ac8e1a] | 1414 | { |
---|
[8ce2d8c] | 1415 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1416 | { |
---|
[a29d092] | 1417 | delete this; |
---|
| 1418 | return CFFactory::basic( 0 ); |
---|
| 1419 | } |
---|
[4ccbc25] | 1420 | else |
---|
| 1421 | { |
---|
[a29d092] | 1422 | decRefCount(); |
---|
| 1423 | return CFFactory::basic( 0 ); |
---|
| 1424 | } |
---|
[ac8e1a] | 1425 | } |
---|
[2dd068] | 1426 | if ( c.isOne() ) |
---|
[a29d092] | 1427 | return this; |
---|
[4ccbc25] | 1428 | else |
---|
| 1429 | { |
---|
[8ce2d8c] | 1430 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1431 | { |
---|
[a29d092] | 1432 | firstTerm = divTermList( firstTerm, c, lastTerm ); |
---|
| 1433 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 1434 | return this; |
---|
[4ccbc25] | 1435 | else if ( firstTerm ) |
---|
| 1436 | { |
---|
[a29d092] | 1437 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 1438 | delete this; |
---|
| 1439 | return res; |
---|
| 1440 | } |
---|
[4ccbc25] | 1441 | else |
---|
| 1442 | { |
---|
[a29d092] | 1443 | delete this; |
---|
| 1444 | return CFFactory::basic( 0 ); |
---|
| 1445 | } |
---|
| 1446 | } |
---|
[4ccbc25] | 1447 | else |
---|
| 1448 | { |
---|
[a29d092] | 1449 | decRefCount(); |
---|
| 1450 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1451 | first = divTermList( first, c, last ); |
---|
| 1452 | if ( first && first->exp != 0 ) |
---|
| 1453 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 1454 | else if ( first ) |
---|
| 1455 | { |
---|
[a29d092] | 1456 | InternalCF * res = first->coeff.getval(); |
---|
| 1457 | delete first; |
---|
| 1458 | return res; |
---|
| 1459 | } |
---|
[4ccbc25] | 1460 | else |
---|
| 1461 | { |
---|
[a29d092] | 1462 | delete first; |
---|
| 1463 | return CFFactory::basic( 0 ); |
---|
| 1464 | } |
---|
| 1465 | } |
---|
[2dd068] | 1466 | } |
---|
| 1467 | } |
---|
| 1468 | |
---|
[ec970e] | 1469 | InternalCF* |
---|
| 1470 | InternalPoly::tryDivcoeff( InternalCF* cc, bool invert, const CanonicalForm& M, bool& fail ) |
---|
| 1471 | { |
---|
| 1472 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1473 | if ( inExtension() && !getReduce( var ) && invert ) |
---|
| 1474 | { |
---|
| 1475 | InternalCF * dummy; |
---|
| 1476 | dummy = this->tryInvert(M, fail); |
---|
| 1477 | if (fail) |
---|
| 1478 | { |
---|
| 1479 | if (getRefCount() <= 1) |
---|
| 1480 | delete this; |
---|
| 1481 | else |
---|
| 1482 | decRefCount(); |
---|
| 1483 | return dummy; |
---|
| 1484 | } |
---|
| 1485 | dummy = dummy->mulcoeff( cc ); |
---|
| 1486 | if ( getRefCount() <= 1 ) |
---|
| 1487 | { |
---|
| 1488 | delete this; |
---|
| 1489 | return dummy; |
---|
| 1490 | } |
---|
| 1491 | else |
---|
| 1492 | { |
---|
| 1493 | decRefCount(); |
---|
| 1494 | return dummy; |
---|
| 1495 | } |
---|
| 1496 | } |
---|
| 1497 | if ( invert ) |
---|
| 1498 | { |
---|
| 1499 | if ( getRefCount() <= 1 ) |
---|
| 1500 | { |
---|
| 1501 | delete this; |
---|
| 1502 | return CFFactory::basic( 0 ); |
---|
| 1503 | } |
---|
| 1504 | else |
---|
| 1505 | { |
---|
| 1506 | decRefCount(); |
---|
| 1507 | return CFFactory::basic( 0 ); |
---|
| 1508 | } |
---|
| 1509 | } |
---|
| 1510 | if ( c.isOne() ) |
---|
| 1511 | return this; |
---|
| 1512 | else |
---|
| 1513 | { |
---|
| 1514 | if ( getRefCount() <= 1 ) |
---|
| 1515 | { |
---|
| 1516 | firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail ); |
---|
| 1517 | if (fail) |
---|
| 1518 | { |
---|
| 1519 | delete this; |
---|
| 1520 | return CFFactory::basic (0); |
---|
| 1521 | } |
---|
| 1522 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 1523 | return this; |
---|
| 1524 | else if ( firstTerm ) |
---|
| 1525 | { |
---|
| 1526 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 1527 | delete this; |
---|
| 1528 | return res; |
---|
| 1529 | } |
---|
| 1530 | else |
---|
| 1531 | { |
---|
| 1532 | delete this; |
---|
| 1533 | return CFFactory::basic( 0 ); |
---|
| 1534 | } |
---|
| 1535 | } |
---|
| 1536 | else |
---|
| 1537 | { |
---|
| 1538 | decRefCount(); |
---|
| 1539 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1540 | first = tryDivTermList( first, c, last, M, fail ); |
---|
| 1541 | if (fail) |
---|
| 1542 | { |
---|
| 1543 | delete this; |
---|
| 1544 | return CFFactory::basic (0); |
---|
| 1545 | } |
---|
| 1546 | if (fail) |
---|
| 1547 | { |
---|
| 1548 | delete first; |
---|
| 1549 | return CFFactory::basic (0); |
---|
| 1550 | } |
---|
| 1551 | if ( first && first->exp != 0 ) |
---|
| 1552 | return new InternalPoly( first, last, var ); |
---|
| 1553 | else if ( first ) |
---|
| 1554 | { |
---|
| 1555 | InternalCF * res = first->coeff.getval(); |
---|
| 1556 | delete first; |
---|
| 1557 | return res; |
---|
| 1558 | } |
---|
| 1559 | else |
---|
| 1560 | { |
---|
| 1561 | delete first; |
---|
| 1562 | return CFFactory::basic( 0 ); |
---|
| 1563 | } |
---|
| 1564 | } |
---|
| 1565 | } |
---|
| 1566 | } |
---|
| 1567 | |
---|
[2dd068] | 1568 | InternalCF* |
---|
| 1569 | InternalPoly::modulocoeff( InternalCF* cc, bool invert ) |
---|
| 1570 | { |
---|
| 1571 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
[4ccbc25] | 1572 | if ( invert ) |
---|
| 1573 | { |
---|
[a29d092] | 1574 | if ( deleteObject() ) delete this; |
---|
| 1575 | return c.getval(); |
---|
[2dd068] | 1576 | } |
---|
| 1577 | ASSERT( ! c.isZero(), "divide by zero!" ); |
---|
| 1578 | if ( deleteObject() ) delete this; |
---|
| 1579 | return CFFactory::basic( 0 ); |
---|
| 1580 | } |
---|
| 1581 | |
---|
| 1582 | InternalCF* |
---|
| 1583 | InternalPoly::modcoeff( InternalCF* cc, bool invert ) |
---|
| 1584 | { |
---|
| 1585 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
[4ccbc25] | 1586 | if ( invert ) |
---|
| 1587 | { |
---|
[a29d092] | 1588 | if ( deleteObject() ) delete this; |
---|
| 1589 | return c.getval(); |
---|
[2dd068] | 1590 | } |
---|
| 1591 | ASSERT( ! c.isZero(), "divide by zero!" ); |
---|
[4ccbc25] | 1592 | if ( c.isOne() ) |
---|
| 1593 | { |
---|
[8ce2d8c] | 1594 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1595 | { |
---|
[2dd068] | 1596 | delete this; |
---|
| 1597 | return CFFactory::basic( 0 ); |
---|
| 1598 | } |
---|
[4ccbc25] | 1599 | else |
---|
| 1600 | { |
---|
[2dd068] | 1601 | decRefCount(); |
---|
| 1602 | return CFFactory::basic( 0 ); |
---|
| 1603 | } |
---|
| 1604 | } |
---|
[4ccbc25] | 1605 | else |
---|
| 1606 | { |
---|
[8ce2d8c] | 1607 | if ( getRefCount() <= 1 ) |
---|
[4ccbc25] | 1608 | { |
---|
[2dd068] | 1609 | firstTerm = modTermList( firstTerm, c, lastTerm ); |
---|
| 1610 | if ( firstTerm && firstTerm->exp != 0 ) |
---|
| 1611 | return this; |
---|
[4ccbc25] | 1612 | else if ( firstTerm ) |
---|
| 1613 | { |
---|
[2dd068] | 1614 | InternalCF * res = firstTerm->coeff.getval(); |
---|
| 1615 | delete this; |
---|
| 1616 | return res; |
---|
| 1617 | } |
---|
[4ccbc25] | 1618 | else |
---|
| 1619 | { |
---|
[2dd068] | 1620 | delete this; |
---|
| 1621 | return CFFactory::basic( 0 ); |
---|
| 1622 | } |
---|
| 1623 | } |
---|
[4ccbc25] | 1624 | else |
---|
| 1625 | { |
---|
[2dd068] | 1626 | decRefCount(); |
---|
| 1627 | termList last, first = copyTermList( firstTerm, last ); |
---|
| 1628 | first = modTermList( first, c, last ); |
---|
| 1629 | if ( first && first->exp != 0 ) |
---|
| 1630 | return new InternalPoly( first, last, var ); |
---|
[4ccbc25] | 1631 | else if ( first ) |
---|
| 1632 | { |
---|
[2dd068] | 1633 | InternalCF * res = first->coeff.getval(); |
---|
| 1634 | delete first; |
---|
| 1635 | return res; |
---|
| 1636 | } |
---|
[4ccbc25] | 1637 | else |
---|
| 1638 | { |
---|
[2dd068] | 1639 | delete first; |
---|
| 1640 | return CFFactory::basic( 0 ); |
---|
| 1641 | } |
---|
| 1642 | } |
---|
| 1643 | } |
---|
| 1644 | } |
---|
| 1645 | |
---|
| 1646 | void |
---|
| 1647 | InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert ) |
---|
| 1648 | { |
---|
[4ccbc25] | 1649 | if ( inExtension() && getReduce( var ) ) |
---|
| 1650 | { |
---|
[a29d092] | 1651 | quot = copyObject(); |
---|
| 1652 | quot = quot->dividecoeff( cc, invert ); |
---|
| 1653 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 1654 | } |
---|
[4ccbc25] | 1655 | else if ( invert ) |
---|
| 1656 | { |
---|
[a29d092] | 1657 | if ( is_imm( cc ) ) |
---|
| 1658 | rem = cc; |
---|
| 1659 | else |
---|
| 1660 | rem = cc->copyObject(); |
---|
| 1661 | quot = CFFactory::basic( 0 ); |
---|
[2dd068] | 1662 | } |
---|
[4ccbc25] | 1663 | else |
---|
| 1664 | { |
---|
[a29d092] | 1665 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1666 | ASSERT( ! c.isZero(), "divide by zero!" ); |
---|
| 1667 | termList quotlast, quotfirst = copyTermList( firstTerm, quotlast ); |
---|
| 1668 | quotfirst = divideTermList( quotfirst, c, quotlast ); |
---|
| 1669 | if ( quotfirst ) |
---|
[4ccbc25] | 1670 | if ( quotfirst->exp == 0 ) |
---|
| 1671 | { |
---|
[a29d092] | 1672 | quot = quotfirst->coeff.getval(); |
---|
| 1673 | delete quotfirst; |
---|
| 1674 | } |
---|
| 1675 | else |
---|
| 1676 | quot = new InternalPoly( quotfirst, quotlast, var ); |
---|
| 1677 | else |
---|
| 1678 | quot = CFFactory::basic( 0 ); |
---|
| 1679 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 1680 | } |
---|
| 1681 | } |
---|
| 1682 | |
---|
| 1683 | bool |
---|
| 1684 | InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert ) |
---|
| 1685 | { |
---|
[4ccbc25] | 1686 | if ( inExtension() && getReduce( var ) ) |
---|
| 1687 | { |
---|
[a29d092] | 1688 | quot = copyObject(); |
---|
| 1689 | quot = quot->dividecoeff( cc, invert ); |
---|
| 1690 | rem = CFFactory::basic( 0 ); |
---|
| 1691 | return true; |
---|
[2dd068] | 1692 | } |
---|
[4ccbc25] | 1693 | else if ( invert ) |
---|
| 1694 | { |
---|
[a29d092] | 1695 | if ( is_imm( cc ) ) |
---|
| 1696 | rem = cc; |
---|
| 1697 | else |
---|
| 1698 | rem = cc->copyObject(); |
---|
| 1699 | quot = CFFactory::basic( 0 ); |
---|
| 1700 | return true; |
---|
[2dd068] | 1701 | } |
---|
| 1702 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1703 | ASSERT( ! c.isZero(), "divide by zero!" ); |
---|
| 1704 | termList quotfirst, quotcursor; |
---|
| 1705 | termList cursor; |
---|
| 1706 | CanonicalForm cquot, crem; |
---|
| 1707 | bool divideok = true; |
---|
| 1708 | |
---|
| 1709 | cursor = firstTerm; |
---|
| 1710 | quotcursor = quotfirst = new term; |
---|
| 1711 | |
---|
[4ccbc25] | 1712 | while ( cursor && divideok ) |
---|
| 1713 | { |
---|
[6b503c] | 1714 | divideok = divremt( cursor->coeff, c, cquot, crem ); |
---|
[a29d092] | 1715 | divideok = divideok && crem.isZero(); |
---|
[4ccbc25] | 1716 | if ( divideok ) |
---|
| 1717 | { |
---|
| 1718 | if ( ! cquot.isZero() ) |
---|
| 1719 | { |
---|
[a29d092] | 1720 | quotcursor->next = new term( 0, cquot, cursor->exp ); |
---|
| 1721 | quotcursor = quotcursor->next; |
---|
| 1722 | } |
---|
| 1723 | cursor = cursor->next; |
---|
| 1724 | } |
---|
[2dd068] | 1725 | } |
---|
| 1726 | quotcursor->next = 0; |
---|
[4ccbc25] | 1727 | if ( divideok ) |
---|
| 1728 | { |
---|
[a29d092] | 1729 | cursor = quotfirst; quotfirst = quotfirst->next; delete cursor; |
---|
| 1730 | if ( quotfirst ) |
---|
[4ccbc25] | 1731 | if ( quotfirst->exp == 0 ) |
---|
| 1732 | { |
---|
[a29d092] | 1733 | quot = quotfirst->coeff.getval(); |
---|
| 1734 | delete quotfirst; |
---|
| 1735 | } |
---|
| 1736 | else |
---|
| 1737 | quot = new InternalPoly( quotfirst, quotcursor, var ); |
---|
| 1738 | else |
---|
| 1739 | quot = CFFactory::basic( 0 ); |
---|
| 1740 | rem = CFFactory::basic( 0 ); |
---|
[2dd068] | 1741 | } |
---|
[4ccbc25] | 1742 | else |
---|
| 1743 | { |
---|
[a29d092] | 1744 | freeTermList( quotfirst ); |
---|
[2dd068] | 1745 | } |
---|
| 1746 | return divideok; |
---|
| 1747 | } |
---|
| 1748 | |
---|
[ec970e] | 1749 | bool |
---|
| 1750 | InternalPoly::tryDivremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert, const CanonicalForm& M, bool& fail ) |
---|
| 1751 | { |
---|
| 1752 | if ( inExtension() && !getReduce( var ) ) |
---|
| 1753 | { |
---|
| 1754 | quot = copyObject(); |
---|
| 1755 | quot = quot->tryDividecoeff( cc, invert, M, fail ); |
---|
| 1756 | if (fail) |
---|
| 1757 | return false; |
---|
| 1758 | rem = CFFactory::basic( 0 ); |
---|
| 1759 | return true; |
---|
| 1760 | } |
---|
| 1761 | else if ( invert ) |
---|
| 1762 | { |
---|
| 1763 | if ( is_imm( cc ) ) |
---|
| 1764 | rem = cc; |
---|
| 1765 | else |
---|
| 1766 | rem = cc->copyObject(); |
---|
| 1767 | quot = CFFactory::basic( 0 ); |
---|
| 1768 | return true; |
---|
| 1769 | } |
---|
| 1770 | CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() ); |
---|
| 1771 | ASSERT( ! c.isZero(), "divide by zero!" ); |
---|
| 1772 | termList quotfirst, quotcursor; |
---|
| 1773 | termList cursor; |
---|
| 1774 | CanonicalForm cquot, crem; |
---|
| 1775 | bool divideok = true; |
---|
| 1776 | |
---|
| 1777 | cursor = firstTerm; |
---|
| 1778 | quotcursor = quotfirst = new term; |
---|
| 1779 | |
---|
| 1780 | while ( cursor && divideok ) |
---|
| 1781 | { |
---|
| 1782 | divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail ); |
---|
| 1783 | if (fail) |
---|
| 1784 | { |
---|
| 1785 | freeTermList (quotfirst); |
---|
| 1786 | return false; |
---|
| 1787 | } |
---|
| 1788 | divideok = divideok && crem.isZero(); |
---|
| 1789 | if ( divideok ) |
---|
| 1790 | { |
---|
| 1791 | if ( ! cquot.isZero() ) |
---|
| 1792 | { |
---|
| 1793 | quotcursor->next = new term( 0, cquot, cursor->exp ); |
---|
| 1794 | quotcursor = quotcursor->next; |
---|
| 1795 | } |
---|
| 1796 | cursor = cursor->next; |
---|
| 1797 | } |
---|
| 1798 | } |
---|
| 1799 | quotcursor->next = 0; |
---|
| 1800 | if ( divideok ) |
---|
| 1801 | { |
---|
| 1802 | cursor = quotfirst; quotfirst = quotfirst->next; delete cursor; |
---|
| 1803 | if ( quotfirst ) |
---|
| 1804 | if ( quotfirst->exp == 0 ) |
---|
| 1805 | { |
---|
| 1806 | quot = quotfirst->coeff.getval(); |
---|
| 1807 | delete quotfirst; |
---|
| 1808 | } |
---|
| 1809 | else |
---|
| 1810 | quot = new InternalPoly( quotfirst, quotcursor, var ); |
---|
| 1811 | else |
---|
| 1812 | quot = CFFactory::basic( 0 ); |
---|
| 1813 | rem = CFFactory::basic( 0 ); |
---|
| 1814 | } |
---|
| 1815 | else |
---|
| 1816 | { |
---|
| 1817 | freeTermList( quotfirst ); |
---|
| 1818 | } |
---|
| 1819 | return divideok; |
---|
| 1820 | } |
---|
| 1821 | |
---|
[2dd068] | 1822 | // static functions |
---|
| 1823 | |
---|
| 1824 | termList |
---|
| 1825 | InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate ) |
---|
| 1826 | { |
---|
[32e9cd7] | 1827 | if ( aTermList == 0 ) |
---|
[a29d092] | 1828 | return 0; |
---|
[1e6de6] | 1829 | else if ( negate ) |
---|
| 1830 | { |
---|
[a29d092] | 1831 | termList sourceCursor = aTermList; |
---|
| 1832 | termList dummy = new term; |
---|
| 1833 | termList targetCursor = dummy; |
---|
| 1834 | |
---|
[1e6de6] | 1835 | while ( sourceCursor ) |
---|
| 1836 | { |
---|
[a29d092] | 1837 | targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp ); |
---|
| 1838 | targetCursor = targetCursor->next; |
---|
| 1839 | sourceCursor = sourceCursor->next; |
---|
| 1840 | } |
---|
| 1841 | targetCursor->next = 0; |
---|
| 1842 | theLastTerm = targetCursor; |
---|
| 1843 | targetCursor = dummy->next; |
---|
| 1844 | delete dummy; |
---|
| 1845 | return targetCursor; |
---|
[2dd068] | 1846 | } |
---|
[1e6de6] | 1847 | else |
---|
| 1848 | { |
---|
[a29d092] | 1849 | termList sourceCursor = aTermList; |
---|
| 1850 | termList dummy = new term; |
---|
| 1851 | termList targetCursor = dummy; |
---|
| 1852 | |
---|
[1e6de6] | 1853 | while ( sourceCursor ) |
---|
| 1854 | { |
---|
[a29d092] | 1855 | targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp ); |
---|
| 1856 | targetCursor = targetCursor->next; |
---|
| 1857 | sourceCursor = sourceCursor->next; |
---|
| 1858 | } |
---|
| 1859 | targetCursor->next = 0; |
---|
| 1860 | theLastTerm = targetCursor; |
---|
| 1861 | targetCursor = dummy->next; |
---|
| 1862 | delete dummy; |
---|
| 1863 | return targetCursor; |
---|
[2dd068] | 1864 | } |
---|
| 1865 | } |
---|
| 1866 | |
---|
| 1867 | termList |
---|
| 1868 | InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm ) |
---|
| 1869 | { |
---|
[32e9cd7] | 1870 | if ( aTermList == 0 ) |
---|
[a29d092] | 1871 | return 0; |
---|
[1e6de6] | 1872 | else |
---|
| 1873 | { |
---|
[a29d092] | 1874 | termList sourceCursor = aTermList; |
---|
| 1875 | termList dummy = new term; |
---|
| 1876 | termList targetCursor = dummy; |
---|
| 1877 | |
---|
[1e6de6] | 1878 | while ( sourceCursor ) |
---|
| 1879 | { |
---|
[a29d092] | 1880 | targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp ); |
---|
| 1881 | targetCursor = targetCursor->next; |
---|
| 1882 | sourceCursor = sourceCursor->next; |
---|
| 1883 | } |
---|
| 1884 | targetCursor->next = 0; |
---|
| 1885 | theLastTerm = targetCursor; |
---|
| 1886 | targetCursor = dummy->next; |
---|
| 1887 | delete dummy; |
---|
| 1888 | return targetCursor; |
---|
[2dd068] | 1889 | } |
---|
| 1890 | } |
---|
| 1891 | |
---|
| 1892 | void |
---|
| 1893 | InternalPoly::freeTermList ( termList aTermList ) |
---|
| 1894 | { |
---|
| 1895 | termList cursor = aTermList; |
---|
| 1896 | |
---|
[1e6de6] | 1897 | while ( cursor ) |
---|
| 1898 | { |
---|
[a29d092] | 1899 | cursor = cursor->next; |
---|
| 1900 | delete aTermList; |
---|
| 1901 | aTermList = cursor; |
---|
[2dd068] | 1902 | } |
---|
| 1903 | } |
---|
| 1904 | |
---|
| 1905 | void |
---|
| 1906 | InternalPoly::negateTermList ( termList terms ) |
---|
| 1907 | { |
---|
| 1908 | termList cursor = terms; |
---|
[1e6de6] | 1909 | while ( cursor ) |
---|
| 1910 | { |
---|
[a29d092] | 1911 | cursor->coeff = -cursor->coeff; |
---|
| 1912 | cursor = cursor->next; |
---|
[2dd068] | 1913 | } |
---|
| 1914 | } |
---|
| 1915 | |
---|
| 1916 | termList |
---|
| 1917 | InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate ) |
---|
| 1918 | { |
---|
| 1919 | termList theCursor = theList; |
---|
| 1920 | termList aCursor = aList; |
---|
| 1921 | termList predCursor = 0; |
---|
| 1922 | |
---|
[1e6de6] | 1923 | while ( theCursor && aCursor ) |
---|
| 1924 | { |
---|
| 1925 | if ( theCursor->exp == aCursor->exp ) |
---|
| 1926 | { |
---|
[a29d092] | 1927 | if ( negate ) |
---|
| 1928 | theCursor->coeff -= aCursor->coeff; |
---|
| 1929 | else |
---|
| 1930 | theCursor->coeff += aCursor->coeff; |
---|
[1e6de6] | 1931 | if ( theCursor->coeff.isZero() ) |
---|
| 1932 | { |
---|
| 1933 | if ( predCursor ) |
---|
| 1934 | { |
---|
[a29d092] | 1935 | predCursor->next = theCursor->next; |
---|
| 1936 | delete theCursor; |
---|
| 1937 | theCursor = predCursor->next; |
---|
| 1938 | } |
---|
[1e6de6] | 1939 | else |
---|
| 1940 | { |
---|
[a29d092] | 1941 | theList = theList->next; |
---|
| 1942 | delete theCursor; |
---|
| 1943 | theCursor = theList; |
---|
| 1944 | } |
---|
| 1945 | } |
---|
[1e6de6] | 1946 | else |
---|
| 1947 | { |
---|
[a29d092] | 1948 | predCursor = theCursor; |
---|
| 1949 | theCursor = theCursor->next; |
---|
| 1950 | } |
---|
| 1951 | aCursor = aCursor->next; |
---|
| 1952 | } |
---|
[1e6de6] | 1953 | else if ( theCursor->exp < aCursor->exp ) |
---|
| 1954 | { |
---|
[a29d092] | 1955 | if ( negate ) |
---|
[1e6de6] | 1956 | if ( predCursor ) |
---|
| 1957 | { |
---|
[a29d092] | 1958 | predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp ); |
---|
| 1959 | predCursor = predCursor->next; |
---|
| 1960 | } |
---|
[1e6de6] | 1961 | else |
---|
| 1962 | { |
---|
[a29d092] | 1963 | theList = new term( theCursor, -aCursor->coeff, aCursor->exp ); |
---|
| 1964 | predCursor = theList; |
---|
| 1965 | } |
---|
| 1966 | else |
---|
[1e6de6] | 1967 | if ( predCursor ) |
---|
| 1968 | { |
---|
[a29d092] | 1969 | predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp ); |
---|
| 1970 | predCursor = predCursor->next; |
---|
| 1971 | } |
---|
[1e6de6] | 1972 | else |
---|
| 1973 | { |
---|
[a29d092] | 1974 | theList = new term( theCursor, aCursor->coeff, aCursor->exp ); |
---|
| 1975 | predCursor = theList; |
---|
| 1976 | } |
---|
| 1977 | aCursor = aCursor->next; |
---|
| 1978 | } |
---|
[1e6de6] | 1979 | else |
---|
| 1980 | { |
---|
[a29d092] | 1981 | predCursor = theCursor; |
---|
| 1982 | theCursor = theCursor->next; |
---|
| 1983 | } |
---|
[2dd068] | 1984 | } |
---|
[1e6de6] | 1985 | if ( aCursor ) |
---|
| 1986 | { |
---|
[a29d092] | 1987 | if ( predCursor ) |
---|
| 1988 | predCursor->next = copyTermList( aCursor, lastTerm, negate ); |
---|
| 1989 | else |
---|
| 1990 | theList = copyTermList( aCursor, lastTerm, negate ); |
---|
[2dd068] | 1991 | } |
---|
| 1992 | else if ( ! theCursor ) |
---|
[a29d092] | 1993 | lastTerm = predCursor; |
---|
[2dd068] | 1994 | |
---|
| 1995 | return theList; |
---|
| 1996 | } |
---|
| 1997 | |
---|
| 1998 | void |
---|
| 1999 | InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp ) |
---|
| 2000 | { |
---|
[1e6de6] | 2001 | while ( theCursor ) |
---|
| 2002 | { |
---|
[a29d092] | 2003 | theCursor->coeff *= coeff; |
---|
| 2004 | theCursor->exp += exp; |
---|
| 2005 | theCursor = theCursor->next; |
---|
[2dd068] | 2006 | } |
---|
| 2007 | } |
---|
| 2008 | |
---|
| 2009 | termList |
---|
[fc732a9] | 2010 | InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm ) |
---|
[2dd068] | 2011 | { |
---|
| 2012 | termList theCursor = firstTerm; |
---|
| 2013 | lastTerm = 0; |
---|
| 2014 | termList dummy; |
---|
| 2015 | |
---|
[1e6de6] | 2016 | while ( theCursor ) |
---|
| 2017 | { |
---|
[a29d092] | 2018 | theCursor->coeff /= coeff; |
---|
[1e6de6] | 2019 | if ( theCursor->coeff.isZero() ) |
---|
| 2020 | { |
---|
[a29d092] | 2021 | if ( theCursor == firstTerm ) |
---|
| 2022 | firstTerm = theCursor->next; |
---|
| 2023 | else |
---|
| 2024 | lastTerm->next = theCursor->next; |
---|
| 2025 | dummy = theCursor; |
---|
| 2026 | theCursor = theCursor->next; |
---|
| 2027 | delete dummy; |
---|
| 2028 | } |
---|
[1e6de6] | 2029 | else |
---|
| 2030 | { |
---|
[a29d092] | 2031 | lastTerm = theCursor; |
---|
| 2032 | theCursor = theCursor->next; |
---|
| 2033 | } |
---|
[fc732a9] | 2034 | } |
---|
| 2035 | return firstTerm; |
---|
| 2036 | } |
---|
| 2037 | |
---|
| 2038 | termList |
---|
| 2039 | InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm ) |
---|
| 2040 | { |
---|
| 2041 | termList theCursor = firstTerm; |
---|
| 2042 | lastTerm = 0; |
---|
| 2043 | termList dummy; |
---|
| 2044 | |
---|
[1e6de6] | 2045 | while ( theCursor ) |
---|
| 2046 | { |
---|
[a29d092] | 2047 | theCursor->coeff.div( coeff ); |
---|
[1e6de6] | 2048 | if ( theCursor->coeff.isZero() ) |
---|
| 2049 | { |
---|
[a29d092] | 2050 | if ( theCursor == firstTerm ) |
---|
| 2051 | firstTerm = theCursor->next; |
---|
| 2052 | else |
---|
| 2053 | lastTerm->next = theCursor->next; |
---|
| 2054 | dummy = theCursor; |
---|
| 2055 | theCursor = theCursor->next; |
---|
| 2056 | delete dummy; |
---|
| 2057 | } |
---|
[1e6de6] | 2058 | else |
---|
| 2059 | { |
---|
[a29d092] | 2060 | lastTerm = theCursor; |
---|
| 2061 | theCursor = theCursor->next; |
---|
| 2062 | } |
---|
[2dd068] | 2063 | } |
---|
| 2064 | return firstTerm; |
---|
| 2065 | } |
---|
| 2066 | |
---|
[ec970e] | 2067 | termList |
---|
| 2068 | InternalPoly::tryDivTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm, const CanonicalForm& M, bool& fail ) |
---|
| 2069 | { |
---|
| 2070 | termList theCursor = firstTerm; |
---|
| 2071 | lastTerm = 0; |
---|
| 2072 | termList dummy; |
---|
| 2073 | |
---|
| 2074 | while ( theCursor ) |
---|
| 2075 | { |
---|
| 2076 | theCursor->coeff.tryDiv( coeff, M, fail ); |
---|
| 2077 | if (fail) |
---|
| 2078 | return 0; |
---|
| 2079 | if ( theCursor->coeff.isZero() ) |
---|
| 2080 | { |
---|
| 2081 | if ( theCursor == firstTerm ) |
---|
| 2082 | firstTerm = theCursor->next; |
---|
| 2083 | else |
---|
| 2084 | lastTerm->next = theCursor->next; |
---|
| 2085 | dummy = theCursor; |
---|
| 2086 | theCursor = theCursor->next; |
---|
| 2087 | delete dummy; |
---|
| 2088 | } |
---|
| 2089 | else |
---|
| 2090 | { |
---|
| 2091 | lastTerm = theCursor; |
---|
| 2092 | theCursor = theCursor->next; |
---|
| 2093 | } |
---|
| 2094 | } |
---|
| 2095 | return firstTerm; |
---|
| 2096 | } |
---|
| 2097 | |
---|
[2dd068] | 2098 | termList |
---|
| 2099 | InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm ) |
---|
| 2100 | { |
---|
| 2101 | termList theCursor = firstTerm; |
---|
| 2102 | lastTerm = 0; |
---|
| 2103 | termList dummy; |
---|
| 2104 | |
---|
[1e6de6] | 2105 | while ( theCursor ) |
---|
| 2106 | { |
---|
[a29d092] | 2107 | theCursor->coeff.mod( coeff ); |
---|
[1e6de6] | 2108 | if ( theCursor->coeff.isZero() ) |
---|
| 2109 | { |
---|
[a29d092] | 2110 | if ( theCursor == firstTerm ) |
---|
| 2111 | firstTerm = theCursor->next; |
---|
| 2112 | else |
---|
| 2113 | lastTerm->next = theCursor->next; |
---|
| 2114 | dummy = theCursor; |
---|
| 2115 | theCursor = theCursor-> next; |
---|
| 2116 | delete dummy; |
---|
| 2117 | } |
---|
[1e6de6] | 2118 | else |
---|
| 2119 | { |
---|
[a29d092] | 2120 | lastTerm = theCursor; |
---|
| 2121 | theCursor = theCursor->next; |
---|
| 2122 | } |
---|
[2dd068] | 2123 | } |
---|
| 2124 | return firstTerm; |
---|
| 2125 | } |
---|
| 2126 | |
---|
| 2127 | void |
---|
| 2128 | InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp ) |
---|
| 2129 | { |
---|
[1e6de6] | 2130 | if ( last ) |
---|
| 2131 | { |
---|
[a29d092] | 2132 | last->next = new term( 0, coeff, exp ); |
---|
| 2133 | last = last->next; |
---|
[2dd068] | 2134 | } |
---|
[1e6de6] | 2135 | else |
---|
| 2136 | { |
---|
[a29d092] | 2137 | first = new term( 0, coeff, exp ); |
---|
| 2138 | last = first; |
---|
[2dd068] | 2139 | } |
---|
| 2140 | } |
---|
| 2141 | |
---|
| 2142 | termList |
---|
| 2143 | InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate ) |
---|
| 2144 | { |
---|
| 2145 | termList theCursor = theList; |
---|
| 2146 | termList aCursor = aList; |
---|
| 2147 | termList predCursor = 0; |
---|
| 2148 | CanonicalForm coeff; |
---|
| 2149 | |
---|
| 2150 | if ( negate ) |
---|
[a29d092] | 2151 | coeff = -c; |
---|
[2dd068] | 2152 | else |
---|
[a29d092] | 2153 | coeff = c; |
---|
[2dd068] | 2154 | |
---|
[1e6de6] | 2155 | while ( theCursor && aCursor ) |
---|
| 2156 | { |
---|
| 2157 | if ( theCursor->exp == aCursor->exp + exp ) |
---|
| 2158 | { |
---|
[a29d092] | 2159 | theCursor->coeff += aCursor->coeff * coeff; |
---|
[1e6de6] | 2160 | if ( theCursor->coeff.isZero() ) |
---|
| 2161 | { |
---|
| 2162 | if ( predCursor ) |
---|
| 2163 | { |
---|
[a29d092] | 2164 | predCursor->next = theCursor->next; |
---|
| 2165 | delete theCursor; |
---|
| 2166 | theCursor = predCursor->next; |
---|
| 2167 | } |
---|
[1e6de6] | 2168 | else |
---|
| 2169 | { |
---|
[a29d092] | 2170 | theList = theList->next; |
---|
| 2171 | delete theCursor; |
---|
| 2172 | theCursor = theList; |
---|
| 2173 | } |
---|
| 2174 | } |
---|
[1e6de6] | 2175 | else |
---|
| 2176 | { |
---|
[a29d092] | 2177 | predCursor = theCursor; |
---|
| 2178 | theCursor = theCursor->next; |
---|
| 2179 | } |
---|
| 2180 | aCursor = aCursor->next; |
---|
| 2181 | } |
---|
[1e6de6] | 2182 | else if ( theCursor->exp < aCursor->exp + exp ) |
---|
| 2183 | { |
---|
| 2184 | if ( predCursor ) |
---|
| 2185 | { |
---|
[a29d092] | 2186 | predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp ); |
---|
| 2187 | predCursor = predCursor->next; |
---|
| 2188 | } |
---|
[1e6de6] | 2189 | else |
---|
| 2190 | { |
---|
[a29d092] | 2191 | theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp ); |
---|
| 2192 | predCursor = theList; |
---|
| 2193 | } |
---|
| 2194 | aCursor = aCursor->next; |
---|
| 2195 | } |
---|
[1e6de6] | 2196 | else |
---|
| 2197 | { |
---|
[a29d092] | 2198 | predCursor = theCursor; |
---|
| 2199 | theCursor = theCursor->next; |
---|
| 2200 | } |
---|
[2dd068] | 2201 | } |
---|
[1e6de6] | 2202 | if ( aCursor ) |
---|
| 2203 | { |
---|
| 2204 | if ( predCursor ) |
---|
| 2205 | { |
---|
[a29d092] | 2206 | predCursor->next = copyTermList( aCursor, lastTerm ); |
---|
| 2207 | predCursor = predCursor->next; |
---|
| 2208 | } |
---|
[1e6de6] | 2209 | else |
---|
| 2210 | { |
---|
[a29d092] | 2211 | theList = copyTermList( aCursor, lastTerm ); |
---|
| 2212 | predCursor = theList; |
---|
| 2213 | } |
---|
[1e6de6] | 2214 | while ( predCursor ) |
---|
| 2215 | { |
---|
[a29d092] | 2216 | predCursor->exp += exp; |
---|
| 2217 | predCursor->coeff *= coeff; |
---|
| 2218 | predCursor = predCursor->next; |
---|
| 2219 | } |
---|
[2dd068] | 2220 | } |
---|
| 2221 | else if ( ! theCursor ) |
---|
[a29d092] | 2222 | lastTerm = predCursor; |
---|
[2dd068] | 2223 | return theList; |
---|
| 2224 | } |
---|
| 2225 | |
---|
| 2226 | termList |
---|
| 2227 | InternalPoly::reduceTermList ( termList first, termList redterms, termList & last ) |
---|
| 2228 | { |
---|
| 2229 | CanonicalForm coeff = redterms->coeff; |
---|
| 2230 | CanonicalForm newcoeff; |
---|
| 2231 | int newexp; |
---|
| 2232 | int exp = redterms->exp; |
---|
| 2233 | termList dummy; |
---|
[1e6de6] | 2234 | while ( first && ( first->exp >= exp ) ) |
---|
| 2235 | { |
---|
[a29d092] | 2236 | newcoeff = first->coeff / coeff; |
---|
| 2237 | newexp = first->exp - exp; |
---|
| 2238 | dummy = first; |
---|
| 2239 | first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true ); |
---|
| 2240 | delete dummy; |
---|
[2dd068] | 2241 | } |
---|
| 2242 | return first; |
---|
| 2243 | } |
---|
[ec970e] | 2244 | |
---|