Changeset cae0b6 in git
- Timestamp:
- Oct 10, 2002, 7:43:40 PM (21 years ago)
- Branches:
- (u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
- Children:
- 7724a3281f0baa9aa017ab10865fcac877d85684
- Parents:
- cbe9af8559b8f0a37f140c253c032b29f7d4103a
- Location:
- factory
- Files:
-
- 5 edited
-
NTLconvert.cc (modified) (2 diffs)
-
cf_factor.cc (modified) (4 diffs)
-
fac_distrib.cc (modified) (8 diffs)
-
fac_multihensel.cc (modified) (2 diffs)
-
fac_multivar.cc (modified) (10 diffs)
Legend:
- Unmodified
- Added
- Removed
-
factory/NTLconvert.cc
rcbe9af8 rcae0b6 1 /* $Id: NTLconvert.cc,v 1. 3 2002-08-19 11:10:41Singular Exp $ */1 /* $Id: NTLconvert.cc,v 1.4 2002-10-10 17:43:38 Singular Exp $ */ 2 2 #include <config.h> 3 3 … … 586 586 // Start by appending the multiplicity 587 587 588 if (!IsOne(multi))588 //if (!IsOne(multi)) 589 589 rueckgabe.append(CFFactor(convertZZ2CF(multi),1)); 590 590 -
factory/cf_factor.cc
rcbe9af8 rcae0b6 1 1 /* emacs edit mode for this file is -*- C++ -*- */ 2 /* $Id: cf_factor.cc,v 1.1 5 2002-09-24 11:28:29 Singular Exp $ */2 /* $Id: cf_factor.cc,v 1.16 2002-10-10 17:43:39 Singular Exp $ */ 3 3 4 4 //{{{ docu … … 174 174 if ( f.inCoeffDomain() ) 175 175 return CFFList( f ); 176 //out_cf("factorize:",f,"==================================\n"); 176 177 int mv=f.level(); 178 int org_v=mv; 177 179 if (! f.isUnivariate() ) 178 180 { 179 181 mv=find_mvar(f); 180 if (mv!=f.level()) 181 { 182 swapvar(f,Variable(mv),f.mvar()); 183 } 184 if ( getCharacteristic() == 0 ) Off(SW_USE_NTL); 182 if ( getCharacteristic() > 0 ) 183 { 184 if (mv!=f.level()) 185 { 186 swapvar(f,Variable(mv),f.mvar()); 187 } 188 } 189 else 190 { 191 if (mv!=1) 192 { 193 swapvar(f,Variable(mv),Variable(1)); 194 org_v=1; 195 } 196 } 185 197 } 186 198 CFFList F; … … 274 286 F.insert( CFFactor( ic ) ); 275 287 } 276 if ( F.getFirst().factor().isOne() ) 277 { 278 F.removeFirst(); 279 } 288 else 289 { 290 if ( !F.getFirst().factor().inCoeffDomain() ) 291 { 292 CFFactor new_first( 1 ); 293 F.insert( new_first ); 294 } 295 } 296 //if ( F.getFirst().factor().isOne() ) 297 //{ 298 // F.removeFirst(); 299 //} 280 300 } 281 301 else … … 306 326 } 307 327 308 if ((mv!= f.level()) && (! f.isUnivariate() ))328 if ((mv!=org_v) && (! f.isUnivariate() )) 309 329 { 310 330 CFFListIterator J=F; 311 331 for ( ; J.hasItem(); J++) 312 332 { 313 swapvar(J.getItem().factor(),Variable(mv),f.mvar()); 314 } 315 swapvar(f,Variable(mv),f.mvar()); 316 } 333 swapvar(J.getItem().factor(),Variable(mv),Variable(org_v)); 334 } 335 swapvar(f,Variable(mv),Variable(org_v)); 336 } 337 //out_cff(F); 317 338 return F; 318 339 } 340 319 341 #ifdef HAVE_NTL 320 342 CanonicalForm fntl ( const CanonicalForm & f, int j ) -
factory/fac_distrib.cc
rcbe9af8 rcae0b6 1 1 /* emacs edit mode for this file is -*- C++ -*- */ 2 /* $Id: fac_distrib.cc,v 1. 6 1997-10-09 14:47:17 schmidtExp $ */2 /* $Id: fac_distrib.cc,v 1.7 2002-10-10 17:43:40 Singular Exp $ */ 3 3 4 4 #include <config.h> … … 22 22 d[0] = delta * omega; 23 23 for ( int i = 1; i <= k; i++ ) { 24 25 26 27 28 29 30 31 32 33 34 35 36 24 q = abs(F[i]); 25 for ( int j = i-1; j >= 0; j-- ) { 26 r = d[j]; 27 do { 28 r = gcd( r, q ); 29 q = q / r; 30 } while ( r != 1 ); 31 if ( q == 1 ) { 32 DEBDECLEVEL( cerr, "nonDivisors" ); 33 return false; 34 } 35 } 36 d[i] = q; 37 37 } 38 38 DEBDECLEVEL( cerr, "nonDivisors" ); … … 50 50 Vn = A( lcU ); 51 51 if ( Vn.isZero() ) 52 52 return false; 53 53 delta = content( U0 ); 54 54 for ( I = F, j = 1; I.hasItem(); I++, j++ ) 55 55 FF[j] = A( I.getItem().factor() ); 56 56 return nonDivisors( omega, delta, FF, D ); 57 57 } … … 67 67 lcG = CFArray( 1, r ); 68 68 for ( j = 1; j <= r; j ++ ) 69 69 lcG[j] = 1; 70 70 71 71 for ( I = F, i = 1; I.hasItem(); I++, i++ ) { 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 72 ft = I.getItem().factor(); 73 m = I.getItem().exp(); 74 DEBOUTLN( cerr, "trying to distribute " << ft ); 75 DEBOUTLN( cerr, "which is tested with " << D[i] ); 76 DEBOUTLN( cerr, "and contained to the power of " << m ); 77 j = 1; 78 while ( m > 0 && j <= r ) { 79 ut = lc( G[j] ); 80 DEBOUTLN( cerr, "checking with " << ut ); 81 while ( m > 0 && divides( D[i], ut ) ) { 82 DEBOUTLN( cerr, "match found" ); 83 m--; ut /= D[i]; 84 lcG[j] *= ft; 85 } 86 j++; 87 } 88 if (m != 0) { 89 DEBDECLEVEL( cerr, "distributeLeadingCoeffs" ); 90 return false; 91 } 92 92 } 93 93 DEBOUTLN( cerr, "the leading coeffs before omega and delta correction: " << lcG ); 94 94 if ( omega != 1 ) { 95 96 // 97 98 99 100 95 for ( j = 1; j <= r; j++ ) { 96 // G[j] *= omega; 97 lcG[j] *= omega; 98 G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) ); 99 } 100 U *= power( omega, r-1 ); 101 101 } 102 102 if ( delta != 1 ) { 103 104 105 106 107 103 for ( j = 1; j <= r; j++ ) { 104 lcG[j] *= delta; 105 G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) ); 106 } 107 U *= power( delta, r ); 108 108 } 109 109 DEBDECLEVEL( cerr, "distributeLeadingCoeffs" ); … … 116 116 { 117 117 if ( F.isOne() ) 118 118 return; 119 119 if ( L.isEmpty() ) { 120 121 120 L.append( F ); 121 return; 122 122 } 123 123 CanonicalForm h, f = F; 124 124 CFListIterator i, j; 125 125 for ( i = L; i.hasItem() && ! f.isOne(); ) { 126 127 128 129 130 131 132 133 134 135 136 137 126 h = gcd( f, i.getItem() ); 127 if ( h.isOne() ) { 128 i++; 129 continue; 130 } 131 while ( divides( h, f ) ) 132 f /= h; 133 CFList D( h ); 134 gfbAdjoin( i.getItem() / h, D ); 135 for ( j = D; j.hasItem(); j++ ) 136 i.append( j.getItem() ); 137 i.remove( true ); 138 138 } 139 139 if ( ! f.isOne() ) 140 140 L.append( f ); 141 141 } 142 142 … … 148 148 CFList R; 149 149 for ( i = L; i.hasItem(); i++ ) 150 150 gfbAdjoin( i.getItem(), R ); 151 151 return R; 152 152 } … … 159 159 CFArray lcG(1,n); 160 160 for ( int i = 1; i <= n; i++ ) { 161 162 161 G[i] *= A(l)/lc(G[i]); 162 lcG[i] = l; 163 163 } 164 164 return Hensel( U * power( l, n-1 ), G, lcG, A, bound, x ); … … 171 171 CFArray TrueLcs(1, n); 172 172 for (i=1; i <= n; i++) 173 173 TrueLcs[i] = 1; 174 174 Variable y; 175 175 CanonicalForm lcU = LC ( U, Variable(1) ); 176 176 while (! lcU.inCoeffDomain()) 177 177 { 178 179 180 181 182 183 184 185 186 187 188 // 189 // 178 y = lcU.mvar(); // should make a more intelligent choice 179 CanonicalForm BivariateU = A ( U, 2, y.level() - 1 ); 180 CFArray BivariateFactors = G; 181 CFArray lcFactors(1,n); 182 Univar2Bivar(BivariateU, BivariateFactors, A, bound, y); 183 for (i = 1; i <= n; i++) 184 { 185 BivariateFactors[i] /= content(BivariateFactors[i]); 186 lcFactors[i] = LC(BivariateFactors[i],Variable(1)); 187 } 188 // GFB = GcdFreeBasis(lcFactors); // this is not right... should probably make everything squarefree 189 // Hensel2(lcU, GFB, A, bound, y); 190 190 } 191 191 for (i = 1; i <= n; i++) 192 192 G[i] *= A(TrueLcs[i])/lc(G[i]); 193 193 return Hensel(U, G, TrueLcs, A, bound, x); 194 194 } -
factory/fac_multihensel.cc
rcbe9af8 rcae0b6 1 1 /* emacs edit mode for this file is -*- C++ -*- */ 2 /* $Id: fac_multihensel.cc,v 1. 7 2001-01-19 18:11:51Singular Exp $ */2 /* $Id: fac_multihensel.cc,v 1.8 2002-10-10 17:43:40 Singular Exp $ */ 3 3 4 4 #include <config.h> … … 229 229 DEBOUTLN( cerr, "we are now performing the liftstep to reach " << Variable(k) ); 230 230 DEBOUTLN( cerr, "the factors so far are " << P ); 231 DEBOUTLN( cerr, "modulus p^k= " << b.getpk() << "=" << b.getp() <<"^"<< b.getk() ); 231 232 232 233 for ( i = 1; i <= r; i++ ) { -
factory/fac_multivar.cc
rcbe9af8 rcae0b6 1 1 /* emacs edit mode for this file is -*- C++ -*- */ 2 /* $Id: fac_multivar.cc,v 1. 8 1998-03-12 14:30:55 schmidtExp $ */2 /* $Id: fac_multivar.cc,v 1.9 2002-10-10 17:43:40 Singular Exp $ */ 3 3 4 4 #include <config.h> … … 17 17 #include "cf_binom.h" 18 18 #include "cf_iter.h" 19 #include "cf_primes.h" 19 20 #include "fac_distrib.h" 20 21 … … 33 34 34 35 if ( ! I.hasItem() ) 35 36 n = 0; 36 37 else if ( I.getItem().factor().inBaseDomain() ) { 37 38 39 38 negate = I.getItem().factor().sign() < 0; 39 I++; 40 n = L.length(); 40 41 } 41 42 else 42 43 n = L.length() + 1; 43 44 CFFListIterator J = I; 44 45 while ( J.hasItem() ) { 45 46 46 n += J.getItem().exp() - 1; 47 J++; 47 48 } 48 49 CFArray result( 1, n-1 ); … … 50 51 i = 1; 51 52 while ( I.hasItem() ) { 52 53 54 55 56 57 53 k = I.getItem().exp(); 54 for ( j = 1; j <= k; j++ ) { 55 result[i] = I.getItem().factor(); 56 i++; 57 } 58 I++; 58 59 } 59 60 if ( negate ) 60 61 result[1] = -result[1]; 61 62 return result; 62 63 } … … 68 69 int M = 0, i, k = f.level(); 69 70 for ( i = 1; i <= k; i++ ) 70 71 M += degs[i]; 71 72 CanonicalForm b = 2 * maxNorm( f ) * power( CanonicalForm( 3 ), M ); 72 73 CanonicalForm B = p; 73 74 k = 1; 74 75 while ( B < b ) { 75 76 76 B *= p; 77 k++; 77 78 } 78 79 return modpk( p, k ); … … 90 91 // d[0] = delta * omega; 91 92 // for ( int i = 1; i <= k; i++ ) { 92 // 93 // 94 // 95 // 96 // 97 // 98 // 99 // 100 // 101 // 102 // 93 // q = abs(F[i]); 94 // for ( int j = i-1; j >= 0; j-- ) { 95 // r = d[j]; 96 // do { 97 // r = gcd( r, q ); 98 // q = q / r; 99 // } while ( r != 1 ); 100 // if ( q == 1 ) 101 // return false; 102 // } 103 // d[i] = q; 103 104 // } 104 105 // return true; … … 115 116 CFArray FF = CFArray( 1, F.length() ); 116 117 if ( r > 0 ) 117 118 A.nextpoint(); 118 119 while ( ! found ) { 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 120 Vn = A( V ); 121 if ( Vn != 0 ) { 122 U0 = A( U ); 123 DEBOUTLN( cerr, "U0 = " << U0 ); 124 if ( isSqrFree( U0 ) ) { 125 delta = content( U0 ); 126 DEBOUTLN( cerr, "content( U0 ) = " << delta ); 127 for ( I = F, j = 1; I.hasItem(); I++, j++ ) 128 FF[j] = A( I.getItem().factor() ); 129 found = nonDivisors( omega, delta, FF, D ); 130 } 131 else { 132 DEBOUTLN( cerr, "not sqrfree : " << sqrFree( U0 ) ); 133 } 134 } 135 if ( ! found ) 136 A.nextpoint(); 136 137 } 137 138 DEBDECLEVEL( cerr, "findEvaluation" ); 138 139 } 140 141 #ifdef HAVE_NTL 142 int prime_number=0; 143 void find_good_prime(const CanonicalForm &f, const CanonicalForm &r,int &start) 144 { 145 if (! f.inBaseDomain() ) 146 { 147 int l = f.level(); 148 for ( CFIterator i = f; i.hasTerms(); i++ ) 149 { 150 find_good_prime(i.coeff(),r,start); 151 } 152 } 153 else 154 { 155 if(mod(f,cf_getSmallPrime(start))==0) 156 { 157 start++; 158 CanonicalForm ff=r; 159 find_good_prime(ff,r,start); 160 } 161 } 162 } 163 #endif 139 164 140 165 static CFArray … … 165 190 maxdeg = 0; 166 191 for ( i = 2; i <= t; i++ ) { 167 168 192 j = U.degree( Variable( i ) ); 193 if ( j > maxdeg ) maxdeg = j; 169 194 } 170 195 171 196 if ( F.getFirst().factor().inCoeffDomain() ) { 172 173 174 175 176 177 178 197 omega = F.getFirst().factor(); 198 F.removeFirst(); 199 if ( omega < 0 ) { 200 negate = true; 201 omega = -omega; 202 U = -U; 203 } 179 204 } 180 205 else 181 206 omega = 1; 182 207 183 208 bool goodeval = false; … … 185 210 186 211 // for ( i = 0; i < 10*t; i++ ) 187 // 212 // A.nextpoint(); 188 213 189 214 while ( ! goodeval ) { 190 TIMING_START(fac_findeval); 191 findEvaluation( U, V, omega, F, A, U0, delta, D, r ); 192 TIMING_END(fac_findeval); 193 DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is " << A ); 194 DEBOUTLN( cerr, "corresponding delta = " << delta ); 195 DEBOUTLN( cerr, " omega = " << omega ); 196 DEBOUTLN( cerr, " D = " << D ); 197 DEBOUTLN( cerr, "now factorize the univariate polynomial " << U0 ); 198 G = conv_to_factor_array( factorize( U0, false ) ); 199 DEBOUTLN( cerr, "which factorizes into " << G ); 200 b = coeffBound( U, getZFacModulus().getp() ); 201 if ( getZFacModulus().getpk() > b.getpk() ) 202 b = getZFacModulus(); 203 DEBOUTLN( cerr, "the coefficient bound of the factors of U is " << b.getpk() ); 204 205 r = G.size(); 206 lcG = CFArray( 1, r ); 207 UU = U; 208 DEBOUTLN( cerr, "now trying to distribute the leading coefficients ..." ); 209 TIMING_START(fac_distrib); 210 goodeval = distributeLeadingCoeffs( UU, G, lcG, F, D, delta, omega, A, r ); 211 TIMING_END(fac_distrib); 215 TIMING_START(fac_findeval); 216 findEvaluation( U, V, omega, F, A, U0, delta, D, r ); 217 TIMING_END(fac_findeval); 218 DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is " << A ); 219 DEBOUTLN( cerr, "corresponding delta = " << delta ); 220 DEBOUTLN( cerr, " omega = " << omega ); 221 DEBOUTLN( cerr, " D = " << D ); 222 DEBOUTLN( cerr, "now factorize the univariate polynomial " << U0 ); 223 G = conv_to_factor_array( factorize( U0, false ) ); 224 DEBOUTLN( cerr, "which factorizes into " << G ); 225 #ifdef HAVE_NTL 226 { 227 int i=prime_number; 228 CanonicalForm f=arg; 229 find_good_prime(f,arg,i); 230 f=U0; 231 find_good_prime(f,U0,i); 232 f=U; 233 find_good_prime(f,U,i); 234 int p=cf_getSmallPrime(i); 235 //printf("found:p=%d (%d)\n",p,i); 236 if ((i==0)||(i!=prime_number)) 237 { 238 b = coeffBound( U, p ); 239 prime_number=i; 240 } 241 modpk bb=coeffBound(U0,p); 242 if (bb.getpk() > b.getpk() ) b=bb; 243 bb=coeffBound(arg,p); 244 if (bb.getpk() > b.getpk() ) b=bb; 245 } 246 #else 247 b = coeffBound( U, getZFacModulus().getp() ); 248 if ( getZFacModulus().getpk() > b.getpk() ) 249 b = getZFacModulus(); 250 #endif 251 DEBOUTLN( cerr, "the coefficient bound of the factors of U is " << b.getpk() ); 252 253 r = G.size(); 254 lcG = CFArray( 1, r ); 255 UU = U; 256 DEBOUTLN( cerr, "now trying to distribute the leading coefficients ..." ); 257 TIMING_START(fac_distrib); 258 goodeval = distributeLeadingCoeffs( UU, G, lcG, F, D, delta, omega, A, r ); 259 TIMING_END(fac_distrib); 212 260 #ifdef DEBUGOUTPUT 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 261 if ( goodeval ) { 262 DEBOUTLN( cerr, "the univariate factors after distribution are " << G ); 263 DEBOUTLN( cerr, "the distributed leading coeffs are " << lcG ); 264 DEBOUTLN( cerr, "U may have changed and is now " << UU ); 265 DEBOUTLN( cerr, "which has leading coefficient " << LC( UU, Variable(1) ) ); 266 267 if ( LC( UU, Variable(1) ) != prod( lcG ) || A(UU) != prod( G ) ) { 268 DEBOUTLN( cerr, "!!! distribution was not correct !!!" ); 269 DEBOUTLN( cerr, "product of leading coeffs is " << prod( lcG ) ); 270 DEBOUTLN( cerr, "product of univariate factors is " << prod( G ) ); 271 DEBOUTLN( cerr, "the new U is evaluated as " << A(UU) ); 272 } 273 else 274 DEBOUTLN( cerr, "leading coeffs correct" ); 275 } 276 else { 277 DEBOUTLN( cerr, "we have found a bad evaluation point" ); 278 } 231 279 #endif 232 233 234 235 236 280 if ( goodeval ) { 281 TIMING_START(fac_hensel); 282 goodeval = Hensel( UU, G, lcG, A, b, Variable(1) ); 283 TIMING_END(fac_hensel); 284 } 237 285 } 238 286 for ( i = 1; i <= r; i++ ) { 239 240 287 G[i] /= icontent( G[i] ); 288 G[i] = M(G[i]); 241 289 } 242 290 // negate noch beachten ! 243 291 if ( negate ) 244 292 G[1] = -G[1]; 245 293 DEBDECLEVEL( cerr, "ZFactorMulti" ); 246 294 return G; … … 260 308 v1 = Variable(1); 261 309 if ( issqrfree ) 262 310 F = CFFactor( f, 1 ); 263 311 else 264 312 F = sqrFree( f ); 265 313 266 314 for ( i = F; i.hasItem(); i++ ) { 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 315 if ( i.getItem().factor().inCoeffDomain() ) { 316 if ( ! i.getItem().factor().isOne() ) 317 R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) ); 318 } 319 else { 320 TIMING_START(fac_content); 321 g = compress( i.getItem().factor(), M ); 322 // now after compress g contains Variable(1) 323 vm = g.mvar(); 324 g = swapvar( g, v1, vm ); 325 cont = content( g ); 326 g = swapvar( g / cont, v1, vm ); 327 cont = swapvar( cont, v1, vm ); 328 n = i.getItem().exp(); 329 TIMING_END(fac_content); 330 DEBOUTLN( cerr, "now after content ..." ); 331 if ( g.isUnivariate() ) { 332 G = factorize( g, true ); 333 for ( j = G; j.hasItem(); j++ ) 334 if ( ! j.getItem().factor().isOne() ) 335 R.append( CFFactor( M( j.getItem().factor() ), n ) ); 336 } 337 else { 338 GG = ZFactorizeMulti( g ); 339 m = GG.max(); 340 for ( k = GG.min(); k <= m; k++ ) 341 if ( ! GG[k].isOne() ) 342 R.append( CFFactor( M( GG[k] ), n ) ); 343 } 344 G = factorize( cont, true ); 345 for ( j = G; j.hasItem(); j++ ) 346 if ( ! j.getItem().factor().isOne() ) 347 R.append( CFFactor( M( j.getItem().factor() ), n ) ); 348 } 301 349 } 302 350 return R;
Note: See TracChangeset
for help on using the changeset viewer.
