Changeset cbb753 in git
- Timestamp:
- Jun 12, 2014, 1:31:56 PM (10 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 086f3ec7ab7655f9627e1c40dd022bf8494b12b1
- Parents:
- 50a6c59553a4e9ed5c3b72c3937a614ffbeac4f5
- git-author:
- Martin Lee <martinlee84@web.de>2014-06-12 13:31:56+02:00
- git-committer:
- Martin Lee <martinlee84@web.de>2014-06-17 17:12:29+02:00
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
factory/canonicalform.cc
r50a6c5 rcbb753 25 25 #endif /* NOSTREAMIO */ 26 26 27 / /{{{ constructors, destructors, selectors27 /** constructors, destructors, selectors **/ 28 28 CanonicalForm::CanonicalForm( const char * str, const int base ) : value( CFFactory::basic( str, base ) ) 29 29 { … … 54 54 getmpi (value, val); 55 55 } 56 //}}} 57 58 / /{{{ predicates56 57 58 /** predicates **/ 59 59 #if 0 60 60 bool … … 193 193 } 194 194 195 //}}} 196 197 / /{{{ conversion functions195 196 197 /** conversion functions **/ 198 198 long 199 199 CanonicalForm::intval() const … … 249 249 } 250 250 } 251 //}}} 252 253 //{{{ CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const 254 //{{{ docu 255 // 256 // lc(), Lc(), LC() - leading coefficient functions. 257 // 258 // All methods return CO if CO is in a base domain. 259 // 260 // lc() returns the leading coefficient of CO with respect to 261 // lexicographic ordering. Elements in an algebraic extension 262 // are considered polynomials so lc() always returns a leading 263 // coefficient in a base domain. This method is useful to get 264 // the base domain over which CO is defined. 265 // 266 // Lc() returns the leading coefficient of CO with respect to 267 // lexicographic ordering. In contrast to lc() elements in an 268 // algebraic extension are considered coefficients so Lc() always 269 // returns a leading coefficient in a coefficient domain. 270 // 271 // LC() returns the leading coefficient of CO where CO is 272 // considered a univariate polynomial in its main variable. An 273 // element of an algebraic extension is considered an univariate 274 // polynomial, too. 275 // 276 // LC( v ) returns the leading coefficient of CO where CO is 277 // considered an univariate polynomial in the polynomial variable 278 // v. 279 // Note: If v is less than the main variable of CO we have to 280 // swap variables which may be quite expensive. 281 // 282 // Examples: 283 // Let x < y be polynomial variables, a an algebraic variable. 284 // 285 // (3*a*x*y^2+y+x).lc() = 3 286 // (3*a*x*y^2+y+x).Lc() = 3*a 287 // (3*a*x*y^2+y+x).LC() = 3*a*x 288 // (3*a*x*y^2+y+x).LC( x ) = 3*a*y^2+1 289 // 290 // (3*a^2+4*a).lc() = 3 291 // (3*a^2+4*a).Lc() = 3*a^2+4*a 292 // (3*a^2+4*a).LC() = 3 293 // (3*a^2+4*a).LC( x ) = 3*a^2+4*a 294 // 295 // See also: InternalCF::lc(), InternalCF::Lc(), InternalCF::LC(), 296 // InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), 297 // ::lc(), ::Lc(), ::LC(), ::LC( v ) 298 // 299 //}}} 251 252 /** CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const 253 * 254 * lc(), Lc(), LC() - leading coefficient functions. 255 * 256 * All methods return CO if CO is in a base domain. 257 * 258 * lc() returns the leading coefficient of CO with respect to 259 * lexicographic ordering. Elements in an algebraic extension 260 * are considered polynomials so lc() always returns a leading 261 * coefficient in a base domain. This method is useful to get 262 * the base domain over which CO is defined. 263 * 264 * Lc() returns the leading coefficient of CO with respect to 265 * lexicographic ordering. In contrast to lc() elements in an 266 * algebraic extension are considered coefficients so Lc() always 267 * returns a leading coefficient in a coefficient domain. 268 * 269 * LC() returns the leading coefficient of CO where CO is 270 * considered a univariate polynomial in its main variable. An 271 * element of an algebraic extension is considered an univariate 272 * polynomial, too. 273 * 274 * LC( v ) returns the leading coefficient of CO where CO is 275 * considered an univariate polynomial in the polynomial variable 276 * v. 277 * Note: If v is less than the main variable of CO we have to 278 * swap variables which may be quite expensive. 279 * 280 * Examples: 281 * > Let x < y be polynomial variables, a an algebraic variable. 282 * 283 * > (3*a*x*y^2+y+x).lc() = 3 284 * 285 * > (3*a*x*y^2+y+x).Lc() = 3*a 286 * 287 * > (3*a*x*y^2+y+x).LC() = 3*a*x 288 * 289 * > (3*a*x*y^2+y+x).LC( x ) = 3*a*y^2+1 290 * 291 * 292 * > (3*a^2+4*a).lc() = 3 293 * 294 * > (3*a^2+4*a).Lc() = 3*a^2+4*a 295 * 296 * > (3*a^2+4*a).LC() = 3 297 * 298 * > (3*a^2+4*a).LC( x ) = 3*a^2+4*a 299 * 300 * @sa InternalCF::lc(), InternalCF::Lc(), InternalCF::LC(), 301 * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), 302 * ::lc(), ::Lc(), ::LC(), ::LC( v ) 303 * 304 **/ 300 305 CanonicalForm 301 306 CanonicalForm::lc () const … … 307 312 } 308 313 314 /** 315 * @sa CanonicalForm::lc(), CanonicalForm::LC(), InternalCF::lc(), 316 * InternalCF::Lc(), InternalCF::LC(), 317 * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), 318 * ::lc(), ::Lc(), ::LC(), ::LC( v ) 319 **/ 309 320 CanonicalForm 310 321 CanonicalForm::Lc () const … … 316 327 } 317 328 329 /** 330 * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(), 331 * InternalCF::Lc(), InternalCF::LC(), 332 * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), 333 * ::lc(), ::Lc(), ::LC(), ::LC( v ) 334 **/ 318 335 CanonicalForm 319 336 CanonicalForm::LC () const … … 325 342 } 326 343 344 /** 345 * @sa CanonicalForm::lc(), CanonicalForm::Lc(), InternalCF::lc(), 346 * InternalCF::Lc(), InternalCF::LC(), 347 * InternalPoly::lc(), InternalPoly::Lc(), InternalPoly::LC(), 348 * ::lc(), ::Lc(), ::LC(), ::LC( v ) 349 **/ 327 350 CanonicalForm 328 351 CanonicalForm::LC ( const Variable & v ) const … … 345 368 } 346 369 } 347 //}}} 348 349 //{{{ int CanonicalForm::degree (), degree ( v ) const 350 //{{{ docu 351 // 352 // degree() - degree methods. 353 // 354 // Both methods returns -1 for the zero polynomial and 0 if 355 // CO is in a base domain. 356 // 357 // degree() returns the degree of CO in its main variable. 358 // Elements in an algebraic extension are considered polynomials. 359 // 360 // degree( v ) returns the degree of CO with respect to v. 361 // Elements in an algebraic extension are considered polynomials, 362 // and v may be algebraic. 363 // 364 // See also: InternalCf::degree(), InternalPoly::degree(), 365 // ::degree(), ::degree( v ) 366 // 367 //}}} 370 371 /** 372 * Returns -1 for the zero polynomial and 0 if 373 * CO is in a base domain. 374 * 375 * degree() returns the degree of CO in its main variable. 376 * Elements in an algebraic extension are considered polynomials. 377 * 378 * @sa InternalCF::degree(), InternalPoly::degree(), 379 * ::degree(), ::degree( v ) 380 * 381 **/ 368 382 int 369 383 CanonicalForm::degree() const … … 381 395 } 382 396 397 /** 398 * returns -1 for the zero polynomial and 0 if 399 * CO is in a base domain. 400 * 401 * degree( v ) returns the degree of CO with respect to v. 402 * Elements in an algebraic extension are considered polynomials, 403 * and v may be algebraic. 404 * 405 * @sa InternalCF::degree(), InternalPoly::degree(), 406 * ::degree(), ::degree( v ) 407 **/ 383 408 int 384 409 CanonicalForm::degree( const Variable & v ) const … … 424 449 } 425 450 } 426 //}}} 427 428 //{{{ CanonicalForm CanonicalForm::tailcoeff (), int CanonicalForm::taildegree () const 429 //{{{ docu 430 // 431 // tailcoeff(), taildegree() - return least coefficient and 432 // degree, resp. 433 // 434 // tailcoeff() returns the coefficient of the term with the least 435 // degree in CO where CO is considered an univariate polynomial 436 // in its main variable. Elements in an algebraic extension are 437 // considered coefficients. 438 // 439 // taildegree() returns -1 for the zero polynomial, 0 if CO is in 440 // a base domain, otherwise the least degree of CO where CO is 441 // considered a univariate polynomial in its main variable. In 442 // contrast to tailcoeff(), elements in an algebraic extension 443 // are considered polynomials, not coefficients, and such may 444 // have a taildegree larger than zero. 445 // 446 // tailcoeff( v ) returns the tail coefficient of CO where CO is 447 // considered an univariate polynomial in the polynomial variable 448 // v. 449 // Note: If v is less than the main variable of CO we have to 450 // swap variables which may be quite expensive. 451 // 452 // See also: InternalCF::tailcoeff(), InternalCF::tailcoeff(), 453 // InternalPoly::tailcoeff(), InternalPoly::taildegree, 454 // ::tailcoeff(), ::taildegree() 455 // 456 //}}} 451 452 /** 453 * 454 * tailcoeff() - return least coefficient 455 * 456 * tailcoeff() returns the coefficient of the term with the least 457 * degree in CO where CO is considered an univariate polynomial 458 * in its main variable. Elements in an algebraic extension are 459 * considered coefficients. 460 * 461 * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(), 462 * InternalPoly::tailcoeff(), InternalPoly::taildegree, 463 * ::tailcoeff(), ::taildegree() 464 * 465 **/ 457 466 CanonicalForm 458 467 CanonicalForm::tailcoeff () const … … 464 473 } 465 474 475 /** 476 * tailcoeff( v ) returns the tail coefficient of CO where CO is 477 * considered an univariate polynomial in the polynomial variable 478 * v. 479 * Note: If v is less than the main variable of CO we have to 480 * swap variables which may be quite expensive. 481 * 482 * @sa CanonicalForm::taildegree(), InternalCF::tailcoeff(), InternalCF::tailcoeff(), 483 * InternalPoly::tailcoeff(), InternalPoly::taildegree, 484 * ::tailcoeff(), ::taildegree() 485 **/ 466 486 CanonicalForm 467 487 CanonicalForm::tailcoeff (const Variable& v) const … … 485 505 } 486 506 507 508 /** 509 * taildegree() returns -1 for the zero polynomial, 0 if CO is in 510 * a base domain, otherwise the least degree of CO where CO is 511 * considered a univariate polynomial in its main variable. In 512 * contrast to tailcoeff(), elements in an algebraic extension 513 * are considered polynomials, not coefficients, and such may 514 * have a taildegree larger than zero. 515 * 516 * @sa CanonicalForm::tailcoeff(), InternalCF::tailcoeff(), InternalCF::tailcoeff(), 517 * InternalPoly::tailcoeff(), InternalPoly::taildegree, 518 * ::tailcoeff(), ::taildegree() 519 **/ 487 520 int 488 521 CanonicalForm::taildegree () const … … 499 532 return value->taildegree(); 500 533 } 501 //}}} 502 503 //{{{ int CanonicalForm::level (), Variable CanonicalForm::mvar () const 504 //{{{ docu 505 // 506 // level(), mvar() - return level and main variable of CO. 507 // 508 // level() returns the level of CO. For a list of the levels and 509 // their meanings, see cf_defs.h. 510 // 511 // mvar() returns the main variable of CO or Variable() if CO is 512 // in a base domain. 513 // 514 // See also: InternalCF::level(), InternalCF::variable(), 515 // InternalPoly::level(), InternalPoly::variable(), ::level(), 516 // ::mvar() 517 // 518 //}}} 534 535 /** 536 * level() returns the level of CO. For a list of the levels and 537 * their meanings, see cf_defs.h. 538 * 539 * @sa InternalCF::level(), InternalCF::variable(), 540 * InternalPoly::level(), InternalPoly::variable(), ::level(), 541 * ::mvar() 542 * 543 **/ 519 544 int 520 545 CanonicalForm::level () const … … 526 551 } 527 552 553 /** 554 * mvar() returns the main variable of CO or Variable() if CO is 555 * in a base domain. 556 * 557 * @sa InternalCF::level(), InternalCF::variable(), 558 * InternalPoly::level(), InternalPoly::variable(), ::level(), 559 * ::mvar() 560 **/ 528 561 Variable 529 562 CanonicalForm::mvar () const … … 534 567 return value->variable(); 535 568 } 536 //}}} 537 538 //{{{ CanonicalForm CanonicalForm::num (), den () const 539 //{{{ docu 540 // 541 // num(), den() - return numinator and denominator of CO. 542 // 543 // num() returns the numinator of CO if CO is a rational number, 544 // CO itself otherwise. 545 // 546 // den() returns the denominator of CO if CO is a rational 547 // number, 1 (from the current domain!) otherwise. 548 // 549 // See also: InternalCF::num(), InternalCF::den(), 550 // InternalRational::num(), InternalRational::den(), ::num(), 551 // ::den() 552 // 553 //}}} 569 570 /** 571 * num() returns the numerator of CO if CO is a rational number, 572 * CO itself otherwise. 573 * 574 * @sa InternalCF::num(), InternalCF::den(), 575 * InternalRational::num(), InternalRational::den(), ::num(), 576 * ::den() 577 * 578 **/ 554 579 CanonicalForm 555 580 CanonicalForm::num () const … … 561 586 } 562 587 588 /** 589 * den() returns the denominator of CO if CO is a rational 590 * number, 1 (from the current domain!) otherwise. 591 * 592 * @sa InternalCF::num(), InternalCF::den(), 593 * InternalRational::num(), InternalRational::den(), ::num(), 594 * ::den() 595 **/ 563 596 CanonicalForm 564 597 CanonicalForm::den () const … … 569 602 return CanonicalForm( value->den() ); 570 603 } 571 //}}} 572 573 //{{{ assignment operators 604 605 /** assignment operators **/ 574 606 CanonicalForm & 575 607 CanonicalForm::operator += ( const CanonicalForm & cf ) … … 806 838 } 807 839 808 // same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible840 ///same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible 809 841 CanonicalForm & 810 842 CanonicalForm::tryDiv ( const CanonicalForm & cf, const CanonicalForm& M, bool& fail ) … … 1009 1041 } 1010 1042 1011 // same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible1043 ///same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible 1012 1044 bool 1013 1045 tryDivremt ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const CanonicalForm& M, bool& fail ) … … 1060 1092 } 1061 1093 1062 //}}} 1063 1064 //{{{ CanonicalForm CanonicalForm::operator () ( f ), operator () ( f, v ) const 1065 //{{{ docu 1066 // 1067 // operator ()() - evaluation operator. 1068 // 1069 // Both operators return CO if CO is in a base domain. 1070 // 1071 // operator () ( f ) returns CO with f inserted for the main 1072 // variable. Elements in an algebraic extension are considered 1073 // polynomials. 1074 // 1075 // operator () ( f, v ) returns CO with f inserted for v. 1076 // Elements in an algebraic extension are considered polynomials 1077 // and v may be an algebraic variable. 1078 // 1079 //}}} 1094 /** 1095 * 1096 * operator ()() - evaluation operator. 1097 * 1098 * Returns CO if CO is in a base domain. 1099 * 1100 * operator () ( f ) returns CO with f inserted for the main 1101 * variable. Elements in an algebraic extension are considered 1102 * polynomials. 1103 * 1104 **/ 1080 1105 CanonicalForm 1081 1106 CanonicalForm::operator () ( const CanonicalForm & f ) const … … 1123 1148 } 1124 1149 1150 /** 1151 * Returns CO if CO is in a base domain. 1152 * 1153 * operator () ( f, v ) returns CO with f inserted for v. 1154 * Elements in an algebraic extension are considered polynomials 1155 * and v may be an algebraic variable. 1156 **/ 1125 1157 CanonicalForm 1126 1158 CanonicalForm::operator () ( const CanonicalForm & f, const Variable & v ) const … … 1142 1174 } 1143 1175 } 1144 //}}} 1145 1146 //{{{ CanonicalForm CanonicalForm::operator [] ( int i ) const 1147 //{{{ docu 1148 // 1149 // operator []() - return i'th coefficient from CO. 1150 // 1151 // Returns CO if CO is in a base domain and i equals zero. 1152 // Returns zero (from the current domain) if CO is in a base 1153 // domain and i is larger than zero. Otherwise, returns the 1154 // coefficient to x^i in CO (if x denotes the main variable of 1155 // CO) or zero if CO does not contain x^i. Elements in an 1156 // algebraic extension are considered polynomials. i should be 1157 // larger or equal zero. 1158 // 1159 // Note: Never use a loop like 1160 // 1161 // for ( int i = degree( f ); i >= 0; i-- ) 1162 // foo( i, f[ i ] ); 1163 // 1164 // which is much slower than 1165 // 1166 // for ( int i = degree( f ), CFIterator I = f; I.hasTerms(); I++ ) { 1167 // // fill gap with zeroes 1168 // for ( ; i > I.exp(); i-- ) 1169 // foo( i, 0 ); 1170 // // at this point, i == I.exp() 1171 // foo( i, i.coeff() ); 1172 // i--; 1173 // } 1174 // // work through trailing zeroes 1175 // for ( ; i >= 0; i-- ) 1176 // foo( i, 0 ); 1177 // 1178 //}}} 1176 1177 /** 1178 * 1179 * operator []() - return i'th coefficient from CO. 1180 * 1181 * Returns CO if CO is in a base domain and i equals zero. 1182 * Returns zero (from the current domain) if CO is in a base 1183 * domain and i is larger than zero. Otherwise, returns the 1184 * coefficient to x^i in CO (if x denotes the main variable of 1185 * CO) or zero if CO does not contain x^i. Elements in an 1186 * algebraic extension are considered polynomials. i should be 1187 * larger or equal zero. 1188 * 1189 * Note: Never use a loop like 1190 * 1191 ~~~~~~~~~~~~~~~~~~~~~{.c} 1192 for ( int i = degree( f ); i >= 0; i-- ) 1193 foo( i, f[ i ] ); 1194 ~~~~~~~~~~~~~~~~~~~~~ 1195 * 1196 * which is much slower than 1197 * 1198 ~~~~~~~~~~~~~~~~~~~~~{.c} 1199 * for ( int i = degree( f ), CFIterator I = f; I.hasTerms(); I++ ) { 1200 * // fill gap with zeroes 1201 * for ( ; i > I.exp(); i-- ) 1202 * foo( i, 0 ); 1203 * // at this point, i == I.exp() 1204 * foo( i, i.coeff() ); 1205 * i--; 1206 * } 1207 * // work through trailing zeroes 1208 * for ( ; i >= 0; i-- ) 1209 * foo( i, 0 ); 1210 ~~~~~~~~~~~~~~~~~~~~~ 1211 * 1212 **/ 1179 1213 CanonicalForm 1180 1214 CanonicalForm::operator [] ( int i ) const … … 1189 1223 return value->coeff( i ); 1190 1224 } 1191 //}}} 1192 1193 //{{{ CanonicalForm CanonicalForm::deriv (), deriv ( x ) 1194 //{{{ docu 1195 // 1196 // deriv() - return the formal derivation of CO. 1197 // 1198 // deriv() derives CO with respect to its main variable. Returns 1199 // zero from the current domain if f is in a coefficient domain. 1200 // 1201 // deriv( x ) derives CO with respect to x. x should be a 1202 // polynomial variable. Returns zero from the current domain if 1203 // f is in a coefficient domain. 1204 // 1205 // See also: ::deriv() 1206 // 1207 //}}} 1225 1226 /** 1227 * 1228 * deriv() - return the formal derivation of CO. 1229 * 1230 * deriv() derives CO with respect to its main variable. Returns 1231 * zero from the current domain if f is in a coefficient domain. 1232 * 1233 * @sa CanonicalForm::deriv ( const Variable & x ) 1234 * 1235 **/ 1208 1236 CanonicalForm 1209 1237 CanonicalForm::deriv () const … … 1221 1249 } 1222 1250 1251 /** 1252 * deriv( x ) derives CO with respect to x. x should be a 1253 * polynomial variable. Returns zero from the current domain if 1254 * f is in a coefficient domain. 1255 **/ 1223 1256 CanonicalForm 1224 1257 CanonicalForm::deriv ( const Variable & x ) const … … 1240 1273 } 1241 1274 } 1242 //}}} 1243 1244 //{{{ int CanonicalForm::sign () const 1245 //{{{ docu 1246 // 1247 // sign() - return sign of CO. 1248 // 1249 // If CO is an integer or a rational number, the sign is defined 1250 // as usual. If CO is an element of a prime power domain or of 1251 // FF(p) and SW_SYMMETRIC_FF is on, the sign of CO is the sign of 1252 // the symmetric representation of CO. If CO is in GF(q) or in 1253 // FF(p) and SW_SYMMETRIC_FF is off, the sign of CO is zero iff 1254 // CO is zero, otherwise the sign is one. 1255 // 1256 // If CO is a polynomial or in an extension of one of the base 1257 // domains, the sign of CO is the sign of its leading 1258 // coefficient. 1259 // 1260 // See also: InternalCF::sign(), InternalInteger::sign(), 1261 // InternalPrimePower::sign(), InternalRational::sign(), 1262 // InternalPoly::sign(), imm_sign(), gf_sign() 1263 // 1264 //}}} 1275 1276 /** int CanonicalForm::sign () const 1277 * 1278 * sign() - return sign of CO. 1279 * 1280 * If CO is an integer or a rational number, the sign is defined 1281 * as usual. If CO is an element of a prime power domain or of 1282 * FF(p) and SW_SYMMETRIC_FF is on, the sign of CO is the sign of 1283 * the symmetric representation of CO. If CO is in GF(q) or in 1284 * FF(p) and SW_SYMMETRIC_FF is off, the sign of CO is zero iff 1285 * CO is zero, otherwise the sign is one. 1286 * 1287 * If CO is a polynomial or in an extension of one of the base 1288 * domains, the sign of CO is the sign of its leading 1289 * coefficient. 1290 * 1291 * @sa InternalCF::sign(), InternalInteger::sign(), 1292 * InternalRational::sign(), 1293 * InternalPoly::sign(), imm_sign(), gf_sign() 1294 * 1295 **/ 1265 1296 int 1266 1297 CanonicalForm::sign () const … … 1271 1302 return value->sign(); 1272 1303 } 1273 //}}} 1274 1275 //{{{ CanonicalForm CanonicalForm::sqrt () const 1276 //{{{ docu 1277 // 1278 // sqrt() - calculate integer square root. 1279 // 1280 // CO has to be an integer greater or equal zero. Returns the 1281 // largest integer less or equal sqrt(CO). 1282 // 1283 // In the immediate case, we use the newton method to find the 1284 // root. The algorithm is from H. Cohen - 'A Course in 1285 // Computational Algebraic Number Theory', ch. 1.7.1. 1286 // 1287 // See also: InternalCF::sqrt(), InternalInteger::sqrt(), ::sqrt() 1288 // 1289 //}}} 1304 1305 /** CanonicalForm CanonicalForm::sqrt () const 1306 * 1307 * sqrt() - calculate integer square root. 1308 * 1309 * CO has to be an integer greater or equal zero. Returns the 1310 * largest integer less or equal sqrt(CO). 1311 * 1312 * In the immediate case, we use the newton method to find the 1313 * root. The algorithm is from H. Cohen - 'A Course in 1314 * Computational Algebraic Number Theory', ch. 1.7.1. 1315 * 1316 * @sa InternalCF::sqrt(), InternalInteger::sqrt(), ::sqrt() 1317 * 1318 **/ 1290 1319 CanonicalForm 1291 1320 CanonicalForm::sqrt () const … … 1311 1340 return CanonicalForm( value->sqrt() ); 1312 1341 } 1313 //}}} 1314 1315 //{{{ int CanonicalForm::ilog2 () const 1316 //{{{ docu 1317 // 1318 // ilog2() - integer logarithm to base 2. 1319 // 1320 // Returns the largest integer less or equal logarithm of CO to 1321 // base 2. CO should be a positive integer. 1322 // 1323 // See also: InternalCF::ilog2(), InternalInteger::ilog2(), ::ilog2() 1324 // 1325 //}}} 1342 1343 /** int CanonicalForm::ilog2 () const 1344 * 1345 * ilog2() - integer logarithm to base 2. 1346 * 1347 * Returns the largest integer less or equal logarithm of CO to 1348 * base 2. CO should be a positive integer. 1349 * 1350 * @sa InternalCF::ilog2(), InternalInteger::ilog2(), ::ilog2() 1351 * 1352 **/ 1326 1353 int 1327 1354 CanonicalForm::ilog2 () const … … 1343 1370 return value->ilog2(); 1344 1371 } 1345 //}}} 1346 1347 //{{{ bool operator ==, operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs ) 1348 //{{{ docu 1349 // 1350 // operator ==(), operator !=() - compare canonical forms on 1351 // (in)equality. 1352 // 1353 // operator ==() returns true iff lhs equals rhs. 1354 // operator !=() returns true iff lhs does not equal rhs. 1355 // 1356 // This is the point in factory where we essentially use that 1357 // CanonicalForms in fact are canonical. There must not be two 1358 // different representations of the same mathematical object, 1359 // otherwise, such (in)equality will not be recognized by these 1360 // operators. In other word, we rely on the fact that structural 1361 // different factory objects in any case represent different 1362 // mathematical objects. 1363 // 1364 // So we use the following procedure to test on equality (and 1365 // analogously on inequality). First, we check whether lhs.value 1366 // equals rhs.value. If so we are ready and return true. 1367 // Second, if one of the operands is immediate, but the other one 1368 // not, we return false. Third, if the operand's levels differ 1369 // we return false. Fourth, if the operand's levelcoeffs differ 1370 // we return false. At last, we call the corresponding internal 1371 // method to compare both operands. 1372 // 1373 // Both operands should have coefficients from the same base domain. 1374 // 1375 // Note: To compare with the zero or the unit of the current domain, 1376 // you better use the methods `CanonicalForm::isZero()' or 1377 // `CanonicalForm::isOne()', resp., than something like `f == 0', 1378 // since the latter is quite a lot slower. 1379 // 1380 // See also: InternalCF::comparesame(), 1381 // InternalInteger::comparesame(), InternalRational::comparesame(), 1382 // InternalPrimePower::comparesame(), InternalPoly::comparesame() 1383 // 1384 //}}} 1372 1373 /** 1374 * 1375 * operator ==() - compare canonical forms on 1376 * (in)equality. 1377 * 1378 * operator ==() returns true iff lhs equals rhs. 1379 * 1380 * This is the point in factory where we essentially use that 1381 * CanonicalForms in fact are canonical. There must not be two 1382 * different representations of the same mathematical object, 1383 * otherwise, such (in)equality will not be recognized by these 1384 * operators. In other word, we rely on the fact that structural 1385 * different factory objects in any case represent different 1386 * mathematical objects. 1387 * 1388 * So we use the following procedure to test on equality (and 1389 * analogously on inequality). First, we check whether lhs.value 1390 * equals rhs.value. If so we are ready and return true. 1391 * Second, if one of the operands is immediate, but the other one 1392 * not, we return false. Third, if the operand's levels differ 1393 * we return false. Fourth, if the operand's levelcoeffs differ 1394 * we return false. At last, we call the corresponding internal 1395 * method to compare both operands. 1396 * 1397 * Both operands should have coefficients from the same base domain. 1398 * 1399 * Note: To compare with the zero or the unit of the current domain, 1400 * you better use the methods `CanonicalForm::isZero()' or 1401 * `CanonicalForm::isOne()', resp., than something like `f == 0', 1402 * since the latter is quite a lot slower. 1403 * 1404 * @sa CanonicalForm::operator !=(), InternalCF::comparesame(), 1405 * InternalInteger::comparesame(), InternalRational::comparesame(), 1406 * InternalPoly::comparesame() 1407 * 1408 **/ 1385 1409 bool 1386 1410 operator == ( const CanonicalForm & lhs, const CanonicalForm & rhs ) … … 1403 1427 } 1404 1428 1429 /** 1430 * operator !=() returns true iff lhs does not equal rhs. 1431 * 1432 * @sa CanonicalForm::operator ==() 1433 **/ 1405 1434 bool 1406 1435 operator != ( const CanonicalForm & lhs, const CanonicalForm & rhs ) … … 1421 1450 else return rhs.value->comparesame( lhs.value ) != 0; 1422 1451 } 1423 //}}} 1424 1425 //{{{ bool operator >, operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs ) 1426 //{{{ docu 1427 // 1428 // operator >(), operator <() - compare canonical forms. on size or 1429 // level. 1430 // 1431 // The most common and most useful application of these operators 1432 // is to compare two integers or rationals, of course. However, 1433 // these operators are defined on all other base domains and on 1434 // polynomials, too. From a mathematical point of view this may 1435 // seem meaningless, since there is no ordering on finite fields 1436 // or on polynomials respecting the algebraic structure. 1437 // Nevertheless, from a programmer's point of view it may be 1438 // sensible to order these objects, e.g. to sort them. 1439 // 1440 // Therefore, the ordering defined by these operators in any case 1441 // is a total ordering which fulfills the law of trichotomy. 1442 // 1443 // It is clear how this is done in the case of the integers and 1444 // the rationals. For finite fields, all you can say is that 1445 // zero is the minimal element w.r.t. the ordering, the other 1446 // elements are ordered in an arbitrary (but total!) way. For 1447 // polynomials, you have an ordering derived from the 1448 // lexicographical ordering of monomials. E.g. if lm(f) < lm(g) 1449 // w.r.t. lexicographic ordering, then f < g. For more details, 1450 // refer to the documentation of `InternalPoly::operator <()'. 1451 // 1452 // Both operands should have coefficients from the same base domain. 1453 // 1454 // The scheme how both operators are implemented is allmost the 1455 // same as for the assignment operators (check for immediates, 1456 // then check levels, then check levelcoeffs, then call the 1457 // appropriate internal comparesame()/comparecoeff() method). 1458 // For more information, confer to the overview for the 1459 // arithmetic operators. 1460 // 1461 // See also: InternalCF::comparesame(), 1462 // InternalInteger::comparesame(), InternalRational::comparesame(), 1463 // InternalPrimePower::comparesame(), InternalPoly::comparesame(), 1464 // InternalCF::comparecoeff(), InternalInteger::comparecoeff(), 1465 // InternalRational::comparecoeff(), 1466 // InternalPrimePower::comparecoeff(), InternalPoly::comparecoeff(), 1467 // imm_cmp(), imm_cmp_p(), imm_cmp_gf() 1468 // 1469 //}}} 1452 1453 /** 1454 * 1455 * operator >() - compare canonical forms. on size or 1456 * level. 1457 * 1458 * The most common and most useful application of these operators 1459 * is to compare two integers or rationals, of course. However, 1460 * these operators are defined on all other base domains and on 1461 * polynomials, too. From a mathematical point of view this may 1462 * seem meaningless, since there is no ordering on finite fields 1463 * or on polynomials respecting the algebraic structure. 1464 * Nevertheless, from a programmer's point of view it may be 1465 * sensible to order these objects, e.g. to sort them. 1466 * 1467 * Therefore, the ordering defined by these operators in any case 1468 * is a total ordering which fulfills the law of trichotomy. 1469 * 1470 * It is clear how this is done in the case of the integers and 1471 * the rationals. For finite fields, all you can say is that 1472 * zero is the minimal element w.r.t. the ordering, the other 1473 * elements are ordered in an arbitrary (but total!) way. For 1474 * polynomials, you have an ordering derived from the 1475 * lexicographical ordering of monomials. E.g. if lm(f) < lm(g) 1476 * w.r.t. lexicographic ordering, then f < g. For more details, 1477 * refer to the documentation of `InternalPoly::operator <()'. 1478 * 1479 * Both operands should have coefficients from the same base domain. 1480 * 1481 * The scheme how both operators are implemented is allmost the 1482 * same as for the assignment operators (check for immediates, 1483 * then check levels, then check levelcoeffs, then call the 1484 * appropriate internal comparesame()/comparecoeff() method). 1485 * For more information, confer to the overview for the 1486 * arithmetic operators. 1487 * 1488 * @sa CanonicalForm::operator <(), InternalCF::comparesame(), 1489 * InternalInteger::comparesame(), InternalRational::comparesame(), 1490 * InternalPoly::comparesame(), 1491 * InternalCF::comparecoeff(), InternalInteger::comparecoeff(), 1492 * InternalRational::comparecoeff(), 1493 * InternalPoly::comparecoeff(), 1494 * imm_cmp(), imm_cmp_p(), imm_cmp_gf() 1495 * 1496 **/ 1470 1497 bool 1471 1498 operator > ( const CanonicalForm & lhs, const CanonicalForm & rhs ) … … 1496 1523 } 1497 1524 1525 /** 1526 * @sa CanonicalForm::operator >() 1527 **/ 1498 1528 bool 1499 1529 operator < ( const CanonicalForm & lhs, const CanonicalForm & rhs ) … … 1523 1553 return lhs.value->level() < rhs.value->level(); 1524 1554 } 1525 //}}} 1526 1527 //{{{ CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ) 1528 //{{{ docu 1529 // 1530 // bgcd() - return base coefficient gcd. 1531 // 1532 // If both f and g are integers and `SW_RATIONAL' is off the 1533 // positive greatest common divisor of f and g is returned. 1534 // Otherwise, if `SW_RATIONAL' is on or one of f and g is not an 1535 // integer, the greatest common divisor is trivial: either zero 1536 // if f and g equal zero or one (both from the current domain). 1537 // 1538 // f and g should come from one base domain which should be not 1539 // the prime power domain. 1540 // 1541 // Implementation: 1542 // 1543 // CanonicalForm::bgcd() handles the immediate case with a 1544 // standard euclidean algorithm. For the non-immediate cases 1545 // `InternalCF::bgcdsame()' or `InternalCF::bgcdcoeff()', resp. are 1546 // called following the usual level/levelcoeff approach. 1547 // 1548 // InternalCF::bgcdsame() and 1549 // InternalCF::bgcdcoeff() throw an assertion ("not implemented") 1550 // 1551 // InternalInteger::bgcdsame() is a wrapper around `mpz_gcd()' 1552 // which takes some care about immediate results and the sign 1553 // of the result 1554 // InternalInteger::bgcdcoeff() is a wrapper around 1555 // `mpz_gcd_ui()' which takes some care about the sign 1556 // of the result 1557 // 1558 // InternalRational::bgcdsame() and 1559 // InternalRational::bgcdcoeff() always return one 1560 // 1561 //}}} 1555 1556 /** CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ) 1557 * 1558 * bgcd() - return base coefficient gcd. 1559 * 1560 * If both f and g are integers and `SW_RATIONAL' is off the 1561 * positive greatest common divisor of f and g is returned. 1562 * Otherwise, if `SW_RATIONAL' is on or one of f and g is not an 1563 * integer, the greatest common divisor is trivial: either zero 1564 * if f and g equal zero or one (both from the current domain). 1565 * 1566 * f and g should come from one base domain which should be not 1567 * the prime power domain. 1568 * 1569 * Implementation: 1570 * 1571 * CanonicalForm::bgcd() handles the immediate case with a 1572 * standard euclidean algorithm. For the non-immediate cases 1573 * `InternalCF::bgcdsame()' or `InternalCF::bgcdcoeff()', resp. are 1574 * called following the usual level/levelcoeff approach. 1575 * 1576 * InternalCF::bgcdsame() and 1577 * InternalCF::bgcdcoeff() throw an assertion ("not implemented") 1578 * 1579 * InternalInteger::bgcdsame() is a wrapper around `mpz_gcd()' 1580 * which takes some care about immediate results and the sign 1581 * of the result 1582 * InternalInteger::bgcdcoeff() is a wrapper around 1583 * `mpz_gcd_ui()' which takes some care about the sign 1584 * of the result 1585 * 1586 * InternalRational::bgcdsame() and 1587 * InternalRational::bgcdcoeff() always return one 1588 * 1589 **/ 1562 1590 CanonicalForm 1563 1591 bgcd ( const CanonicalForm & f, const CanonicalForm & g ) … … 1628 1656 return f.value->bgcdcoeff( g.value ); 1629 1657 } 1630 //}}} 1631 1632 //{{{ CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) 1633 //{{{ docu 1634 // 1635 // bextgcd() - return base coefficient extended gcd. 1636 // 1637 //}}} 1658 1659 /** CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) 1660 * 1661 * bextgcd() - return base coefficient extended gcd. 1662 * 1663 **/ 1638 1664 CanonicalForm 1639 1665 bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) … … 1729 1755 return f.value->bextgcdcoeff( g.value, a, b ); 1730 1756 } 1731 //}}}1732 1757 1733 1758 CanonicalForm … … 1746 1771 } 1747 1772 1748 / /{{{ input/output1773 /** input/output **/ 1749 1774 #ifndef NOSTREAMIO 1750 1775 void … … 1780 1805 } 1781 1806 #endif /* NOSTREAMIO */ 1782 //}}} 1783 1784 //{{{ genOne(), genZero() 1807 1808 /** genOne(), genZero() **/ 1785 1809 CanonicalForm 1786 1810 CanonicalForm::genZero() const … … 1810 1834 return CanonicalForm( value->genOne() ); 1811 1835 } 1812 //}}} 1813 1814 //{{{ exponentiation 1836 1837 /** exponentiation **/ 1815 1838 CanonicalForm 1816 1839 power ( const CanonicalForm & f, int n ) … … 1855 1878 } 1856 1879 1880 /** exponentiation **/ 1857 1881 CanonicalForm 1858 1882 power ( const Variable & v, int n ) … … 1871 1895 return CanonicalForm( v, n ); 1872 1896 } 1873 //}}} 1874 1875 //{{{ switches 1897 1898 /** switches **/ 1876 1899 void 1877 1900 On( int sw ) … … 1880 1903 } 1881 1904 1905 /** switches **/ 1882 1906 void 1883 1907 Off( int sw ) … … 1886 1910 } 1887 1911 1912 /** switches **/ 1888 1913 bool 1889 1914 isOn( int sw ) … … 1891 1916 return cf_glob_switches.isOn( sw ); 1892 1917 } 1893 //}}}
Note: See TracChangeset
for help on using the changeset viewer.