Changeset 8519cfb in git
 Timestamp:
 Sep 9, 1997, 10:39:02 AM (26 years ago)
 Branches:
 (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
 Children:
 7078880fce41b700d9e350ba47533908fc986463
 Parents:
 030c6813af8a267ae33e85e00dcb4866be1a7aba
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_ops.cc
r030c681 r8519cfb 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: cf_ops.cc,v 1.6 19970901 09:06:19 schmidt Exp $ */ 2 /* $Id: cf_ops.cc,v 1.7 19970909 08:39:02 schmidt Exp $ */ 3 4 //{{{ docu 5 // 6 // cf_ops.cc  simple structural algorithms. 7 // 8 // A 'structural' algorithm is an algorithm which gives 9 // structural information on polynomials in contrast to a 10 // 'mathematical' algorithm which calculates some mathematical 11 // function. 12 // 13 // Compare these functions with the functions in cf_algorithm.cc, 14 // which are mathematical algorithms. 15 // 16 // Used by: allmost everywhere 17 // 18 // Header file: canonicalform.h 19 // 20 //}}} 3 21 4 22 #include <config.h> … … 6 24 #include "assert.h" 7 25 8 #include "cf_defs.h"9 26 #include "canonicalform.h" 27 #include "variable.h" 10 28 #include "cf_iter.h" 11 29 30 //{{{ static Variable sv_x1, sv_x2; 31 //{{{ docu 32 // 33 // sv_x1, sv_x2  variables to swap by swapvar() and replacevar. 34 // 35 // These variables are initialized by swapvar() such that sv_x1 < 36 // sv_x2. They are used by swapvar_between() and swapvar_rec() 37 // to swap variables efficiently. 38 // Furthermore, sv_x1 and sv_x2 are used by replacevar() and 39 // replacevar_between(). 40 // 41 //}}} 42 static Variable sv_x1, sv_x2; 43 //}}} 44 45 //{{{ static void swapvar_between ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & term, int expx2 ) 46 //{{{ docu 47 // 48 // swapvar_between()  replace occurences of sv_x1 in f with sv_x2. 49 // 50 // If Psi denotes the map which maps sv_x1 to sv_x2, this 51 // function returns 52 // 53 // result + Psi(f) * term * sv_x1^expx2 54 // 55 // Used by: swapvar() 56 // 57 //}}} 58 static void 59 swapvar_between ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & term, int expx2 ) 60 { 61 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 62 // in this case, we do not have to replace anything 63 result += term * power( sv_x1, expx2 ) * f; 64 else if ( f.mvar() == sv_x1 ) 65 // this is where the real work is done: this iterator 66 // replaces sv_x1 with sv_x2 67 for ( CFIterator i = f; i.hasTerms(); i++ ) 68 result += power( sv_x2, i.exp() ) * term * power( sv_x1, expx2 ) * i.coeff(); 69 else 70 // f's level is larger than sv_x1: descend down 71 for ( CFIterator i = f; i.hasTerms(); i++ ) 72 swapvar_between( i.coeff(), result, term * power( f.mvar(), i.exp() ), expx2 ); 73 } 74 static CanonicalForm 75 swapvar_between1 ( const CanonicalForm & f ) 76 { 77 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 78 // in this case, we do not have to replace anything 79 return f; 80 else if ( f.mvar() == sv_x1 ) { 81 // this is where the real work is done: this iterator 82 // replaces sv_x1 with sv_x2 83 CanonicalForm result; 84 for ( CFIterator i = f; i.hasTerms(); i++ ) 85 result += power( sv_x2, i.exp() ) * i.coeff(); 86 return result; 87 } 88 else { 89 // f's level is larger than sv_x1: descend down 90 CanonicalForm result; 91 for ( CFIterator i = f; i.hasTerms(); i++ ) 92 result += swapvar_between1( i.coeff() ) * power( f.mvar(), i.exp() ); 93 return result; 94 } 95 } 96 //}}} 97 98 //{{{ static void swapvar_rec ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & term ) 99 //{{{ docu 100 // 101 // swapvar_between()  swap occurences of sv_x1 and sv_x2 in f. 102 // 103 // If Psi denotes the map which swaps sv_x1 and sv_x2, this 104 // function returns 105 // 106 // result + Psi(f) * term 107 // 108 // Used by: swapvar() 109 // 110 //}}} 111 static void 112 swapvar_rec ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & term ) 113 { 114 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 115 // in this case, we do not have to swap anything 116 result += term * f; 117 else if ( f.mvar() == sv_x2 ) 118 // this is where the real work is done: this iterator 119 // replaces sv_x1 with sv_x2 in the coefficients of f and 120 // remembers the exponents of sv_x2 in the last argument 121 // of the call to swapvar_between() 122 for ( CFIterator i = f; i.hasTerms(); i++ ) 123 swapvar_between( i.coeff(), result, term, i.exp() ); 124 else if ( f.mvar() < sv_x2 ) 125 // sv_x2 does not occur in f, but sv_x1 does. Replace it. 126 swapvar_between( f, result, term, 0 ); 127 else 128 // f's level is larger than sv_x2: descend down 129 for ( CFIterator i = f; i.hasTerms(); i++ ) 130 swapvar_rec( i.coeff(), result, term * power( f.mvar(), i.exp() ) ); 131 } 132 static CanonicalForm 133 swapvar_rec1 ( const CanonicalForm & f ) 134 { 135 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 136 return f; 137 else if ( f.mvar() == sv_x2 ) { 138 CanonicalForm result; 139 for ( CFIterator i = f; i.hasTerms(); i++ ) 140 result += swapvar_between1( i.coeff() ) * power( sv_x1, i.exp() ); 141 return result; 142 } 143 else if ( f.mvar() < sv_x2 ) 144 return swapvar_between1( f ); 145 else { 146 CanonicalForm result; 147 for ( CFIterator i = f; i.hasTerms(); i++ ) 148 result += swapvar_rec1( i.coeff() ) * power( f.mvar(), i.exp() ); 149 return result; 150 } 151 } 152 //}}} 153 154 //{{{ CanonicalForm swapvar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) 155 //{{{ docu 156 // 157 // swapvar()  swap variables x1 and x2 in f. 158 // 159 // Returns the image of f under the map which maps x1 to x2 and 160 // x2 to x1. This is done quite efficiently because it is used 161 // really often. x1 and x2 should be polynomial variables. 162 // 163 //}}} 12 164 CanonicalForm 13 psr( const CanonicalForm &f, const CanonicalForm &g, const Variable & x ) 14 { 15 int m = f.degree( x ); 16 int n = g.degree( x ); 17 if ( m < n ) 18 return f; 19 else 20 return ( power( LC(g,x), mn+1 ) * f ) % g; 21 } 22 23 CanonicalForm 24 psq( const CanonicalForm &f, const CanonicalForm &g, const Variable & x ) 25 { 26 return ( power( LC(g,x), degree(f,x)degree(g,x)+1 ) * f ) / g; 27 } 28 29 void 30 psqr( const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable& x ) 31 { 32 divrem( power( LC(g,x), degree(f,x)degree(g,x)+1 ) * f, g, q, r ); 33 } 34 35 static void swapvar_rec ( const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term ); 36 37 static void swapvar_between ( const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term, int expx2 ); 38 39 static Variable sv_x1, sv_x2; 40 41 CanonicalForm 42 swapvar ( const CanonicalForm &f, const Variable &x1, const Variable &x2 ) 165 swapvar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) 43 166 { 44 167 ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic Variables" ); … … 54 177 } 55 178 if ( f.mvar() < sv_x2 ) 179 // we only have to replace sv_x1 by sv_x2 56 180 swapvar_between( f, result, 1, 0 ); 57 181 else 182 // we really have to swap variables 58 183 swapvar_rec( f, result, 1 ); 59 184 return result; 60 185 } 61 186 } 62 63 void 64 swapvar_rec ( const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term ) 65 { 66 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 67 result += term * f; 68 else if ( f.mvar() == sv_x2 ) 69 for ( CFIterator i = f; i.hasTerms(); i++ ) 70 swapvar_between( i.coeff(), result, term, i.exp() ); 71 else if ( f.mvar() < sv_x2 ) 72 swapvar_between( f, result, term, 0 ); 73 else 74 for ( CFIterator i = f; i.hasTerms(); i++ ) 75 swapvar_rec( i.coeff(), result, term*power( f.mvar(), i.exp() ) ); 76 } 77 78 void 79 swapvar_between ( const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term, int expx2 ) 80 { 81 if ( f.inCoeffDomain()  f.mvar() < sv_x1 ) 82 result += term * power( sv_x1, expx2 ) * f; 83 else if ( f.mvar() == sv_x1 ) 84 for ( CFIterator i = f; i.hasTerms(); i++ ) 85 result += power( sv_x2, i.exp() ) * term * i.coeff() * power( sv_x1, expx2 ); 86 else 87 for ( CFIterator i = f; i.hasTerms(); i++ ) 88 swapvar_between( i.coeff(), result, term*power( f.mvar(), i.exp() ), expx2 ); 89 } 90 187 CanonicalForm 188 swapvar1 ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) 189 { 190 ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic variables" ); 191 if ( f.inCoeffDomain()  x1 == x2  ( x1 > f.mvar() && x2 > f.mvar() ) ) 192 return f; 193 else { 194 CanonicalForm result = 0; 195 if ( x1 > x2 ) { 196 sv_x1 = x2; sv_x2 = x1; 197 } 198 else { 199 sv_x1 = x1; sv_x2 = x2; 200 } 201 if ( f.mvar() < sv_x2 ) 202 // we only have to replace sv_x1 by sv_x2 203 return swapvar_between1( f ); 204 else 205 // we really have to swap variables 206 return swapvar_rec1( f ); 207 } 208 } 209 //}}} 210 211 //{{{ static CanonicalForm replacevar_between ( const CanonicalForm & f ) 212 //{{{ docu 213 // 214 // replacevar_between()  replace occurences of sv_x1 in f with sv_x2. 215 // 216 // This is allmost the same as swapvar_between() except that 217 // sv_x1 may be an algebraic variable, so we have to test on 218 // 'f.inBaseDomain()' instead of 'f.inCoeffDomain()' in the 219 // beginning. 220 // 221 // Used by: replacevar() 222 // 223 //}}} 224 static CanonicalForm 225 replacevar_between ( const CanonicalForm & f ) 226 { 227 if ( f.inBaseDomain() ) 228 return f; 229 230 Variable x = f.mvar(); 231 232 if ( x < sv_x1 ) 233 // in this case, we do not have to replace anything 234 return f; 235 else if ( x == sv_x1 ) { 236 // this is where the real work is done: this iterator 237 // replaces sv_x1 with sv_x2 238 CanonicalForm result; 239 for ( CFIterator i = f; i.hasTerms(); i++ ) 240 result += power( sv_x2, i.exp() ) * i.coeff(); 241 return result; 242 } 243 else { 244 // f's level is larger than sv_x1: descend down 245 CanonicalForm result; 246 for ( CFIterator i = f; i.hasTerms(); i++ ) 247 result += replacevar_between( i.coeff() ) * power( x, i.exp() ); 248 return result; 249 } 250 } 251 //}}} 252 253 //{{{ CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) 254 //{{{ docu 255 // 256 // replacevar()  replace all occurences of x1 in f by x2. 257 // 258 // In contrast to swapvar(), x1 may be an algebraic variable, but 259 // x2 must be a polynomial variable. 260 // 261 //}}} 262 CanonicalForm 263 replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) 264 { 265 ASSERT( x2.level() > 0, "cannot replace with algebraic variable" ); 266 if ( f.inBaseDomain()  x1 == x2  ( x1 > f.mvar() ) ) 267 return f; 268 else { 269 sv_x1 = x1; 270 sv_x2 = x2; 271 return replacevar_between( f ); 272 } 273 } 274 //}}} 275 276 //{{{ static void fillVarsRec ( const CanonicalForm & f, int * vars ) 277 //{{{ docu 278 // 279 // fillVarsRec  fill array describing occurences of variables in f. 280 // 281 // Only polynomial variables are looked up. The information is 282 // stored in the arrary vars. vars should be large enough to 283 // hold all information, i.e. larger than the level of f. 284 // 285 // Used by getVars() and getNumVars(). 286 // 287 //}}} 288 static void 289 fillVarsRec ( const CanonicalForm & f, int * vars ) 290 { 291 int n; 292 if ( (n = f.level()) > 0 ) { 293 vars[n] = 1; 294 CFIterator i; 295 for ( i = f; i.hasTerms(); ++i ) 296 fillVarsRec( i.coeff(), vars ); 297 } 298 } 299 //}}} 300 301 //{{{ int getNumVars ( const CanonicalForm & f ) 302 //{{{ docu 303 // 304 // getNumVars()  get number of polynomial variables in f. 305 // 306 //}}} 307 int 308 getNumVars ( const CanonicalForm & f ) 309 { 310 int n; 311 if ( f.inCoeffDomain() ) 312 return 0; 313 else if ( (n = f.level()) == 1 ) 314 return 1; 315 else { 316 int * vars = new int[ n+1 ]; 317 int i; 318 for ( i = 0; i < n; i++ ) vars[i] = 0; 319 320 // look for variables 321 for ( CFIterator I = f; I.hasTerms(); ++I ) 322 fillVarsRec( I.coeff(), vars ); 323 324 // count them 325 int m = 0; 326 for ( i = 1; i < n; i++ ) 327 if ( vars[i] != 0 ) m++; 328 329 delete [] vars; 330 // do not forget to count our own variable 331 return m+1; 332 } 333 } 334 //}}} 335 336 //{{{ CanonicalForm getVars ( const CanonicalForm & f ) 337 //{{{ docu 338 // 339 // getVars()  get polynomial variables of f. 340 // 341 // Return the product of all of them, 1 if there are not any. 342 // 343 //}}} 344 CanonicalForm 345 getVars ( const CanonicalForm & f ) 346 { 347 int n; 348 if ( f.inCoeffDomain() ) 349 return 1; 350 else if ( (n = f.level()) == 1 ) 351 return Variable( 1 ); 352 else { 353 int * vars = new int[ n+1 ]; 354 int i; 355 for ( i = 0; i <= n; i++ ) vars[i] = 0; 356 357 // look for variables 358 for ( CFIterator I = f; I.hasTerms(); ++I ) 359 fillVarsRec( I.coeff(), vars ); 360 361 // multiply them all 362 CanonicalForm result = 1; 363 for ( i = n; i > 0; i ) 364 if ( vars[i] != 0 ) result *= Variable( i ); 365 366 delete [] vars; 367 // do not forget our own variable 368 return f.mvar() * result; 369 } 370 } 371 //}}} 372 373 //{{{ CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) 374 //{{{ docu 375 // 376 // apply()  apply mf to terms of f. 377 // 378 // Calls mf( f[i], i ) for each term f[i]*x^i of f and builds a 379 // new term from the result. If f is in a coefficient domain, 380 // mf( f, i ) should result in an i == 0, since otherwise it is 381 // not clear which variable to use for the resulting term. 382 // 383 // An example: 384 // 385 // void 386 // diff( CanonicalForm & f, int & i ) 387 // { 388 // f = f * i; 389 // if ( i > 0 ) i; 390 // } 391 // 392 // Then apply( f, diff ) is differentation of f with respect to the 393 // main variable of f. 394 // 395 //}}} 91 396 CanonicalForm 92 397 apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) … … 94 399 if ( f.inCoeffDomain() ) { 95 400 int exp = 0; 96 CanonicalForm result ;401 CanonicalForm result = f; 97 402 mf( result, exp ); 98 403 ASSERT( exp == 0, "illegal result, do not know what variable to use" ); … … 114 419 } 115 420 } 421 //}}} 422 423 //{{{ CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) 424 //{{{ docu 425 // 426 // mapdomain()  map all coefficients of f through mf. 427 // 428 // Recursively descends down through f to the coefficients which 429 // are in a coefficient domain mapping each such coefficient 430 // through mf and returns the result. 431 // 432 //}}} 433 CanonicalForm 434 mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) 435 { 436 if ( f.inCoeffDomain() ) 437 return mf( f ); 438 else { 439 CanonicalForm result = 0; 440 CFIterator i; 441 Variable x = f.mvar(); 442 for ( i = f; i.hasTerms(); i++ ) 443 result += power( x, i.exp() ) * mapdomain( i.coeff(), mf ); 444 return result; 445 } 446 } 447 //}}} 116 448 117 449 //{{{ static void degreesRec ( const CanonicalForm & f, int * degs ) … … 119 451 // 120 452 // degreesRec()  recursively get degrees of f. 453 // 454 // Used by degrees(). 121 455 // 122 456 //}}} … … 166 500 degreesRec( f, degs ); 167 501 return degs; 168 }169 }170 //}}}171 172 //{{{ CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )173 //{{{ docu174 //175 // mapdomain()  map all coefficients of f through mf.176 //177 // Recursively descends down through f to the coefficients which178 // are in a coefficient domain mapping each such coefficient179 // through mf and returns the result.180 //181 //}}}182 CanonicalForm183 mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )184 {185 if ( f.inCoeffDomain() )186 return mf( f );187 else {188 CanonicalForm result = 0;189 CFIterator i;190 Variable x = f.mvar();191 for ( i = f; i.hasTerms(); i++ )192 result += power( x, i.exp() ) * mapdomain( i.coeff(), mf );193 return result;194 502 } 195 503 } … … 274 582 } 275 583 //}}} 276 277 //{{{ static void fillVarsRec ( const CanonicalForm & f, int * vars )278 //{{{ docu279 //280 // fillVarsRec  fill array describing occurences of variables in f.281 //282 // Only polynomial variables are looked up. The information is283 // stored in the arrary vars. vars should be large enough to284 // hold all information, i.e. larger than the level of f.285 //286 //}}}287 static void288 fillVarsRec ( const CanonicalForm & f, int * vars )289 {290 int n;291 if ( (n = f.level()) > 0 ) {292 vars[n] = 1;293 CFIterator i;294 for ( i = f; i.hasTerms(); ++i )295 fillVarsRec( i.coeff(), vars );296 }297 }298 //}}}299 300 //{{{ int getNumVars( const CanonicalForm & f )301 //{{{ docu302 //303 // getNumVars()  get number of polynomial variables in f.304 //305 //}}}306 int307 getNumVars( const CanonicalForm & f )308 {309 int n;310 if ( f.inCoeffDomain() )311 return 0;312 else if ( (n = f.level()) == 1 )313 return 1;314 else {315 int * vars = new int[ n+1 ];316 int i;317 for ( i = 0; i < n; i++ ) vars[i] = 0;318 319 // look for variables320 for ( CFIterator I = f; I.hasTerms(); ++I )321 fillVarsRec( I.coeff(), vars );322 323 // count them324 int m = 0;325 for ( i = 1; i < n; i++ )326 if ( vars[i] != 0 ) m++;327 328 delete [] vars;329 // do not forget to count our own variable330 return m+1;331 }332 }333 //}}}334 335 //{{{ CanonicalForm getVars( const CanonicalForm & f )336 //{{{ docu337 //338 // getVars()  get polynomial variables of f.339 //340 // Return the product of all of them, 1 if there are not any.341 //342 //}}}343 CanonicalForm344 getVars( const CanonicalForm & f )345 {346 int n;347 if ( f.inCoeffDomain() )348 return 1;349 else if ( (n = f.level()) == 1 )350 return Variable( 1 );351 else {352 int * vars = new int[ n+1 ];353 int i;354 for ( i = 0; i <= n; i++ ) vars[i] = 0;355 356 // look for variables357 for ( CFIterator I = f; I.hasTerms(); ++I )358 fillVarsRec( I.coeff(), vars );359 360 // multiply them all361 CanonicalForm result = 1;362 for ( i = n; i > 0; i )363 if ( vars[i] != 0 ) result *= Variable( i );364 365 delete [] vars;366 // do not forget our own variable367 return f.mvar() * result;368 }369 }370 //}}}371 372 static CanonicalForm373 cden ( const CanonicalForm & f )374 {375 if ( f.inCoeffDomain() )376 return f.den();377 else {378 CFIterator i;379 CanonicalForm cd = 1;380 for ( i = f; i.hasTerms(); i++ )381 cd = lcm( cd, cden( i.coeff() ) );382 return cd;383 }384 }385 386 CanonicalForm387 common_den ( const CanonicalForm & f )388 {389 if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) {390 Off( SW_RATIONAL );391 CanonicalForm cd = cden( f );392 On( SW_RATIONAL );393 return cd;394 }395 else396 return 1;397 }
Note: See TracChangeset
for help on using the changeset viewer.