- Timestamp:
- Jul 30, 2002, 5:23:51 PM (22 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- 412bedd0d8fb0ee909f2782332e9750b3d45b71a
- Parents:
- b2231c92ab6b80cbd9f6b556cd9aa757c5afc3f3
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
factory/cf_factor.cc
rb2231c r7af0e48 1 1 /* emacs edit mode for this file is -*- C++ -*- */ 2 /* $Id: cf_factor.cc,v 1.1 2 2002-03-08 10:31:46Singular Exp $ */2 /* $Id: cf_factor.cc,v 1.13 2002-07-30 15:23:51 Singular Exp $ */ 3 3 4 4 //{{{ docu … … 29 29 30 30 #include "int_int.h" 31 #if 031 #ifdef HAVE_NTL 32 32 #include "NTLconvert.h" 33 33 #endif … … 50 50 int e=f.level(); 51 51 CFIterator i = f; 52 if (i.exp() > exp_f[e]) exp_f[e]=i.exp(); 52 if (e>=0) 53 { 54 if (i.exp() > exp_f[e]) exp_f[e]=i.exp(); 55 } 53 56 for (; i.hasTerms(); i++ ) 54 57 { … … 76 79 } 77 80 81 #if 0 82 void out_cf(char *s1,const CanonicalForm &f,char *s2) 83 { 84 printf("%s",s1); 85 if (f==0) printf("+0"); 86 else if (! f.inCoeffDomain() ) 87 { 88 int l = f.level(); 89 for ( CFIterator i = f; i.hasTerms(); i++ ) 90 { 91 int e=i.exp(); 92 printf("+(");out_cf("+(",i.coeff(),")*v(");printf("%d)^%d",l,e); 93 } 94 } 95 else 96 { 97 if ( f.isImm() ) 98 { 99 printf("+%d(",f.intval()); 100 } 101 else printf("+...("); 102 if (f.inZ()) printf("Z)"); 103 else if (f.inQ()) printf("Q)"); 104 else if (f.inFF()) printf("FF)"); 105 else if (f.inPP()) printf("PP)"); 106 else if (f.inGF()) printf("PP)"); 107 else if (f.inExtension()) printf("E(%d))",f.level()); 108 109 } 110 printf("%s",s2); 111 } 112 void out_cff(CFFList &L) 113 { 114 int n = L.length(); 115 CFFListIterator J=L; 116 int j=0; 117 for ( ; J.hasItem(); J++, j++ ) 118 { 119 printf("F%d",j);out_cf(":",J.getItem().factor()," ^ "); 120 printf("%d\n", J.getItem().exp()); 121 } 122 } 123 void test_cff(CFFList &L,const CanonicalForm & f) 124 { 125 int n = L.length(); 126 CFFListIterator J=L; 127 CanonicalForm t=1; 128 int j=0; 129 if (!(L.getFirst().factor().inCoeffDomain())) 130 printf("first entry is not const\n"); 131 for ( ; J.hasItem(); J++, j++ ) 132 { 133 CanonicalForm tt=J.getItem().factor(); 134 if (tt.inCoeffDomain() && (j!=0)) 135 printf("other entry is const\n"); 136 j=J.getItem().exp(); 137 while(j>0) { t*=tt; j--; } 138 } 139 if ((f-t)!=0) { printf("problem:\n");out_cf("factor:",f," has problems\n");} 140 } 141 #endif 142 143 static bool isPurePoly(const CanonicalForm & f) 144 { 145 if (f.level()<=0) return false; 146 for (CFIterator i=f;i.hasTerms();i++) 147 { 148 if (!(i.coeff().inBaseDomain())) return false; 149 } 150 return true; 151 } 152 78 153 CFFList factorize ( const CanonicalForm & f, bool issqrfree ) 79 154 { 80 155 if ( f.inCoeffDomain() ) 81 156 return CFFList( f ); 82 157 int mv=f.level(); 83 158 if (! f.isUnivariate() ) … … 88 163 swapvar(f,Variable(mv),f.mvar()); 89 164 } 165 if ( getCharacteristic() == 0 ) Off(SW_USE_NTL); 90 166 } 91 167 CFFList F; 92 if ( getCharacteristic() > 0 ) 168 if ( getCharacteristic() > 0 ) 93 169 { 94 170 ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); 95 #if 0 96 if (isOn(SW_USE_NTL) && (getExp()==1)) 97 { 98 printf("start ntl...\n"); 171 #ifdef HAVE_NTL 172 if (isOn(SW_USE_NTL) && (isPurePoly(f))) 173 { 99 174 // USE NTL 100 175 if (getCharacteristic()!=2) 101 176 { 102 // set remainder 177 // set remainder 103 178 ZZ r; 104 r=getCharacteristic(); 179 r=getCharacteristic(); 105 180 ZZ_pContext ccc(r); 106 181 ccc.restore(); 182 ZZ_p::init(r); 107 183 // convert to NTL 108 ZZ_pX f1=convertFacCF2NTLZZpX(f); 184 ZZ_pX f1=convertFacCF2NTLZZpX(f); 109 185 ZZ_p leadcoeff = LeadCoeff(f1); 110 186 //make monic … … 114 190 vec_pair_ZZ_pX_long factors; 115 191 CanZass(factors,f1); 116 192 117 193 // convert back to factory 118 194 F=convertNTLvec_pair_ZZpX_long2FacCFFList(factors,leadcoeff,f.mvar()); 195 //test_cff(F,f); 119 196 } 120 197 else 121 198 { 122 199 // Specialcase characteristic==2 123 200 ZZ r;r=2; 201 ZZ_p::init(r); 202 124 203 // remainder is 2 --> nothing to set 125 204 126 205 // convert to NTL using the faster conversion routine for characteristic 2 127 206 GF2X f1=convertFacCF2NTLGF2X(f); 128 129 207 // no make monic necessary in GF2 130 131 208 //factorize 132 209 vec_pair_GF2X_long factors; 133 210 CanZass(factors,f1); 134 211 135 212 // convert back to factory again using the faster conversion routine for vectors over GF2X 136 F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar()); 137 } 138 printf("... end ntl\n"); 213 F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar()); 214 } 139 215 } 140 216 else … … 143 219 if ( isOn( SW_BERLEKAMP ) ) 144 220 F=FpFactorizeUnivariateB( f, issqrfree ); 145 else 221 else 146 222 F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() ); 147 } 223 } 148 224 } 149 225 else … … 155 231 if ( f.isUnivariate() ) 156 232 { 157 #if 0 158 if (isOn(SW_USE_NTL)) 159 { 160 printf("start ntl...\n"); 233 #ifdef HAVE_NTL 234 if ((isOn(SW_USE_NTL)) && (isPurePoly(f))) 235 { 161 236 //USE NTL 237 CanonicalForm ic=icontent(fz); 238 fz/=ic; 162 239 ZZ c; 163 240 vec_pair_ZZX_long factors; 164 241 //factorize the converted polynomial 165 factor(c,factors,convertFacCF2NTLZZX(fz)); 166 242 factor(c,factors,convertFacCF2NTLZZX(fz)); 243 167 244 //convert the result back to Factory 168 245 F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar()); 169 printf("... end ntl\n"); 246 if ( ! ic.isOne() ) 247 { 248 if ( F.getFirst().factor().inCoeffDomain() ) 249 { 250 CFFactor new_first( F.getFirst().factor() * ic ); 251 F.removeFirst(); 252 F.insert( new_first ); 253 } 254 else 255 F.insert( CFFactor( ic ) ); 256 } 257 if ( F.getFirst().factor().isOne() ) 258 { 259 F.removeFirst(); 260 } 170 261 } 171 262 else 172 263 #endif 173 { 264 { 174 265 //Use Factory without NTL 175 266 F = ZFactorizeUnivariate( fz, issqrfree ); … … 194 285 } 195 286 } 196 } 287 } 197 288 198 289 if ((mv!=f.level()) && (! f.isUnivariate() )) … … 210 301 CFFList factorize ( const CanonicalForm & f, const Variable & alpha ) 211 302 { 303 CFFList F; 212 304 ASSERT( alpha.level() < 0, "not an algebraic extension" ); 213 305 ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); 214 306 ASSERT( getCharacteristic() > 0, "char 0 factorization not implemented" ); 215 #if 0307 #ifdef HAVE_NTL 216 308 if (isOn(SW_USE_NTL)) 217 309 { 218 310 //USE NTL 219 if ( getCharacteristic()!=2)220 { 311 if (1 ) //getCharacteristic()!=2) 312 { 221 313 // First all cases with characteristic !=2 222 // set remainder 314 // set remainder 223 315 ZZ r; 224 r=getCharacteristic(); 316 r=getCharacteristic(); 225 317 ZZ_pContext ccc(r); 226 318 ccc.restore(); 227 319 228 320 // set minimal polynomial in NTL 229 321 ZZ_pX minPo=convertFacCF2NTLZZpX(getMipo(alpha,f.mvar())); … … 232 324 233 325 // convert to NTL 234 ZZ_pEX f1= to_ZZ_pEX(convertFacCF2NTLZZpX(f));235 326 ZZ_pEX f1=convertFacCF2NTLZZ_pEX(f,minPo); 327 236 328 //make monic 237 329 ZZ_pE leadcoeff= LeadCoeff(f1); … … 243 335 244 336 // return converted result 245 returnconvertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);337 F=convertNTLvec_pair_ZZpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha); 246 338 } 247 339 else 248 340 { 249 341 // special case : GF2 250 342 251 343 // remainder is two ==> nothing to do 252 344 … … 255 347 GF2EContext c(minPo); 256 348 c.restore(); 257 349 258 350 // convert to NTL again using the faster conversion routines 259 GF2EX f1=to_GF2EX(convertFacCF2NTLGF2X(f)); 260 351 GF2X f_tmp=convertFacCF2NTLGF2X(f); 352 GF2EX f1=to_GF2EX(f_tmp); 353 261 354 // no make monic necessary in GF2 262 355 263 356 // factorize using NTL 264 357 vec_pair_GF2EX_long factors; … … 266 359 267 360 // return converted result 268 returnconvertNTLvec_pair_GF2EX_long2FacCFFList(factors,LeadCoeff(f1),f.mvar(),alpha);269 } 270 271 } 272 else 361 F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,LeadCoeff(f1),f.mvar(),alpha); 362 } 363 364 } 365 else 273 366 #endif 274 367 { 275 returnFpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() );276 } 277 368 F=FpFactorizeUnivariateCZ( f, false, 1, alpha, Variable() ); 369 } 370 return F; 278 371 } 279 372 … … 284 377 285 378 if ( getCharacteristic() == 0 ) 286 287 else 288 379 result = sqrFreeZ( f ); 380 else 381 result = sqrFreeFp( f ); 289 382 290 383 return ( sort ? sortCFFList( result ) : result ); … … 295 388 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" ); 296 389 if ( getCharacteristic() == 0 ) 297 298 else 299 300 } 301 390 return isSqrFreeZ( f ); 391 else 392 return isSqrFreeFp( f ); 393 } 394
Note: See TracChangeset
for help on using the changeset viewer.