 Timestamp:
 Mar 12, 1998, 11:26:14 AM (26 years ago)
 Branches:
 (u'spielwiese', 'd1b01e9d51ade4b46b745d3bada5c5f3696be3a8')
 Children:
 041dbdc0753163b5283d5d03266a061267c59427
 Parents:
 91c4fc82713e72893b097592af3f701d13a4f992
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/cf_algorithm.cc
r91c4fc8 r9719434 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: cf_algorithm.cc,v 1. 5 19971009 14:48:19schmidt Exp $ */2 /* $Id: cf_algorithm.cc,v 1.6 19980312 10:26:14 schmidt Exp $ */ 3 3 4 4 //{{{ docu … … 14 14 // 15 15 // Used by: cf_gcd.cc, cf_resultant.cc, fac_distrib.cc, 16 // fac_ezgcd.cc, sm_sparsemod.cc16 // fac_ezgcd.cc, fac_util.cc, sm_sparsemod.cc 17 17 // 18 18 //}}} … … 24 24 #include "cf_defs.h" 25 25 #include "canonicalform.h" 26 #include "cf_algorithm.h" 26 27 #include "variable.h" 27 28 #include "cf_iter.h" … … 30 31 //{{{ docu 31 32 // 32 // psr()  calculate pseudo remainder of f and g with respect to x. 33 // 34 // x should be a polynomial variable. 33 // psr()  calculate pseudo remainder of `f' and `g' with respect 34 // to `x'. 35 // 36 // `x' should be a polynomial variable, `g' must not equal zero. 35 37 // 36 38 // For f and g in R[x], R an integral domain, g != 0, there is a … … 51 53 psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) 52 54 { 53 ASSERT( x.level() > 0, " cannot calculate pseudo remainder/quotient with respect to algebraic variables" );55 ASSERT( x.level() > 0, "illegal variable" ); 54 56 ASSERT( g != 0, "division by zero" ); 55 57 … … 66 68 //{{{ docu 67 69 // 68 // psq()  calculate pseudo quotient of f and g with respect to x. 69 // 70 // x should be a polynomial variable. See psr() for more 71 // detailed information. 70 // psq()  calculate pseudo quotient of `f' and `g' with respect 71 // to `x'. 72 // 73 // `x' should be a polynomial variable, `g' must not equal zero. 74 // See `psr()' for more detailed information. 72 75 // 73 76 //}}} … … 75 78 psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) 76 79 { 77 ASSERT( x.level() > 0, " cannot calculate pseudo remainder/quotient with respect to algebraic variables" );80 ASSERT( x.level() > 0, "illegal variable" ); 78 81 ASSERT( g != 0, "division by zero" ); 79 82 … … 90 93 //{{{ docu 91 94 // 92 // psqr()  calculate pseudo quotient and remainder of f and g with respect to x. 93 // 94 // x should be a polynomial variable. See psr() for more 95 // detailed information. 95 // psqr()  calculate pseudo quotient and remainder of `f' and 96 // `g' with respect to `x'. 97 // 98 // `x' should be a polynomial variable, `g' must not equal zero. 99 // See `psr()' for more detailed information. 96 100 // 97 101 //}}} … … 99 103 psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable& x ) 100 104 { 101 ASSERT( x.level() > 0, " cannot calculate pseudo remainder/quotient with respect to algebraic variables" );105 ASSERT( x.level() > 0, "illegal variable" ); 102 106 ASSERT( g != 0, "division by zero" ); 103 107 … … 112 116 //}}} 113 117 114 //{{{ static CanonicalForm cden ( const CanonicalForm & f )115 //{{{ docu 116 // 117 // cden()  recursively calculate multivariate common denominator118 // of coefficients of f.119 // 120 // Used by: common_den()118 //{{{ static CanonicalForm internalBCommonDen ( const CanonicalForm & f ) 119 //{{{ docu 120 // 121 // internalBCommonDen()  recursively calculate multivariate 122 // common denominator of coefficients of `f'. 123 // 124 // Used by: bCommonDen() 121 125 // 122 126 //}}} 123 127 static CanonicalForm 124 cden ( const CanonicalForm & f )128 internalBCommonDen ( const CanonicalForm & f ) 125 129 { 126 130 if ( f.inBaseDomain() ) 127 131 return f.den(); 128 132 else { 129 CFIterator i; 130 CanonicalForm cd = 1; 131 for ( i = f; i.hasTerms(); i++ ) 132 cd = lcm( cd, cden( i.coeff() ) ); 133 return cd; 134 } 135 } 136 //}}} 137 138 //{{{ CanonicalForm common_den ( const CanonicalForm & f ) 139 //{{{ docu 140 // 141 // common_den()  calculate multivariate common denominator of 142 // coefficients of f. 133 CanonicalForm result = 1; 134 for ( CFIterator i = f; i.hasTerms(); i++ ) 135 result = blcm( result, internalBCommonDen( i.coeff() ) ); 136 return result; 137 } 138 } 139 //}}} 140 141 //{{{ CanonicalForm bCommonDen ( const CanonicalForm & f ) 142 //{{{ docu 143 // 144 // bCommonDen()  calculate multivariate common denominator of 145 // coefficients of `f'. 143 146 // 144 147 // The common denominator is calculated with respect to all 145 // coefficients of f which are in a base domain. In other words, 146 // common_den( f ) * f is guaranteed to have integer 147 // coefficients only. 148 // 149 // Returns one for domains other than Q. 150 // 151 //}}} 152 CanonicalForm 153 common_den ( const CanonicalForm & f ) 148 // coefficients of `f' which are in a base domain. In other 149 // words, common_den( `f' ) * `f' is guaranteed to have integer 150 // coefficients only. The common denominator of zero equals is 151 // one. 152 // 153 // Returns something nontrivial iff the current domain is Q. 154 // 155 //}}} 156 CanonicalForm 157 bCommonDen ( const CanonicalForm & f ) 154 158 { 155 159 if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) { 156 // switch to Z so lcm() will work correctly160 // otherwise `bgcd()' returns one 157 161 Off( SW_RATIONAL ); 158 CanonicalForm cd = cden( f );162 CanonicalForm result = internalBCommonDen( f ); 159 163 On( SW_RATIONAL ); 160 return cd; 161 } 162 else 163 return 1; 164 return result; 165 } else 166 return CanonicalForm( 1 ); 164 167 } 165 168 //}}} … … 168 171 //{{{ docu 169 172 // 170 // divides()  check whether f divides g.173 // divides()  check whether `f' divides `g'. 171 174 // 172 175 // Uses some extra checks to avoid polynomial division. … … 180 183 CanonicalForm q, r; 181 184 bool ok = divremt( g, f, q, r ); 182 return ok && r == 0;185 return ok && r.isZero(); 183 186 } 184 187 else … … 187 190 CanonicalForm q, r; 188 191 bool ok = divremt( g, f, q, r ); 189 return ok && r == 0; 190 } 191 } 192 //}}} 192 return ok && r.isZero(); 193 } 194 } 195 //}}} 196 197 //{{{ CanonicalForm maxNorm ( const CanonicalForm & f ) 198 //{{{ docu 199 // 200 // maxNorm()  get maximum norm of `f'. 201 // 202 // That is, the base coefficient of `f' with the largest absolute 203 // value. 204 // 205 // Valid for arbitrary polynomials over arbitrary domains, but 206 // most useful for multivariate polynomials over Z. 207 // 208 //}}} 209 CanonicalForm 210 maxNorm ( const CanonicalForm & f ) 211 { 212 if ( f.inBaseDomain() ) 213 return abs( f ); 214 else { 215 CanonicalForm result = 0; 216 for ( CFIterator i = f; i.hasTerms(); i++ ) { 217 CanonicalForm coeffMaxNorm = maxNorm( i.coeff() ); 218 if ( coeffMaxNorm > result ) 219 result = coeffMaxNorm; 220 } 221 return result; 222 } 223 } 224 //}}} 225 226 //{{{ CanonicalForm euclideanNorm ( const CanonicalForm & f ) 227 //{{{ docu 228 // 229 // euclideanNorm()  get euclidean norm of `f'. 230 // 231 // That is, returns the largest integer smaller or equal 232 // norm(`f') = sqrt(sum( `f'[i]^2 )). `f' should be an 233 // univariate polynomial over Z. 234 // 235 //}}} 236 CanonicalForm 237 euclideanNorm ( const CanonicalForm & f ) 238 { 239 ASSERT( (f.inBaseDomain()  f.isUnivariate()) && f.LC().inZ(), 240 "illegal polynomial" ); 241 242 CanonicalForm result = 0; 243 for ( CFIterator i = f; i.hasTerms(); i++ ) { 244 CanonicalForm coeff = i.coeff(); 245 result += coeff*coeff; 246 } 247 return sqrt( result ); 248 } 249 //}}}
Note: See TracChangeset
for help on using the changeset viewer.