1 | /* Copyright 1996 Michael Messollen. All rights reserved. */ |
---|
2 | //////////////////////////////////////////////////////////// |
---|
3 | // emacs edit mode for this file is -*- C++ -*- |
---|
4 | static char * rcsid = "$Id: csutil.cc,v 1.14 2007-05-15 14:46:48 Singular Exp $"; |
---|
5 | ///////////////////////////////////////////////////////////// |
---|
6 | // FACTORY - Includes |
---|
7 | #include <factory.h> |
---|
8 | // Factor - Includes |
---|
9 | #include <tmpl_inst.h> |
---|
10 | #include <Factor.h> |
---|
11 | #include <SqrFree.h> |
---|
12 | #include <helpstuff.h> |
---|
13 | #include <homogfactor.h> |
---|
14 | // Charset - Includes |
---|
15 | #include "csutil.h" |
---|
16 | extern void out_cf(char *s1,const CanonicalForm &f,char *s2); |
---|
17 | extern CanonicalForm alg_lc(const CanonicalForm &f); |
---|
18 | extern int hasAlgVar(const CanonicalForm &f); |
---|
19 | |
---|
20 | static bool |
---|
21 | lowerRank ( const CanonicalForm & f, const CanonicalForm & g, int & ind ) |
---|
22 | { |
---|
23 | int df, dg; |
---|
24 | Variable vf = f.mvar(), vg = g.mvar(); |
---|
25 | |
---|
26 | if ( f.inCoeffDomain() ) { |
---|
27 | if ( g.inCoeffDomain() ) ind= 1; |
---|
28 | return true;//( vg > vf ); |
---|
29 | } |
---|
30 | else if ( g.inCoeffDomain() ) return false; |
---|
31 | else if ( vf < vg ) return true; |
---|
32 | else if ( vf == vg ) { |
---|
33 | df = degree( f ); dg = degree( g ); |
---|
34 | if ( df < dg ) return true; |
---|
35 | else if ( df == dg ) return lowerRank( LC( f ), LC( g ) , ind); |
---|
36 | else return false; |
---|
37 | } |
---|
38 | return false; |
---|
39 | } |
---|
40 | |
---|
41 | CanonicalForm |
---|
42 | lowestRank( const CFList & F ) |
---|
43 | { |
---|
44 | CFListIterator i = F; |
---|
45 | CanonicalForm f; |
---|
46 | int ind=0; |
---|
47 | if ( ! i.hasItem() ) return f; |
---|
48 | f = i.getItem(); ++i; |
---|
49 | while ( i.hasItem() ) { |
---|
50 | //CERR << "comparing " << f << " and " << i.getItem() |
---|
51 | // << " == " << lowerRank( i.getItem(), f, ind ) << "\n"; |
---|
52 | if ( lowerRank( i.getItem(), f, ind ) ) { |
---|
53 | if ( ind ){ |
---|
54 | CFList Itemlist= get_Terms(i.getItem()); |
---|
55 | CFList Flist= get_Terms(f); |
---|
56 | |
---|
57 | // Have to further compare number of terms! |
---|
58 | //CERR << "compare terms! f= " << Flist.length() << " item= " |
---|
59 | // << Itemlist.length() <<"\n"; |
---|
60 | if ( Itemlist.length() < Flist.length()) f = i.getItem(); |
---|
61 | ind=0; |
---|
62 | } |
---|
63 | else{ |
---|
64 | f = i.getItem(); |
---|
65 | } |
---|
66 | } |
---|
67 | ++i; |
---|
68 | } |
---|
69 | return f; |
---|
70 | } |
---|
71 | |
---|
72 | // old version |
---|
73 | // CanonicalForm |
---|
74 | // prem ( const CanonicalForm &f, const CanonicalForm &g ) |
---|
75 | // { |
---|
76 | // CanonicalForm ff, gg, cg; |
---|
77 | // int df, dg; |
---|
78 | // bool reord; |
---|
79 | // Variable vf, vg, v; |
---|
80 | // |
---|
81 | // if ( (vf = f.mvar()) < (vg = g.mvar()) ) return f; |
---|
82 | // else { |
---|
83 | // if ( vf == vg ) { |
---|
84 | // ff = f; gg = g; |
---|
85 | // reord = false; |
---|
86 | // v = vg; |
---|
87 | // } |
---|
88 | // else { |
---|
89 | // v = Variable(level(f.mvar()) + 1); |
---|
90 | // ff = swapvar(f,vg,v); |
---|
91 | // gg = swapvar(g,vg,v); |
---|
92 | // reord=true; |
---|
93 | // } |
---|
94 | // cg = ini( gg, v ); |
---|
95 | // dg = degree( gg, v ); |
---|
96 | // while ( ( df = degree( ff, v ) ) >= dg ) |
---|
97 | // ff = cg * ff - power( v, df-dg ) * gg * LC( ff, v ); |
---|
98 | // if ( reord ) { |
---|
99 | // return swapvar( ff, vg, v ); |
---|
100 | // } |
---|
101 | // else |
---|
102 | // return ff; |
---|
103 | // } |
---|
104 | // } |
---|
105 | |
---|
106 | CanonicalForm |
---|
107 | Prem ( const CanonicalForm &f, const CanonicalForm &g ){ |
---|
108 | CanonicalForm ff, gg, l, test, lu, lv, t, retvalue; |
---|
109 | int df, dg; |
---|
110 | bool reord; |
---|
111 | Variable vf, vg, v; |
---|
112 | |
---|
113 | if ( (vf = f.mvar()) < (vg = g.mvar()) ) return f; |
---|
114 | else { |
---|
115 | if ( vf == vg ) { |
---|
116 | ff = f; gg = g; |
---|
117 | reord = false; |
---|
118 | v = vg; |
---|
119 | } |
---|
120 | else { |
---|
121 | v = Variable(level(f.mvar()) + 1); |
---|
122 | ff = swapvar(f,vg,v); |
---|
123 | gg = swapvar(g,vg,v); |
---|
124 | reord=true; |
---|
125 | } |
---|
126 | dg = degree( gg, v ); |
---|
127 | df = degree( ff, v ); |
---|
128 | if (dg <= df) {l=LC(gg); gg = gg -LC(gg)*power(v,dg);} |
---|
129 | else { l = 1; } |
---|
130 | while ( ( dg <= df ) && ( ff != ff.genZero()) ){ |
---|
131 | // CERR << "Start gcd..." << "\n"; |
---|
132 | test = gcd(l,LC(ff)); |
---|
133 | //CERR << "gcd(" << l << "," << LC(ff) << ")= " << test << "\n"; |
---|
134 | lu = l/test; lv = LC(ff)/test; |
---|
135 | t = power(v,df-dg) * gg * lv; |
---|
136 | if ( df == 0 ){ ff = ff.genZero(); } |
---|
137 | else { ff = ff - LC(ff)*power(v,df); } |
---|
138 | ff = lu*ff - t; |
---|
139 | df = degree( ff, v ); |
---|
140 | } |
---|
141 | if ( reord ) { |
---|
142 | retvalue= swapvar( ff, vg, v ); |
---|
143 | } |
---|
144 | else { |
---|
145 | retvalue= ff; |
---|
146 | } |
---|
147 | return retvalue; |
---|
148 | } |
---|
149 | } |
---|
150 | |
---|
151 | static CanonicalForm |
---|
152 | Sprem ( const CanonicalForm &f, const CanonicalForm &g, CanonicalForm & m, CanonicalForm & q ){ |
---|
153 | CanonicalForm ff, gg, l, test, retvalue; |
---|
154 | int df, dg,n; |
---|
155 | bool reord; |
---|
156 | Variable vf, vg, v; |
---|
157 | |
---|
158 | if ( (vf = f.mvar()) < (vg = g.mvar()) ) { |
---|
159 | m=CanonicalForm(0); q=CanonicalForm(0); |
---|
160 | return f; |
---|
161 | } |
---|
162 | else { |
---|
163 | if ( vf == vg ) { |
---|
164 | ff = f; gg = g; |
---|
165 | reord = false; |
---|
166 | v = vg; // == x |
---|
167 | } |
---|
168 | else { |
---|
169 | v = Variable(level(f.mvar()) + 1); |
---|
170 | ff = swapvar(f,vg,v); // == r |
---|
171 | gg = swapvar(g,vg,v); // == v |
---|
172 | reord=true; |
---|
173 | } |
---|
174 | dg = degree( gg, v ); // == dv |
---|
175 | df = degree( ff, v ); // == dr |
---|
176 | if (dg <= df) {l=LC(gg); gg = gg -LC(gg)*power(v,dg);} |
---|
177 | else { l = 1; } |
---|
178 | n= 0; |
---|
179 | while ( ( dg <= df ) && ( ff != ff.genZero()) ){ |
---|
180 | test= power(v,df-dg) * gg * LC(ff); |
---|
181 | if ( df == 0 ){ff= ff.genZero();} |
---|
182 | else {ff= ff - LC(ff)*power(v,df);} |
---|
183 | ff = l*ff-test; |
---|
184 | df= degree(ff,v); |
---|
185 | n++; |
---|
186 | } |
---|
187 | if ( reord ) { |
---|
188 | retvalue= swapvar( ff, vg, v ); |
---|
189 | } |
---|
190 | else { |
---|
191 | retvalue= ff; |
---|
192 | } |
---|
193 | m= power(l,n); |
---|
194 | if ( fdivides(g,m*f-retvalue) ) |
---|
195 | q= (m*f-retvalue)/g; |
---|
196 | else { |
---|
197 | q= CanonicalForm(0); |
---|
198 | } |
---|
199 | return retvalue; |
---|
200 | } |
---|
201 | } |
---|
202 | |
---|
203 | CanonicalForm |
---|
204 | divide( const CanonicalForm & ff, const CanonicalForm & f, const CFList & as) |
---|
205 | { |
---|
206 | CanonicalForm r,m,q; |
---|
207 | |
---|
208 | //out_cf("divide f=",ff,"\n"); |
---|
209 | //out_cf("divide g=",f,"\n"); |
---|
210 | if (f.inCoeffDomain()) |
---|
211 | { |
---|
212 | bool b=false; |
---|
213 | if (!isOn(SW_RATIONAL)) { b=true;On(SW_RATIONAL); } |
---|
214 | q=ff/f; |
---|
215 | if (b) Off(SW_RATIONAL); |
---|
216 | } |
---|
217 | else |
---|
218 | r= Sprem(ff,f,m,q); //result in q, ignore r,m |
---|
219 | //CERR << "r= " << r << " , m= " << m << " , q= " << q << "\n"; |
---|
220 | r= Prem(q,as); |
---|
221 | //CERR << "r= " << r << "\n"; |
---|
222 | //out_cf(" ->",r,"\n"); |
---|
223 | return r; |
---|
224 | } |
---|
225 | |
---|
226 | static CanonicalForm |
---|
227 | myfitting( const CanonicalForm &f ) |
---|
228 | { |
---|
229 | CanonicalForm rem=f; |
---|
230 | |
---|
231 | if ( !(rem.isZero()) ) |
---|
232 | { |
---|
233 | if ( getCharacteristic() > 0 ) |
---|
234 | return num((rem/lc(rem))); |
---|
235 | else |
---|
236 | { |
---|
237 | On(SW_RATIONAL); |
---|
238 | CanonicalForm temp= mapinto(rem); |
---|
239 | // CERR << "temp= " << temp << "\n"; |
---|
240 | // CERR << "lc(temp)= " << lc(temp) << "\n"; |
---|
241 | // CERR << "temp/lc(temp)= " << temp/lc(temp) << "\n"; |
---|
242 | // CERR << "num(rem/lc(rem))= " << num(rem/lc(rem)) << "\n"; |
---|
243 | temp= bCommonDen(temp/lc(temp))*(temp/lc(temp)); |
---|
244 | Off(SW_RATIONAL); |
---|
245 | rem= mapinto(temp); |
---|
246 | return rem; |
---|
247 | } |
---|
248 | } |
---|
249 | else |
---|
250 | return rem; |
---|
251 | } |
---|
252 | |
---|
253 | CanonicalForm |
---|
254 | Prem( const CanonicalForm &f, const CFList &L ){ |
---|
255 | CanonicalForm rem = f; |
---|
256 | CFListIterator i = L; |
---|
257 | for ( i.lastItem(); i.hasItem(); i-- ){ |
---|
258 | //CERR << " PREM: Prem(" << rem << "," ; |
---|
259 | rem = Prem( rem, i.getItem() ); |
---|
260 | //CERR << " PREM: Prem(" << rem << "," << i.getItem() << ") = " << rem << "\n"; |
---|
261 | } |
---|
262 | return myfitting(rem); |
---|
263 | } |
---|
264 | |
---|
265 | CFList |
---|
266 | Prem( const CFList &AS, const CFList &L ){ |
---|
267 | CFList Output; |
---|
268 | |
---|
269 | for ( CFListIterator i=AS; i.hasItem(); i++ ) |
---|
270 | Output = Union(CFList(Prem(i.getItem(),L)), Output); |
---|
271 | |
---|
272 | return Output; |
---|
273 | } |
---|
274 | |
---|
275 | static CanonicalForm |
---|
276 | premasb( const CanonicalForm & f, const CFList & as) |
---|
277 | { |
---|
278 | CanonicalForm remd=f; |
---|
279 | CFList AS=as; |
---|
280 | |
---|
281 | if ( as.length() > 1 ) |
---|
282 | { |
---|
283 | AS.removeFirst(); // get rid of first elem |
---|
284 | CanonicalForm elem; |
---|
285 | while ( ! AS.isEmpty() ) |
---|
286 | { // thats true for at least the first iteration |
---|
287 | elem= AS.getLast(); |
---|
288 | remd= Prem(remd,elem); |
---|
289 | AS.removeLast(); |
---|
290 | } |
---|
291 | } |
---|
292 | CanonicalForm a,b; |
---|
293 | if ( mydivremt(remd, as.getFirst(), a,b )){ remd= remd.genZero();} |
---|
294 | else { remd= Prem(remd, as.getFirst()); } |
---|
295 | |
---|
296 | return remd; |
---|
297 | } |
---|
298 | |
---|
299 | CFList |
---|
300 | remsetb( const CFList & ps, const CFList & as) |
---|
301 | { |
---|
302 | CFList output; |
---|
303 | CanonicalForm elem; |
---|
304 | for (CFListIterator i=ps; i.hasItem(); i++) |
---|
305 | { |
---|
306 | elem= premasb(i.getItem(),as); |
---|
307 | if ( elem != elem.genZero() ) output.append(elem); |
---|
308 | } |
---|
309 | return output; |
---|
310 | } |
---|
311 | |
---|
312 | // for characteristic sets |
---|
313 | ////////////////////////////////// |
---|
314 | // replace the power of factors of polys in as by 1 if any |
---|
315 | static CFList |
---|
316 | nopower( const CanonicalForm & init ) |
---|
317 | { |
---|
318 | CFFList sqrfreelist;// = Factorize(init);//SqrFree(init); |
---|
319 | CFList output; |
---|
320 | CanonicalForm elem; |
---|
321 | int count=0; |
---|
322 | |
---|
323 | for ( CFIterator j=init; j.hasTerms(); j++ ) |
---|
324 | if (!(j.coeff().isOne()) ) count += 1; |
---|
325 | // if ( init != 1 ){ |
---|
326 | // CERR << "nopower: f is " << init << "\n"; |
---|
327 | // CERR << "nopower: count is " << count << "\n";} |
---|
328 | if ( count > 1 ) sqrfreelist = CFFList( CFFactor(init,1)); |
---|
329 | else |
---|
330 | { |
---|
331 | sqrfreelist = Factorize(init); |
---|
332 | //sqrfreelist.removeFirst(); |
---|
333 | } |
---|
334 | for ( CFFListIterator i=sqrfreelist; i.hasItem(); i++ ) |
---|
335 | { |
---|
336 | elem=i.getItem().factor(); |
---|
337 | if ( cls(elem) > 0 ) output.append(elem); |
---|
338 | } |
---|
339 | return output; |
---|
340 | } |
---|
341 | |
---|
342 | // remove the content of polys in PS; add the removed content to |
---|
343 | // Remembern.FS2 ( the set of removed factors ) |
---|
344 | CFList |
---|
345 | removecontent ( const CFList & PS, PremForm & Remembern ) |
---|
346 | { |
---|
347 | CFListIterator i=PS; |
---|
348 | if ((!i.hasItem()) || ( cls(PS.getFirst()) == 0 )) return PS; |
---|
349 | |
---|
350 | CFList output; |
---|
351 | CanonicalForm cc,elem; |
---|
352 | |
---|
353 | for (; i.hasItem(); i++) |
---|
354 | { |
---|
355 | elem = i.getItem(); |
---|
356 | cc = content(elem, elem.mvar()); |
---|
357 | if ( cls(cc) > 0 ) |
---|
358 | { |
---|
359 | output.append(elem/cc); |
---|
360 | Remembern.FS2 = Union(CFList(cc), Remembern.FS2); |
---|
361 | } |
---|
362 | else{ output.append(elem); } |
---|
363 | } |
---|
364 | return output; |
---|
365 | } |
---|
366 | |
---|
367 | // remove possible factors in Remember.FS1 from poly r |
---|
368 | // Remember.FS2 contains all factors removed before |
---|
369 | void |
---|
370 | removefactor( CanonicalForm & r , PremForm & Remembern){ |
---|
371 | int test; |
---|
372 | CanonicalForm a,b,testelem; |
---|
373 | CFList testlist; |
---|
374 | int n=level(r); |
---|
375 | CFListIterator j ; |
---|
376 | |
---|
377 | for ( int J=1; J<= n ; J++ ) |
---|
378 | { |
---|
379 | testlist.append(CanonicalForm(Variable(J))); |
---|
380 | } |
---|
381 | |
---|
382 | // testlist = Union(Remembern.FS1, testlist); // add candidates |
---|
383 | |
---|
384 | // remove already removed factors |
---|
385 | for ( j = Remembern.FS2 ; j.hasItem(); j++ ) |
---|
386 | { |
---|
387 | testelem = j.getItem(); |
---|
388 | while ( 1 ) |
---|
389 | { |
---|
390 | test = mydivremt(r,testelem,a,b); |
---|
391 | if ( test && b == r.genZero() ) r = a; |
---|
392 | else break; |
---|
393 | } |
---|
394 | } |
---|
395 | |
---|
396 | // Let's look if we have other canditates to remove |
---|
397 | for ( j = testlist ; j.hasItem(); j++ ) |
---|
398 | { |
---|
399 | testelem = j.getItem(); |
---|
400 | // if ( testelem != r && testelem != r.mvar() ){ |
---|
401 | if ( testelem != r ) |
---|
402 | { |
---|
403 | while ( 1 ) |
---|
404 | { |
---|
405 | test = divremt(r,testelem,a,b); |
---|
406 | if ( test && b == r.genZero() ) |
---|
407 | { |
---|
408 | Remembern.FS2= Union(Remembern.FS2, CFList(testelem)); |
---|
409 | r = a; |
---|
410 | if ( r == 1 ) break; |
---|
411 | } |
---|
412 | else break; |
---|
413 | } |
---|
414 | } |
---|
415 | } |
---|
416 | // CERR << "Remembern.FS1 = " << Remembern.FS1 << "\n"; |
---|
417 | // CERR << "Remembern.FS2 = " << Remembern.FS2 << "\n"; |
---|
418 | // Remembern.FS1 = Difference(Remembern.FS1, Remembern.FS2); |
---|
419 | // CERR << " New Remembern.FS1 = " << Remembern.FS1 << "\n"; |
---|
420 | } |
---|
421 | |
---|
422 | |
---|
423 | // all irreducible nonconstant factors of a set of polynomials |
---|
424 | CFList |
---|
425 | factorps( const CFList &ps ) |
---|
426 | { |
---|
427 | CFList qs; |
---|
428 | CFFList q; |
---|
429 | CanonicalForm elem; |
---|
430 | |
---|
431 | for ( CFListIterator i=ps; i. hasItem(); i++ ) |
---|
432 | { |
---|
433 | q=Factorize(i.getItem()); |
---|
434 | q.removeFirst(); |
---|
435 | // Next can be simplified ( first (already removed) elem in q is the only constant |
---|
436 | for ( CFFListIterator j=q; j.hasItem(); j++ ) |
---|
437 | { |
---|
438 | elem = j.getItem().factor(); |
---|
439 | if ( getNumVars(elem) > 0 ) |
---|
440 | qs= Union(qs, CFList(myfitting(elem))); |
---|
441 | } |
---|
442 | } |
---|
443 | return qs; |
---|
444 | } |
---|
445 | |
---|
446 | // the initial of poly f wrt to the order of the variables |
---|
447 | static CanonicalForm |
---|
448 | inital( const CanonicalForm &f ) |
---|
449 | { |
---|
450 | CanonicalForm leadcoeff; |
---|
451 | |
---|
452 | if ( cls(f) == 0 ) {return f.genOne(); } |
---|
453 | else |
---|
454 | { |
---|
455 | leadcoeff = LC(f,lvar(f)); |
---|
456 | // if ( leadcoeff != 0 ) |
---|
457 | return myfitting(leadcoeff); //num(leadcoeff/lc(leadcoeff)); |
---|
458 | // else return leadcoeff; |
---|
459 | } |
---|
460 | } |
---|
461 | |
---|
462 | // the set of all nonconstant factors of initals of polys in as |
---|
463 | // CFList |
---|
464 | // initalset(const CFList &as){ |
---|
465 | // CanonicalForm elem; |
---|
466 | // CFList is, iss,iniset; |
---|
467 | |
---|
468 | // for ( CFListIterator i=as ; i.hasItem(); i++ ){ |
---|
469 | // elem = inital(i.getItem()); |
---|
470 | // if ( cls(elem) > 0 ) is.append(elem); |
---|
471 | // } |
---|
472 | // iss = factorps(is); |
---|
473 | // for ( CFListIterator j=iss; j.hasItem();j++ ){ |
---|
474 | // elem = j.getItem(); |
---|
475 | // if ( cls(elem) > 0 ) iniset.append(num(elem/lc(elem))); |
---|
476 | // } |
---|
477 | // return iniset; |
---|
478 | // } |
---|
479 | |
---|
480 | // the set of nonconstant initials of Cset |
---|
481 | // with certain repeated factors cancelled |
---|
482 | CFList |
---|
483 | initalset1(const CFList & Cset){ |
---|
484 | CFList temp; |
---|
485 | CFList initals; |
---|
486 | CanonicalForm init; |
---|
487 | |
---|
488 | for ( CFListIterator i = Cset ; i.hasItem(); i++ ){ |
---|
489 | initals= nopower( inital(i.getItem()) ); |
---|
490 | // init= inital(i.getItem()); |
---|
491 | for ( CFListIterator j = initals; j.hasItem(); j++){ |
---|
492 | init = j.getItem(); |
---|
493 | if ( cls(init) > 0 ) |
---|
494 | temp= Union(temp, CFList(init)); |
---|
495 | } |
---|
496 | } |
---|
497 | return temp; |
---|
498 | } |
---|
499 | |
---|
500 | // the set of nonconstant initials of Cset of those polys |
---|
501 | // not having their cls higher than reducible |
---|
502 | // with certain repeated factors cancelled |
---|
503 | CFList |
---|
504 | initalset2(const CFList & Cset, const CanonicalForm & reducible){ |
---|
505 | CFList temp; |
---|
506 | CFList initals; |
---|
507 | CanonicalForm init; |
---|
508 | int clsred = cls(reducible); |
---|
509 | |
---|
510 | for ( CFListIterator i = Cset ; i.hasItem(); i++ ){ |
---|
511 | init = i.getItem(); |
---|
512 | if ( cls(init) < clsred ){ |
---|
513 | initals= nopower( inital(init) ); |
---|
514 | // init= inital(i.getItem()); |
---|
515 | for ( CFListIterator j = initals; j.hasItem(); j++){ |
---|
516 | init = j.getItem(); |
---|
517 | if ( cls(init) > 0 ) |
---|
518 | temp= Union(temp, CFList(init)); |
---|
519 | } |
---|
520 | } |
---|
521 | } |
---|
522 | return temp; |
---|
523 | } |
---|
524 | |
---|
525 | //replace the power of factors of poly in CF init by 1 if any |
---|
526 | // and return the sqrfree poly |
---|
527 | // static CanonicalForm |
---|
528 | // nopower1( const CanonicalForm & init ){ |
---|
529 | // CFFList returnlist=Factorize(init); |
---|
530 | // CanonicalForm elem, test=init.genOne(); |
---|
531 | // for ( CFFListIterator i= returnlist; i.hasItem(); i++){ |
---|
532 | // elem = i.getItem().factor(); |
---|
533 | // if ( cls(elem)>0 ) test *= elem; |
---|
534 | // } |
---|
535 | // return test; |
---|
536 | // } |
---|
537 | |
---|
538 | // the sequence of distinct factors of f |
---|
539 | //CF pfactor( ..... ) |
---|
540 | |
---|
541 | // ////////////////////////////////////////// |
---|
542 | // // for IrrCharSeries |
---|
543 | |
---|
544 | #ifdef IRRCHARSERIESDEBUG |
---|
545 | # define DEBUGOUTPUT |
---|
546 | #else |
---|
547 | # undef DEBUGOUTPUT |
---|
548 | #endif |
---|
549 | #include "debug.h" |
---|
550 | // examine the irreducibility of as for IrrCharSeries |
---|
551 | int |
---|
552 | irreducible( const CFList & AS){ |
---|
553 | // AS is given by AS = { A1, A2, .. Ar }, d_i = degree(Ai) |
---|
554 | |
---|
555 | DEBOUTMSG(CERR, rcsid); |
---|
556 | // 1) we test: if d_i > 1, d_j =1 for all j<>i, then AS is irreducible. |
---|
557 | bool deg1=1; |
---|
558 | for ( CFListIterator i = AS ; i.hasItem(); i++ ){ |
---|
559 | if ( degree(i.getItem()) > 1 ){ |
---|
560 | if ( deg1 ) deg1=0; |
---|
561 | else return 0; // found 2nd poly with deg > 1 |
---|
562 | } |
---|
563 | } |
---|
564 | return 1; |
---|
565 | } |
---|
566 | |
---|
567 | |
---|
568 | // select an item from PS for irras |
---|
569 | CFList |
---|
570 | select( const ListCFList & PS){ |
---|
571 | |
---|
572 | return PS.getFirst(); |
---|
573 | } |
---|
574 | |
---|
575 | // divide list ppi in elems having length <= and > length |
---|
576 | void |
---|
577 | select( const ListCFList & ppi, int length, ListCFList & ppi1, ListCFList & ppi2){ |
---|
578 | CFList elem; |
---|
579 | for ( ListCFListIterator i=ppi ; i.hasItem(); i++ ){ |
---|
580 | elem = i.getItem(); |
---|
581 | if ( ! elem.isEmpty() ) |
---|
582 | if ( length <= elem.length() ){ ppi2.append(elem); } |
---|
583 | else { ppi1.append(elem); } |
---|
584 | } |
---|
585 | } |
---|
586 | |
---|
587 | |
---|
588 | ////////////////////////////////////////////////////////////// |
---|
589 | // help-functions for sets |
---|
590 | |
---|
591 | // is f in F ? |
---|
592 | static bool |
---|
593 | member( const CanonicalForm &f, const CFList &F){ |
---|
594 | |
---|
595 | for ( CFListIterator i=F; i.hasItem(); i++ ) |
---|
596 | if ( i.getItem() == f ) return 1; |
---|
597 | return 0; |
---|
598 | } |
---|
599 | |
---|
600 | // are list A and B the same? |
---|
601 | bool |
---|
602 | same( const CFList &A, const CFList &B ){ |
---|
603 | CFListIterator i; |
---|
604 | |
---|
605 | for (i = A; i.hasItem(); i++) |
---|
606 | if (! member(i.getItem(), B) ) return 0; |
---|
607 | for (i = B; i.hasItem(); i++) |
---|
608 | if (! member(i.getItem(), A) ) return 0; |
---|
609 | return 1; |
---|
610 | } |
---|
611 | |
---|
612 | |
---|
613 | // is List cs contained in List of lists pi? |
---|
614 | bool |
---|
615 | member( const CFList & cs, const ListCFList & pi ){ |
---|
616 | ListCFListIterator i; |
---|
617 | CFList elem; |
---|
618 | |
---|
619 | for ( i=pi; i.hasItem(); i++){ |
---|
620 | elem = i.getItem(); |
---|
621 | if ( same(cs,elem) ) return 1; |
---|
622 | } |
---|
623 | return 0; |
---|
624 | } |
---|
625 | |
---|
626 | // is PS a subset of Cset ? |
---|
627 | bool |
---|
628 | subset( const CFList &PS, const CFList &Cset ){ |
---|
629 | |
---|
630 | // CERR << "subset: called with: " << PS << " " << Cset << "\n"; |
---|
631 | for ( CFListIterator i=PS; i.hasItem(); i++ ) |
---|
632 | if ( ! member(i.getItem(), Cset) ) { |
---|
633 | // CERR << "subset: " << i.getItem() << " is not a member of " << Cset << "\n"; |
---|
634 | return 0; |
---|
635 | } |
---|
636 | return 1; |
---|
637 | } |
---|
638 | |
---|
639 | // Union of two List of Lists |
---|
640 | ListCFList |
---|
641 | MyUnion( const ListCFList & a, const ListCFList &b ){ |
---|
642 | ListCFList output; |
---|
643 | ListCFListIterator i; |
---|
644 | CFList elem; |
---|
645 | |
---|
646 | for ( i = a ; i.hasItem(); i++ ){ |
---|
647 | elem=i.getItem(); |
---|
648 | // if ( ! member(elem,output) ){ |
---|
649 | if ( (! elem.isEmpty()) && ( ! member(elem,output)) ){ |
---|
650 | output.append(elem); |
---|
651 | } |
---|
652 | } |
---|
653 | |
---|
654 | for ( i = b ; i.hasItem(); i++ ){ |
---|
655 | elem=i.getItem(); |
---|
656 | // if ( ! member(elem,output) ){ |
---|
657 | if ( (! elem.isEmpty()) && ( ! member(elem,output)) ){ |
---|
658 | output.append(elem); |
---|
659 | } |
---|
660 | } |
---|
661 | return output; |
---|
662 | } |
---|
663 | |
---|
664 | //if list b is member of the list of lists remove b and return the rest |
---|
665 | ListCFList |
---|
666 | MyDifference( const ListCFList & a, const CFList &b){ |
---|
667 | ListCFList output; |
---|
668 | ListCFListIterator i; |
---|
669 | CFList elem; |
---|
670 | |
---|
671 | for ( i = a ; i.hasItem(); i++ ){ |
---|
672 | elem=i.getItem(); |
---|
673 | if ( (! elem.isEmpty()) && ( ! same(elem,b)) ){ |
---|
674 | output.append(elem); |
---|
675 | } |
---|
676 | } |
---|
677 | return output; |
---|
678 | } |
---|
679 | |
---|
680 | // remove all elements of b from list of lists a and return the rest |
---|
681 | ListCFList |
---|
682 | Minus( const ListCFList & a, const ListCFList & b){ |
---|
683 | ListCFList output=a; |
---|
684 | |
---|
685 | for ( ListCFListIterator i=b; i.hasItem(); i++ ) |
---|
686 | output = MyDifference(output, i.getItem() ); |
---|
687 | |
---|
688 | return output; |
---|
689 | } |
---|
690 | |
---|
691 | #if 0 |
---|
692 | static CanonicalForm alg_lc(const CanonicalForm &f, const CFList as) |
---|
693 | { |
---|
694 | for(CFListIterator i=as; i.hasItem(); i++) |
---|
695 | { |
---|
696 | if (f.mvar()==i.getItem().mvar()) return f; |
---|
697 | } |
---|
698 | if (f.level()>0) |
---|
699 | { |
---|
700 | return alg_lc(f.LC(),as); |
---|
701 | } |
---|
702 | return CanonicalForm(1); |
---|
703 | } |
---|
704 | #endif |
---|
705 | |
---|
706 | CanonicalForm alg_gcd(const CanonicalForm & fff, const CanonicalForm &ggg, |
---|
707 | const CFList &as) |
---|
708 | { |
---|
709 | CanonicalForm f=fff; |
---|
710 | CanonicalForm g=ggg; |
---|
711 | f=Prem(f,as); |
---|
712 | g=Prem(g,as); |
---|
713 | if ( f.isZero() ) |
---|
714 | { |
---|
715 | if ( g.lc().sign() < 0 ) return -g; |
---|
716 | else return g; |
---|
717 | } |
---|
718 | else if ( g.isZero() ) |
---|
719 | { |
---|
720 | if ( f.lc().sign() < 0 ) return -f; |
---|
721 | else return f; |
---|
722 | } |
---|
723 | //out_cf("alg_gcd(",fff," , "); |
---|
724 | //out_cf("",ggg,")\n"); |
---|
725 | CanonicalForm res; |
---|
726 | // does as appear in f and g ? |
---|
727 | bool has_alg_var=false; |
---|
728 | for ( CFListIterator j=as;j.hasItem(); j++ ) |
---|
729 | { |
---|
730 | Variable v=j.getItem().mvar(); |
---|
731 | if (hasVar(f,v)) {has_alg_var=true; /*break;*/} |
---|
732 | if (hasVar(g,v)) {has_alg_var=true; /*break;*/} |
---|
733 | //out_cf("as:",j.getItem(),"\n"); |
---|
734 | } |
---|
735 | if (!has_alg_var) |
---|
736 | { |
---|
737 | if ((hasAlgVar(f)) |
---|
738 | || (hasAlgVar(g))) |
---|
739 | { |
---|
740 | Varlist ord; |
---|
741 | for ( CFListIterator j=as;j.hasItem(); j++ ) |
---|
742 | ord.append(j.getItem().mvar()); |
---|
743 | res=algcd(f,g,as,ord); |
---|
744 | } |
---|
745 | else |
---|
746 | res=gcd(f,g); |
---|
747 | //out_cf("gcd=",res,"\n"); |
---|
748 | //out_cf("of f=",fff," , "); |
---|
749 | //out_cf("and g=",ggg,"\n"); |
---|
750 | |
---|
751 | return res; |
---|
752 | } |
---|
753 | |
---|
754 | int mvf=f.level(); |
---|
755 | int mvg=g.level(); |
---|
756 | if (mvg > mvf) |
---|
757 | { |
---|
758 | CanonicalForm tmp=f; f=g; g=tmp; |
---|
759 | int tmp2=mvf; mvf=mvg; mvg=tmp2; |
---|
760 | } |
---|
761 | if (g.inBaseDomain() || f.inBaseDomain()) |
---|
762 | { |
---|
763 | //printf("const\n"); |
---|
764 | //out_cf("of f=",fff," , "); |
---|
765 | //out_cf("and g=",ggg,"\n"); |
---|
766 | return CanonicalForm(1); |
---|
767 | } |
---|
768 | |
---|
769 | // gcd of all coefficients: |
---|
770 | CFIterator i=f; |
---|
771 | CanonicalForm c_gcd=i.coeff(); i++; |
---|
772 | while( i.hasTerms()) |
---|
773 | { |
---|
774 | c_gcd=alg_gcd(i.coeff(),c_gcd,as); |
---|
775 | if (c_gcd.inBaseDomain()) break; |
---|
776 | i++; |
---|
777 | } |
---|
778 | //printf("f.mvar=%d (%d), g.mvar=%d (%d)\n",f.level(),mvf,g.level(),mvg); |
---|
779 | if (mvf!=mvg) // => mvf > mvg |
---|
780 | { |
---|
781 | res=alg_gcd(g,c_gcd,as); |
---|
782 | //out_cf("alg_gcd1=",res,"\n"); |
---|
783 | //out_cf("of f=",fff," , "); |
---|
784 | //out_cf("and g=",ggg,"\n"); |
---|
785 | return res; |
---|
786 | } |
---|
787 | // now: mvf==mvg, f.level()==g.level() |
---|
788 | if (!c_gcd.inBaseDomain()) |
---|
789 | { |
---|
790 | i=g; |
---|
791 | while( i.hasTerms()) |
---|
792 | { |
---|
793 | c_gcd=alg_gcd(i.coeff(),c_gcd,as); |
---|
794 | if (c_gcd.inBaseDomain()) break; |
---|
795 | i++; |
---|
796 | } |
---|
797 | } |
---|
798 | |
---|
799 | //f/=c_gcd; |
---|
800 | //g/=c_gcd; |
---|
801 | if (!c_gcd.isOne()) |
---|
802 | { |
---|
803 | f=divide(f,c_gcd,as); |
---|
804 | g=divide(g,c_gcd,as); |
---|
805 | } |
---|
806 | |
---|
807 | CFList gg; |
---|
808 | CanonicalForm r=1; |
---|
809 | while (1) |
---|
810 | { |
---|
811 | //printf("f.mvar=%d, g.mvar=%d\n",f.level(),g.level()); |
---|
812 | gg=as; |
---|
813 | if (!g.inCoeffDomain()) gg.append(g); |
---|
814 | //out_cf("Prem(",f," , "); |
---|
815 | //out_cf("",g,")\n"); |
---|
816 | if (g.inCoeffDomain()|| g.isZero()) |
---|
817 | { |
---|
818 | //printf("in coeff domain:"); |
---|
819 | if (g.isZero()) { //printf("0\n"); |
---|
820 | i=f; |
---|
821 | CanonicalForm f_gcd=i.coeff(); i++; |
---|
822 | while( i.hasTerms()) |
---|
823 | { |
---|
824 | f_gcd=alg_gcd(i.coeff(),f_gcd,as); |
---|
825 | if (f_gcd.inBaseDomain()) break; |
---|
826 | i++; |
---|
827 | } |
---|
828 | //out_cf("g=0 -> f:",f,"\n"); |
---|
829 | //out_cf("f_gcd:",f_gcd,"\n"); |
---|
830 | //out_cf("c_gcd:",c_gcd,"\n"); |
---|
831 | //f/=f_gcd; |
---|
832 | f=divide(f,f_gcd,as); |
---|
833 | //out_cf("f/f_gcd:",f,"\n"); |
---|
834 | f*=c_gcd; |
---|
835 | //out_cf("f*c_gcd:",f,"\n"); |
---|
836 | CanonicalForm r_lc=alg_lc(f); |
---|
837 | //out_cf("r_lc:",r_lc,"\n"); |
---|
838 | //f/=r_lc; |
---|
839 | f=divide(f,r_lc,as); |
---|
840 | //out_cf(" -> gcd:",f,"\n"); |
---|
841 | return f; |
---|
842 | } |
---|
843 | else { //printf("c\n"); |
---|
844 | return c_gcd;} |
---|
845 | } |
---|
846 | else if (g.level()==f.level()) r=Prem(f,gg); |
---|
847 | else |
---|
848 | { |
---|
849 | //printf("diff. level: %d, %d\n", f.level(), g.level()); |
---|
850 | // g and f have different levels |
---|
851 | //out_cf("c_gcd=",c_gcd,"\n"); |
---|
852 | //out_cf("of f=",fff," , "); |
---|
853 | //out_cf("and g=",ggg,"\n"); |
---|
854 | return c_gcd; |
---|
855 | } |
---|
856 | //out_cf("->",r,"\n"); |
---|
857 | f=g; |
---|
858 | g=r; |
---|
859 | } |
---|
860 | if (degree(f,Variable(mvg))==0) |
---|
861 | { |
---|
862 | // remark: mvf == mvg == f.level() ==g.level() |
---|
863 | //out_cf("c_gcd=",c_gcd,"\n"); |
---|
864 | //out_cf("of f=",fff," , "); |
---|
865 | //out_cf("and g=",ggg,"\n"); |
---|
866 | return c_gcd; |
---|
867 | } |
---|
868 | //out_cf("f=",f,"\n"); |
---|
869 | i=f; |
---|
870 | CanonicalForm k=i.coeff(); i++; |
---|
871 | //out_cf("k=",k,"\n"); |
---|
872 | while( i.hasTerms()) |
---|
873 | { |
---|
874 | if (k.inCoeffDomain()) break; |
---|
875 | k=alg_gcd(i.coeff(),k,as); |
---|
876 | //out_cf("k=",k,"\n"); |
---|
877 | i++; |
---|
878 | } |
---|
879 | //out_cf("end-k=",k,"\n"); |
---|
880 | f/=k; |
---|
881 | //out_cf("f/k=",f,"\n"); |
---|
882 | res=c_gcd*f; |
---|
883 | CanonicalForm r_lc=alg_lc(res); |
---|
884 | res/=r_lc; |
---|
885 | //CanonicalForm r_lc=alg_lc(res,as); |
---|
886 | //res/=r_lc; |
---|
887 | //out_cf("alg_gcd2=",res,"\n"); |
---|
888 | // out_cf("of f=",fff," , "); |
---|
889 | // out_cf("and g=",ggg,"\n"); |
---|
890 | //return res; |
---|
891 | //if (res.level()<fff.level() && res.level() < ggg.level()) |
---|
892 | // return alg_gcd(alg_gcd(fff,res,as),ggg,as); |
---|
893 | //else |
---|
894 | return res; |
---|
895 | } |
---|
896 | |
---|
897 | /* |
---|
898 | $Log: not supported by cvs2svn $ |
---|
899 | Revision 1.13 2006/06/19 13:37:47 Singular |
---|
900 | *hannes: more CS renamed |
---|
901 | |
---|
902 | Revision 1.12 2006/05/16 14:46:49 Singular |
---|
903 | *hannes: gcc 4.1 fixes |
---|
904 | |
---|
905 | Revision 1.11 2006/05/16 13:48:13 Singular |
---|
906 | *hannes: gcc 4.1 fix: factory changes |
---|
907 | |
---|
908 | Revision 1.10 2006/04/28 13:45:29 Singular |
---|
909 | *hannes: better tests for 0, 1 |
---|
910 | |
---|
911 | Revision 1.9 2003/05/28 11:52:52 Singular |
---|
912 | *pfister/hannes: newfactoras, alg_gcd, divide (see bug_33) |
---|
913 | |
---|
914 | Revision 1.8 2002/10/24 17:22:22 Singular |
---|
915 | * hannes: factoring in alg.ext., alg_gcd, NTL stuff |
---|
916 | |
---|
917 | Revision 1.7 2002/08/19 11:11:31 Singular |
---|
918 | * hannes/pfister: alg_gcd etc. |
---|
919 | |
---|
920 | Revision 1.6 2002/01/21 09:11:07 Singular |
---|
921 | * hannes: handle empty set in removecontent |
---|
922 | |
---|
923 | Revision 1.5 2001/06/21 14:57:04 Singular |
---|
924 | *hannes/GP: Factorize, newfactoras, ... |
---|
925 | |
---|
926 | Revision 1.4 1998/03/12 12:34:35 schmidt |
---|
927 | * charset/csutil.cc, charset/alg_factor.cc: all references to |
---|
928 | `common_den()' replaced by `bCommonDen()' |
---|
929 | |
---|
930 | Revision 1.3 1997/09/12 07:19:41 Singular |
---|
931 | * hannes/michael: libfac-0.3.0 |
---|
932 | |
---|
933 | Revision 1.3 1997/04/25 22:55:00 michael |
---|
934 | Version for libfac-0.2.1 |
---|
935 | |
---|
936 | Revision 1.2 1996/12/13 05:53:42 michael |
---|
937 | fixed a typo in nopower |
---|
938 | |
---|
939 | */ |
---|