Changeset 14b1e65 in git
- Timestamp:
- Aug 8, 2001, 1:59:13 PM (22 years ago)
- Branches:
- (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
- Children:
- 456842ed1cd4bb0af35f859e0befe623c3991393
- Parents:
- c794a95c85e7ae1437369ab150d85b7c4ff17fd0
- Location:
- libfac/factor
- Files:
-
- 5 edited
-
Factor.cc (modified) (5 diffs)
-
MVMultiHensel.cc (modified) (21 diffs)
-
SqrFree.cc (modified) (16 diffs)
-
Truefactor.cc (modified) (2 diffs)
-
tmpl_inst.cc (modified) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libfac/factor/Factor.cc
rc794a9 r14b1e65 1 1 /* Copyright 1996 Michael Messollen. All rights reserved. */ 2 2 /////////////////////////////////////////////////////////////////////////////// 3 static char * rcsid = "$Id: Factor.cc,v 1. 8 2001-08-06 08:32:54Singular Exp $ ";3 static char * rcsid = "$Id: Factor.cc,v 1.9 2001-08-08 11:59:12 Singular Exp $ "; 4 4 static char * errmsg = "\nYou found a bug!\nPlease inform (Michael Messollen) michael@math.uni-sb.de \nPlease include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you."; 5 5 /////////////////////////////////////////////////////////////////////////////// 6 6 // FACTORY - Includes 7 7 #include <factory.h> 8 #ifndef NOSTREAMIO 9 #include <iostream.h> 10 #endif 8 11 // Factor - Includes 9 12 #include "tmpl_inst.h" … … 324 327 WerrorS("libfac: evaluate: Extension not inFF() or inGF() !"); 325 328 #else 329 #ifndef NOSTREAMIO 326 330 cerr << "libfac: evaluate: " << Extension << " not inFF() or inGF() !" 327 331 << endl; 332 #endif 328 333 #endif 329 334 FFRandom gen; … … 534 539 CFList as(mipo); 535 540 Outputlist = newfactoras( F, as, 1); 536 #endif 541 #endif 537 542 TIMING_END(evaluate_time); 538 543 return Outputlist; … … 644 649 CFList as(mipo); 645 650 UnivariateFactorlist = newfactoras( ffuni, as, 1); 646 #endif 651 #endif 647 652 } 648 653 } … … 823 828 /* 824 829 $Log: not supported by cvs2svn $ 830 Revision 1.8 2001/08/06 08:32:54 Singular 831 * hannes: code cleanup 832 825 833 Revision 1.7 2001/06/21 14:57:05 Singular 826 834 *hannes/GP: Factorize, newfactoras, ... -
libfac/factor/MVMultiHensel.cc
rc794a9 r14b1e65 2 2 /////////////////////////////////////////////////////////////////////////////// 3 3 // emacs edit mode for this file is -*- C++ -*- 4 // static char * rcsid = "$Id: MVMultiHensel.cc,v 1. 4 1997-11-18 16:39:05Singular Exp $";4 // static char * rcsid = "$Id: MVMultiHensel.cc,v 1.5 2001-08-08 11:59:12 Singular Exp $"; 5 5 /////////////////////////////////////////////////////////////////////////////// 6 6 // FACTORY - Includes 7 7 #include <factory.h> 8 #ifndef NOSTREAMIO 9 #include <iostream.h> 10 #endif 8 11 // Factor - Includes 9 12 #include "tmpl_inst.h" … … 48 51 public: 49 52 inline RememberForm operator=( CanonicalForm & value ){ 50 this->calculated = true; 53 this->calculated = true; 51 54 this->poly = value; 52 55 return *this; … … 56 59 }; 57 60 58 // Array to remember already calculated values; used for the diophantine 59 // equation s*f + t*g = x^i 61 // Array to remember already calculated values; used for the diophantine 62 // equation s*f + t*g = x^i 60 63 class RememberArray { 61 64 public: … … 87 90 // Returns s and t. // 88 91 /////////////////////////////////////////////////////////////// 89 static DiophantForm 92 static DiophantForm 90 93 diophant( int levelU , const CanonicalForm & F1 , const CanonicalForm & F2 , int i , RememberArray & A, RememberArray & B ) { 91 94 DiophantForm Retvalue; … … 96 99 DEBOUT(cout, " ", F2); DEBOUTLN(cout, " ", i); 97 100 98 // Did we solve the diophantine equation yet? 101 // Did we solve the diophantine equation yet? 99 102 // If so, return the calculated values 100 103 if ( A[i].calculated && B[i].calculated ){ 101 Retvalue.One=A[i].poly; 104 Retvalue.One=A[i].poly; 102 105 Retvalue.Two=B[i].poly; 103 106 return Retvalue; … … 109 112 WerrorS("libfac: diophant ERROR: degree too large! "); 110 113 #else 111 cerr << "libfac: diophant ERROR: degree too large! " 112 114 cerr << "libfac: diophant ERROR: degree too large! " 115 << (degree(F1,levelU) + degree(F2,levelU) ) <<endl; 113 116 #endif 114 117 Retvalue.One=F1;Retvalue.Two=F2; … … 118 121 if ( i == 0 ) { // call the extended gcd 119 122 r=extgcd(F1,F2,s,t); 120 // check if gcd(F1,F2) <> 1 , i.e. F1 and F2 are not relatively prime 121 if ( ! r.isOne() ){ 123 // check if gcd(F1,F2) <> 1 , i.e. F1 and F2 are not relatively prime 124 if ( ! r.isOne() ){ 122 125 #ifdef HAVE_SINGULAR 123 126 WerrorS("libfac: diophant ERROR: F1 and F2 are not relatively prime! "); 124 127 #else 125 cerr << "libfac: diophant ERROR: " << F1 << " and " << F2 126 << " are not relatively prime!" << endl; 128 #ifndef NOSTREAMIO 129 cerr << "libfac: diophant ERROR: " << F1 << " and " << F2 130 << " are not relatively prime!" << endl; 131 #else 132 cerr << "libfac: diophant ERROR: F1 and F2 are not relatively prime!" 133 << endl; 134 #endif 127 135 #endif 128 136 Retvalue.One=F1;Retvalue.Two=F2; … … 132 140 } 133 141 else { // recursively call diophant 134 Retvalue=diophant(levelU,F1,F2,i-1,A,B); 142 Retvalue=diophant(levelU,F1,F2,i-1,A,B); 135 143 Retvalue.One *= x; // createVar(levelU,1); 136 144 Retvalue.Two *= x; // createVar(levelU,1); … … 144 152 else { 145 153 if ( degree(Retvalue.Two,levelU) >= degree(F1,levelU) ){ 146 147 148 154 // Make degree(Retvalue.Two,mainvar) <= degree(F1,mainvar) 155 divrem(Retvalue.Two,F1,q,r); 156 Retvalue.One += F2*q; Retvalue.Two = r; 149 157 } 150 158 } 151 159 152 160 } 153 A[i].poly = Retvalue.One ; 161 A[i].poly = Retvalue.One ; 154 162 B[i].poly = Retvalue.Two ; 155 163 A[i].calculated = true ; B[i].calculated = true ; … … 165 173 // as in Wang and Rothschild [Wang&Roth75]. // 166 174 /////////////////////////////////////////////////////////////// 167 static CanonicalForm 168 make_delta( int levelU, const CanonicalForm & W, 169 const CanonicalForm & F1, const CanonicalForm & F2, 170 175 static CanonicalForm 176 make_delta( int levelU, const CanonicalForm & W, 177 const CanonicalForm & F1, const CanonicalForm & F2, 178 RememberArray & A, RememberArray & B){ 171 179 CanonicalForm Retvalue; 172 180 DiophantForm intermediate; … … 189 197 } 190 198 191 static CanonicalForm 192 make_square( int levelU, const CanonicalForm & W, 193 const CanonicalForm & F1, const CanonicalForm & F2, 194 199 static CanonicalForm 200 make_square( int levelU, const CanonicalForm & W, 201 const CanonicalForm & F1, const CanonicalForm & F2, 202 RememberArray & A, RememberArray & B){ 195 203 CanonicalForm Retvalue; 196 204 DiophantForm intermediate; … … 222 230 // Return the fully lifted factors. // 223 231 /////////////////////////////////////////////////////////////// 224 static DiophantForm 225 mvhensel( const CanonicalForm & U , const CanonicalForm & F , 226 232 static DiophantForm 233 mvhensel( const CanonicalForm & U , const CanonicalForm & F , 234 const CanonicalForm & G , const SFormList & Substitutionlist){ 227 235 CanonicalForm V,Fk=F,Gk=G,Rk,W,D,S; 228 236 int levelU=level(U), degU=subvardegree(U,levelU); // degree(U,{x_1,..,x_(level(U)-1)}) … … 284 292 // Recursive Version of MultiHensel. // 285 293 /////////////////////////////////////////////////////////////// 286 CFFList 287 multihensel( const CanonicalForm & mF, const CFFList & Factorlist, 288 294 CFFList 295 multihensel( const CanonicalForm & mF, const CFFList & Factorlist, 296 const SFormList & Substitutionlist){ 289 297 CFFList Returnlist,factorlist=Factorlist; 290 298 DiophantForm intermediat; … … 298 306 Returnlist.append(CFFactor(mF,1)); 299 307 } 300 else { 308 else { 301 309 if ( n == 2 ){ 302 intermediat= mvhensel(mF, factorlist.getFirst().factor(), 303 Factorlist.getLast().factor(), 304 310 intermediat= mvhensel(mF, factorlist.getFirst().factor(), 311 Factorlist.getLast().factor(), 312 Substitutionlist); 305 313 Returnlist.append(CFFactor(intermediat.One,1)); 306 314 Returnlist.append(CFFactor(intermediat.Two,1)); … … 313 321 Pr=Pl.genOne(); 314 322 for ( ListIterator<CFFactor> i=factorlist; i.hasItem(); i++ ) 315 Pr *= i.getItem().factor() ; 316 #ifdef HENSELDEBUG2 317 cout << "multihensel: Pl,Pr, factorlist: " << Pl << " " << Pr 318 323 Pr *= i.getItem().factor() ; 324 #ifdef HENSELDEBUG2 325 cout << "multihensel: Pl,Pr, factorlist: " << Pl << " " << Pr 326 << " " << factorlist << endl; 319 327 #endif 320 328 intermediat= mvhensel(mF,Pl,Pr,Substitutionlist); … … 334 342 // Returns the list of fully lifted factors. // 335 343 /////////////////////////////////////////////////////////////// 336 CFFList 337 MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist, 338 344 CFFList 345 MultiHensel( const CanonicalForm & mF, const CFFList & Factorlist, 346 const SFormList & Substitutionlist){ 339 347 CFFList Returnlist,Retlistinter,factorlist=Factorlist,Ll; 340 348 CFFListIterator i; … … 351 359 Returnlist.append(CFFactor(mF,1)); 352 360 } 353 else { 361 else { 354 362 if ( n == 2 ){ 355 intermediat= mvhensel(mF, factorlist.getFirst().factor(), 356 Factorlist.getLast().factor(), 357 363 intermediat= mvhensel(mF, factorlist.getFirst().factor(), 364 Factorlist.getLast().factor(), 365 Substitutionlist); 358 366 Returnlist.append(CFFactor(intermediat.One,1)); 359 367 Returnlist.append(CFFactor(intermediat.Two,1)); … … 361 369 else { // more then two factors 362 370 for ( k=1 ; k<=h; k++){ 363 364 371 Ll.append(factorlist.getFirst()); 372 factorlist.removeFirst(); 365 373 } 366 374 … … 370 378 Pl = 1; Pr = 1; 371 379 for ( i = Ll; i.hasItem(); i++) 372 380 Pl *= i.getItem().factor(); 373 381 DEBOUTLN(cout, "MultiHensel: Pl= ", Pl); 374 382 for ( i = factorlist; i.hasItem(); i++) 375 383 Pr *= i.getItem().factor(); 376 384 DEBOUTLN(cout, "MultiHensel: Pr= ", Pr); 377 385 intermediat = mvhensel(mF,Pl,Pr,Substitutionlist); … … 380 388 // we add a division test now for intermediat.One and intermediat.Two 381 389 if ( mydivremt (mF,intermediat.One,a,b) && b == mF.genZero() ) 382 390 Retlistinter.append(CFFactor(intermediat.One,1) ); 383 391 if ( mydivremt (mF,intermediat.Two,a,b) && b == mF.genZero() ) 384 392 Retlistinter.append(CFFactor(intermediat.Two,1) ); 385 393 386 394 Ll = MultiHensel(intermediat.One, Ll, Substitutionlist); … … 397 405 /* 398 406 $Log: not supported by cvs2svn $ 407 Revision 1.4 1997/11/18 16:39:05 Singular 408 * hannes: moved WerrorS from C++ to C 409 (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc) 410 399 411 Revision 1.3 1997/09/12 07:19:48 Singular 400 412 * hannes/michael: libfac-0.3.0 -
libfac/factor/SqrFree.cc
rc794a9 r14b1e65 2 2 /////////////////////////////////////////////////////////////////////////////// 3 3 // emacs edit mode for this file is -*- C++ -*- 4 static char * rcsid = "$Id: SqrFree.cc,v 1. 4 1997-11-18 16:39:06Singular Exp $";4 static char * rcsid = "$Id: SqrFree.cc,v 1.5 2001-08-08 11:59:13 Singular Exp $"; 5 5 static char * errmsg = "\nYou found a bug!\nPlease inform (Michael Messollen) michael@math.uni-sb.de .\n Please include above information and your input (the ideal/polynomial and characteristic) in your bug-report.\nThank you."; 6 6 /////////////////////////////////////////////////////////////////////////////// 7 7 // FACTORY - Includes 8 8 #include<factory.h> 9 #ifndef NOSTREAMIO 10 #include <iostream.h> 11 #endif 9 12 // Factor - Includes 10 13 #include "tmpl_inst.h" … … 30 33 31 34 32 static inline CFFactor 33 Powerup( const CFFactor & F , int exp=1){ 34 return CFFactor(F.factor(), exp*F.exp()) ; 35 } 36 37 static CFFList 35 static inline CFFactor 36 Powerup( const CFFactor & F , int exp=1){ 37 return CFFactor(F.factor(), exp*F.exp()) ; 38 } 39 40 static CFFList 38 41 Powerup( const CFFList & Inputlist , int exp=1 ){ 39 42 CFFList Outputlist; … … 49 52 // Domain is q=p^m , f a uni/multivariate polynomial // 50 53 /////////////////////////////////////////////////////////////// 51 static CanonicalForm 54 static CanonicalForm 52 55 PthRoot( const CanonicalForm & f ){ 53 56 CanonicalForm RES, R = f; 54 57 int n= max(level(R),getNumVars(R)), p= getCharacteristic(); 55 58 56 59 if (n==0){ // constant 57 60 if (R.inExtension()) // not in prime field; f over |F(q=p^k) … … 90 93 g = mygcd(f,g); 91 94 if ( g.isOne() || (-g).isOne() ) return 1; 92 else 95 else 93 96 if ( getNumVars(g) == 0 ) return 1;// <- totaldegree!!! 94 97 else return 0 ; … … 99 102 // g = 1 || -1 : sqr-free, g poly : not sqr-free, g number : opt helps 100 103 if ( ! (g.isOne() || (-g).isOne() || getNumVars(g)==0 ) ) { 101 102 103 104 105 106 104 if ( opt==0 ) return 0; 105 else { 106 if ( SqrFreeTest(g,1) == 0 ) return 0; 107 g = swapvar(g,k,n); 108 f /=g ; 109 } 107 110 } 108 111 } … … 110 113 n = level(f); // maybe less indeterminants 111 114 // if ( totaldegree(f) <= 1 ) return 1; 112 115 113 116 // Let`s look if it is a Pth root 114 117 if ( getCharacteristic() > 0 ) 115 118 for (int k=1; k<=n; k++ ) { 116 117 118 119 g=swapvar(f,k,n); g=g.deriv(); 120 if ( ! g.isZero() ) break ; 121 else if ( k==n) return 0 ; // really is Pth root 119 122 } 120 123 g = f.deriv() ; … … 128 131 WerrorS("libfac: ERROR: SqrFreeTest: we should never fall trough here!"); 129 132 #else 130 cerr << "\nlibfac: ERROR: SqrFreeTest: we should never fall trough here!\n" 133 cerr << "\nlibfac: ERROR: SqrFreeTest: we should never fall trough here!\n" 131 134 << rcsid << errmsg << endl; 132 135 #endif … … 141 144 // needs not to be 1 !!!!! // 142 145 /////////////////////////////////////////////////////////////// 143 static CFFList 146 static CFFList 144 147 SqrFreed( const CanonicalForm & r ){ 145 148 CanonicalForm h, g, f = r; … … 154 157 } 155 158 156 // We look if we do have a content; if so, SqrFreed the content 159 // We look if we do have a content; if so, SqrFreed the content 157 160 // and continue computations with pp(f) 158 161 for (int k=1; k<=n; k++) { … … 161 164 g = swapvar(g,k,n); 162 165 DEBOUTLN(cout, "We have a content: ", g); 163 Outputlist = myUnion(InternalSqrFree(g),Outputlist); // should we add a 166 Outputlist = myUnion(InternalSqrFree(g),Outputlist); // should we add a 164 167 // SqrFreeTest(g) first ? 165 168 DEBOUTLN(cout, "Outputlist is now: ", Outputlist); … … 177 180 f /= g; 178 181 } 179 Outputlist = Union(sqrFree(f),Outputlist) ; 182 Outputlist = Union(sqrFree(f),Outputlist) ; 180 183 DEBOUTLN(cout, "Outputlist after univ. sqrFree(f) = ", Outputlist); 181 184 DEBDECLEVEL(cout, "SqrFreed"); … … 197 200 g=swapvar(f,k,n) ; g = g.deriv(); 198 201 if ( ! g.isZero() ){ // can`t be Pth root 199 CFFList Outputlist2= SqrFreed(swapvar(f,k,n)); 200 201 202 203 202 CFFList Outputlist2= SqrFreed(swapvar(f,k,n)); 203 for (CFFListIterator inter=Outputlist2; inter.hasItem(); inter++){ 204 Outputlist= myappend(Outputlist, CFFactor(swapvar(inter.getItem().factor(),k,n), inter.getItem().exp())); 205 } 206 return Outputlist; 204 207 } 205 else 206 208 else 209 if ( k==n ) { // really is Pth power 207 210 DEBOUTLN(cout, "f is a p'th root: ", f); 208 211 CFMap m; 209 212 g = compress(f,m); 210 213 f = m(PthRoot(g)); 211 214 DEBOUTLN(cout, " that is : ", f); 212 213 214 215 216 215 // now : Outputlist union ( SqrFreed(f) )^getCharacteristic() 216 Outputlist=myUnion(Powerup(InternalSqrFree(f),getCharacteristic()),Outputlist); 217 DEBDECLEVEL(cout, "SqrFreed"); 218 return Outputlist ; 219 } 217 220 } 218 221 } … … 254 257 WerrorS("libfac: ERROR: SqrFreed: we should never fall trough here!"); 255 258 #else 256 cerr << "\nlibfac: ERROR: SqrFreed: we should never fall trough here!\n" 259 cerr << "\nlibfac: ERROR: SqrFreed: we should never fall trough here!\n" 257 260 << rcsid << errmsg << endl; 258 261 #endif … … 265 268 // Input can have a constant as content // 266 269 /////////////////////////////////////////////////////////////// 267 CFFList 270 CFFList 268 271 InternalSqrFree( const CanonicalForm & r ){ 269 272 CanonicalForm g=icontent(r), f = r; … … 285 288 f /= g; 286 289 if ( getNumVars(f) != 0 ) // a real polynomial 287 290 Outputlist=myUnion(SqrFreed(f),Outputlist) ; 288 291 } 289 292 DEBOUTLN(cout,"Outputlist = ", Outputlist); … … 331 334 /* 332 335 $Log: not supported by cvs2svn $ 336 Revision 1.4 1997/11/18 16:39:06 Singular 337 * hannes: moved WerrorS from C++ to C 338 (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc) 339 333 340 Revision 1.3 1997/09/12 07:19:50 Singular 334 341 * hannes/michael: libfac-0.3.0 -
libfac/factor/Truefactor.cc
rc794a9 r14b1e65 2 2 /////////////////////////////////////////////////////////////////////////////// 3 3 // emacs edit mode for this file is -*- C++ -*- 4 //static char * rcsid = "@(#) $Id: Truefactor.cc,v 1. 7 2001-08-06 08:32:54Singular Exp $";4 //static char * rcsid = "@(#) $Id: Truefactor.cc,v 1.8 2001-08-08 11:59:13 Singular Exp $"; 5 5 /////////////////////////////////////////////////////////////////////////////// 6 6 // Factory - Includes 7 7 #include <factory.h> 8 #ifndef NOSTREAMIO 9 #include <iostream.h> 10 #endif 8 11 // Factor - Includes 9 12 #include "tmpl_inst.h" … … 410 413 /* 411 414 $Log: not supported by cvs2svn $ 415 Revision 1.7 2001/08/06 08:32:54 Singular 416 * hannes: code cleanup 417 412 418 Revision 1.6 2001/06/27 13:58:06 Singular 413 419 *hannes/GP: debug newfactoras, char_series, ... -
libfac/factor/tmpl_inst.cc
rc794a9 r14b1e65 2 2 //////////////////////////////////////////////////////////// 3 3 // emacs edit mode for this file is -*- C++ -*- 4 // $Id: tmpl_inst.cc,v 1. 4 1998-02-27 10:34:02 schmidtExp $4 // $Id: tmpl_inst.cc,v 1.5 2001-08-08 11:59:13 Singular Exp $ 5 5 //////////////////////////////////////////////////////////// 6 6 … … 25 25 template class SubMatrix<CanonicalForm>; 26 26 27 #ifndef NOSTREAMIO 27 28 template ostream & operator << ( ostream &, const List<CanonicalForm> & ); 28 29 template ostream & operator << ( ostream &, const List<CFFactor> & ); … … 31 32 template ostream & operator << ( ostream &, const Factor<CanonicalForm> & ); 32 33 //template ostream & operator << ( ostream &, const Matrix<CanonicalForm> & ); 34 #endif 33 35 34 36 template List<CFFactor> Union ( const List<CFFactor>&, const List<CFFactor>& ); … … 62 64 template List<CanonicalForm> Difference ( const List<CanonicalForm>&, const List<CanonicalForm>& ); 63 65 66 #ifndef NOSTREAMIO 64 67 template ostream & operator << ( ostream &, const List<int> & ); 65 68 template ostream & operator << ( ostream &, const List<IntList> & ); 69 #endif 66 70 67 71 // for charsets: … … 74 78 template List<Variable> Difference ( const List<Variable>&, const List<Variable>& ); 75 79 80 #ifndef NOSTREAMIO 76 81 template ostream & operator << ( ostream &, const List<CFList> & ); 77 82 template ostream & operator << ( ostream &, const List<Variable> & ); 78 83 template ostream & operator << ( ostream &, const List<int> & ); 79 84 template ostream & operator << ( ostream &, const Array<int> & ); 85 #endif 80 86 81 87 template class Array<int>; … … 90 96 /* 91 97 $Log: not supported by cvs2svn $ 98 Revision 1.4 1998/02/27 10:34:02 schmidt 99 * factor/tmpl_inst.cc: template names adapted (`*.cc' -> 100 `ftmpl_*.cc') 101 92 102 Revision 1.3 1997/09/12 07:20:00 Singular 93 103 * hannes/michael: libfac-0.3.0
Note: See TracChangeset
for help on using the changeset viewer.
