source: git/factory/libfac/charset/charset.cc @ 5b2d2b

spielwiese
Last change on this file since 5b2d2b was 2024b69, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: commented out unused errmsg fix: dangling else
  • Property mode set to 100644
File size: 15.9 KB
Line 
1////////////////////////////////////////////////////////////
2// emacs edit mode for this file is -*- C++ -*-
3/////////////////////////////////////////////////////////////
4// FACTORY - Includes
5#include <factory.h>
6#ifdef HAVE_IOSTREAM
7#define CIN std::cin
8#else
9#define CIN cin
10#endif
11// Factor - Includes
12#include <SqrFree.h>
13#include <Factor.h>
14#include <interrupt.h>
15// Charset - Includes
16#include "csutil.h"
17#include "algfactor.h"
18#include "alg_factor.h"
19// Some CC's need this:
20#include "charset.h"
21
22#ifdef BASICSETDEBUG
23#  define DEBUGOUTPUT
24#else
25#  undef DEBUGOUTPUT
26#endif
27
28#include <libfac/factor/debug.h>
29#include "timing.h"
30TIMING_DEFINE_PRINT(subfactorize_time)
31
32
33// forward declarations:
34static CFList     irras(CFList & AS, int &ja, CanonicalForm & reducible);
35
36#ifdef BASICSETDEBUG
37#  define DEBUGOUTPUT
38#else
39#  undef DEBUGOUTPUT
40#endif
41#include <libfac/factor/debug.h>
42
43// the next computes a characteristic set (a basic set in Wang's sense)
44CFList
45BasicSet( const CFList &PS )
46{
47    CFList QS = PS, BS, RS;
48    CanonicalForm b;
49    int cb;
50
51    DEBOUTLN(CERR, "BasicSet: called with ps= ", PS);
52    if ( PS.length() < 2 ) return PS;
53    while ( ! QS.isEmpty() ) {
54        b = lowestRank( QS );
55        cb = rank( b );
56        DEBOUTLN(CERR, "BasicSet: choose b  = ", b);
57        DEBOUTLN(CERR, "BasicSet: it's rank = ", cb);
58        BS=Union(CFList(b),BS);//BS.append( b );
59        if ( rank( b ) == 0 )
60            return Union(PS, CFList(b)) ; // b should be the first elem!
61        else {
62            RS = CFList();
63            // QS:= {q \in QS -{B} | q is reduced wrt b}
64            // We can process whole QS, because b is not reduced wrt. b
65            for ( CFListIterator i = QS; i.hasItem(); ++i )
66                if ( degree( i.getItem(), cb ) < degree( b ) )
67                    //RS.append( i.getItem() );
68                    RS = Union(CFList(i.getItem()),RS);
69            QS = RS;
70        }
71    }
72    DEBOUTLN(CERR, "BasicSet: returning bs= ", BS);
73    return BS;
74}
75
76int
77checkok( const CFList & PS, CFList & FS2){
78  CanonicalForm elem;
79
80  for ( CFListIterator i=PS; i.hasItem(); i++){
81    elem= i.getItem();
82    for (CFListIterator j=FS2; j.hasItem(); j++){
83      if (elem == j.getItem()){
84         //        FS2= Difference(FS2,CFList(elem));
85         return 0;
86      }
87    }
88  }
89  return 1;
90}
91
92#ifdef MCHARSETNDEBUG
93#  define DEBUGOUTPUT
94#else
95#  undef DEBUGOUTPUT
96#endif
97#include <libfac/factor/debug.h>
98
99// The modified CharSet (an extended characteristic set with certain factors
100// canceled; this is a characteristic set in Wang's sense)
101CFList
102MCharSetN( const CFList &PS, PremForm & Remembern ){
103  CFList QS = PS, RS = PS, CSet, OLDCS;
104
105  DEBOUTLN(CERR, "MCharSetN: called with ps= ", PS);
106  while ( ! RS.isEmpty() ) {
107    CSet = BasicSet( QS );
108    OLDCS=CSet;
109    DEBOUTLN(CERR, "MCharSetN: CS= ", CSet);
110//     if ( getNumVars(CSet.getFirst()) > 1 ){
111//       //CSet = removecontent(CSet, Remembern);
112// #ifdef MCHARSETNDEBUG
113//       CERR << "MCharSetN: CSet= " << CSet << "\n";
114// #endif
115//     }
116    Remembern.FS1 = Union(Remembern.FS1, initalset1(CSet));
117    DEBOUTLN(CERR, "MCharSetN: Remembern.FS1= ", Remembern.FS1);
118    DEBOUTLN(CERR, "MCharSetN: Remembern.FS2= ", Remembern.FS2);
119    RS = CFList();
120    if ( rank( CSet.getFirst() ) != 0 ) {
121      CFList D = Difference( QS, CSet );
122      DEBOUT(CERR, "MCharSetN: Difference( ", QS);
123      DEBOUT(CERR, " , ", CSet);
124      DEBOUTLN(CERR, " ) = ", D);
125//CERR << "MCharSetN: Difference( " << QS << " , " << CSet << " ) = " << D << "\n";
126      //PremForm Oldremember=Remembern;
127      //PremForm Newremember=Remembern;
128      for ( CFListIterator i = D; i.hasItem(); ++i ) {
129        CanonicalForm r = Prem( i.getItem(), CSet );
130        DEBOUT(CERR,"MCharSetN: Prem(", i.getItem()  );
131        DEBOUT(CERR, ",", CSet);
132        DEBOUTLN(CERR,") = ", r);
133//CERR << "MCharSetN: Prem("<< i.getItem() << "," << CSet << ") = " << r << "\n";
134        if ( r != 0 ){
135          //removefactor( r, Newremember );
136          removefactor( r, Remembern );
137          //Remembern.FS2 = Union(Remembern.FS2, Newremember.FS2);
138          //Newremember = Oldremember;
139          //if ( cls(r) > 0 )
140            //RS=Union(CFList(r),RS);//RS.append( r );
141            RS=Union(RS,CFList(r));
142        }
143      }
144      if ( ! checkok(RS,Remembern.FS2)) return CFList(CanonicalForm(1));
145      DEBOUTLN(CERR, "MCharSetN: RS= ", RS);
146      //QS = Union( QS, RS );
147      QS = Union(OLDCS,RS);
148      DEBOUTLN(CERR, "MCharSetN: QS= Union(QS,RS)= ", QS);
149    }
150    else{ return CFList(CanonicalForm(1)); }
151  }
152  DEBOUTLN(CERR, "MCharSetN: Removed factors: ", Remembern.FS2);
153  DEBOUTLN(CERR, "MCharSetN: Remembern.FS1: ", Remembern.FS1);
154
155  return CSet;
156}
157
158
159CFList
160mcharset( const CFList &PS, PremForm & Remembern ){
161  CFList cs= MCharSetN(PS, Remembern );
162  CFList rs= remsetb(Difference(PS,cs),cs);
163
164  DEBOUTLN(CERR, "mcharset: cs= ", cs);
165  DEBOUTLN(CERR, "mcharset: rs= ", rs);
166  if ( rs.length() > 0 )
167    cs= mcharset(Union(PS,Union(cs,rs)), Remembern);
168  return cs;
169}
170
171// the "original" extended characteristic set
172CFList
173CharSet( const CFList &PS ){
174  CFList QS = PS, RS = PS, CSet;
175
176  while ( ! RS.isEmpty() ) {
177    CSet = BasicSet( QS );
178    DEBOUTLN(CERR, "CharSet: CSet= ", CSet);
179    RS = CFList();
180    if ( rank( CSet.getFirst() ) != 0 ) {
181      CFList D = Difference( QS, CSet );
182      for ( CFListIterator i = D; i.hasItem(); ++i ) {
183        CanonicalForm r = Prem( i.getItem(), CSet );
184        if ( r != 0 )  RS=Union(CFList(r),RS);//RS.append( r );
185      }
186      QS = Union( QS, RS );
187    }
188  }
189  return CSet;
190}
191
192static CFList
193charseta( const CFList & PS ){
194  CFList QS = PS, RS = PS, CSet;
195
196  while ( ! RS.isEmpty() ) {
197    CSet = CharSet( QS );
198    RS = CFList();
199    if ( rank( CSet.getFirst() ) != 0 ) {
200      CFList D = Difference( QS, CSet );
201      for ( CFListIterator i = D; i.hasItem(); ++i ) {
202        CanonicalForm r = Prem( i.getItem(), CSet );
203        if ( r != 0 )  RS=Union(CFList(r),RS);//RS.append( r );
204      }
205      QS = Union(CSet,Union( QS, RS ));
206    }
207    else return CFList(CanonicalForm(1));
208  }
209  return CSet;
210}
211
212static bool
213contractsub( const CFList & cs1, const CFList & cs2 ){
214  CFListIterator i;
215
216  for ( i=cs1; i.hasItem(); i++ )
217    if ( Prem(i.getItem(),cs2 ) != 0 ) return false;
218  CFList is=initalset1(cs1);
219  for ( i=is; i.hasItem(); i++ )
220    if ( Prem(i.getItem(),cs2 ) == 0 ) return false;
221  return true;
222}
223
224static ListCFList
225contract( const ListCFList & cs){
226  ListCFList mem,ts;
227  CFList iitem,jitem;
228
229  if ( cs.length() < 2 ) return cs;
230
231  for ( ListCFListIterator i=cs; i.hasItem(); i++ ){
232    iitem=i.getItem();
233    if ( ! member(iitem, mem))
234      for ( ListCFListIterator j=i; j.hasItem(); j++){
235        jitem=j.getItem();
236        if ( ! same( iitem, jitem ) )
237          if ( ! member(jitem, mem))
238          {
239            if ( contractsub(iitem, jitem) ){
240              ts.append(jitem); mem.append(jitem);
241            }
242            else
243              if ( contractsub(jitem, iitem) ){
244                ts.append(iitem);
245              }
246          }
247      }
248  }
249  return Minus(cs,ts);
250}
251
252static ListCFList
253adjoin(const CFList & is, const CFList & qs, const ListCFList & qh ){
254  ListCFList iss,qhi;
255  ListCFListIterator j;
256  CFList iscopy,itt;
257  CFListIterator i;
258  CanonicalForm elem;
259  int ind, length;
260
261  for ( i=is ; i.hasItem(); i++ ){
262    elem=i.getItem();
263    if ( cls(elem) > 0 ) iscopy=Union(CFList(elem),iscopy);
264  }
265  if ( iscopy.isEmpty() ) return iss;
266  qhi = MyDifference(qh,qs);
267  length = qhi.length();
268  for ( i =iscopy; i.hasItem(); i++){
269    itt = Union(qs,CFList(i.getItem()));
270    ind = 0;
271    if ( length > 0 )
272      for ( j=qhi; j.hasItem(); j++ )
273        if ( subset(j.getItem(),itt )) ind=1;
274    if ( ind == 0 ) iss.append(itt);
275  }
276  return iss;
277}
278
279static ListCFList
280adjoinb(const CFList & is, const CFList & qs, const ListCFList & qh ,const CFList & cs){
281  ListCFList iss,qhi;
282  ListCFListIterator j;
283  CFList iscopy,itt;
284  CFListIterator i;
285  CanonicalForm elem;
286  int ind, length;
287
288  for ( i=is ; i.hasItem(); i++ ){
289    elem=i.getItem();
290    if ( cls(elem) > 0 ) iscopy=Union(CFList(elem),iscopy);
291  }
292  if ( iscopy.isEmpty() ) return iss;
293  qhi = MyDifference(qh,qs);
294  length = qhi.length();
295  for ( i =iscopy; i.hasItem(); i++){
296    itt = Union(Union(qs,CFList(i.getItem())),cs);
297    ind = 0;
298    if ( length > 0 )
299      for ( j=qhi; j.hasItem(); j++ )
300        if ( subset(j.getItem(),itt )) ind=1;
301    if ( ind == 0 ) {iss.append(itt);}
302  }
303  return iss;
304}
305
306static ListCFList
307sort( const ListCFList & list_to_sort ){
308  ListCFList output,copy=list_to_sort;
309  CFList l,qs1,elem;
310
311  l = copy.getLast(); copy.removeLast();
312  if ( copy.length() == 0 ){ return ListCFList(l); }
313  for ( ListCFListIterator i=copy ; i.hasItem(); i++ ){
314    elem = i.getItem();
315    if ( elem.length() > l.length() ) {
316      output = MyUnion( ListCFList(l), output);
317      l= elem;
318    }
319    else{ output = MyUnion(output, ListCFList(elem) ); }
320  }
321  //output = MyUnion(ListCFList(l),sort(output));
322  output = MyUnion(ListCFList(l),output);
323  return output;
324}
325
326#ifdef IRRCHARSERIESDEBUG
327#  define DEBUGOUTPUT
328#else
329#  undef DEBUGOUTPUT
330#endif
331#include <libfac/factor/debug.h>
332
333ListCFList
334IrrCharSeries( const CFList &PS, int opt ){
335  CanonicalForm reducible,reducible2;
336  CFList qs,cs,factorset,is,ts;
337  ListCFList pi,ppi,qqi,qsi,iss,qhi= ListCFList(PS);
338  int nr_of_iteration=0,ts2,highestlevel=0;
339
340//  CERR << getCharacteristic() << "\n";
341  for ( CFListIterator Ps=PS; Ps.hasItem(); Ps++ )
342    if ( level(Ps.getItem() ) > highestlevel ) highestlevel = level(Ps.getItem()) ;
343//  for ( int xx=1; xx <= highestlevel; xx++)
344//   CERR << Variable(xx) ;
345//  CERR << "\n";
346//  for ( CFListIterator Ps=PS; Ps.hasItem(); Ps++ )
347//    CERR << Ps.getItem() << ", " ;//<< "\n";
348//  CERR <<  "\n";
349  while ( ! qhi.isEmpty() ) {
350    qhi=sort(qhi);
351    DEBOUTLN(CERR, "qhi is: ", qhi);
352    qs=qhi.getFirst();
353    DEBOUTLN(CERR, "qs  is: ", qs);
354    DEBOUTLN(CERR, "ppi is: ", ppi);
355    ListCFList ppi1,ppi2;
356    select(ppi,qs.length(),ppi1,ppi2);
357    DEBOUTLN(CERR, "ppi1 is: ", ppi1);
358    DEBOUTLN(CERR, "ppi2 is: ", ppi2);
359    qqi = MyUnion(ppi2,qqi);
360    DEBOUTLN(CERR, "qqi is: ", qqi);
361    if ( nr_of_iteration == 0 ){ nr_of_iteration += 1; ppi = ListCFList(); }
362    else{ nr_of_iteration += 1; ppi = MyUnion(ListCFList(qs),ppi1); }
363    DEBOUTLN(CERR,"ppi is: ", ppi);
364    PremForm Remembern;
365    cs = MCharSetN(qs,Remembern);
366    DEBOUTLN(CERR, "cs is: ", cs);
367    DEBOUTLN(CERR, "factorset is: ", Remembern.FS2);
368    cs = removecontent(cs,Remembern);
369    factorset=Remembern.FS2;
370    DEBOUTLN(CERR, "cs (after removecontent) is: ", cs);
371    DEBOUTLN(CERR, "factorset is: ", factorset);
372    // Hier: removecontent einfuegen!!!!
373    if ( cls(cs.getFirst()) > 0 ){
374      ts = irras(cs,ts2, reducible);
375
376      // INTERRUPTHANDLER
377      if ( interrupt_handle() ) return ListCFList() ;
378      // INTERRUPTHANDLER
379
380      DEBOUTLN(CERR, "ts is: ", ts);
381      DEBOUTLN(CERR, "ts2 is: ", ts2);
382      // next is preliminary: should be ==0
383      if ( ts2 <= 0 ){ //irreducible
384        if ( ! subset(cs,qs) ){
385          DEBOUTMSG(CERR, "cs is not a subset of qs");
386          cs = charseta(Union(qs,cs));
387          DEBOUTLN(CERR, "new cs is: ", cs);
388        }
389        if ( ! member(cs,pi) ){
390          pi = MyUnion(pi, ListCFList(cs));
391          DEBOUTMSG(CERR, "cs is not a member of pi");
392          DEBOUTLN(CERR, "pi is: ", pi);
393          if ( cls(cs.getFirst()) > 0 ){
394            ts = irras(cs,ts2,reducible);
395
396            // INTERRUPTHANDLER
397            if ( interrupt_handle() ) return ListCFList() ;
398            // INTERRUPTHANDLER
399
400            DEBOUTLN(CERR, "ts is: ", ts);
401            DEBOUTLN(CERR, "ts2 is: ", ts2);
402            // next is preliminary: should be ==0
403            if ( ts2 <= 0 ){ //irreducible
404              qsi = MyUnion(qsi,ListCFList(cs));
405              DEBOUTLN(CERR, "qsi is: ", qsi);
406              if ( cs.length() == highestlevel ){
407                DEBOUTLN(CERR, "cs.length() == nops(ord) :", cs.length());
408                is = factorps(factorset);
409              }
410              else{
411                DEBOUT(CERR,"cs.length() != nops(ord) :", cs.length());
412                DEBOUTLN(CERR, "  nops(ord)= ", highestlevel);
413                is = Union(initalset1(cs),factorps(factorset));
414              }
415              DEBOUTLN(CERR, "is is: ", is);
416              iss = adjoin(is,qs,qqi);
417              DEBOUTLN(CERR, "iss is: ", iss);
418            }
419          }
420          else{ iss = adjoin(factorps(factorset),qs,qqi); }
421        }
422        else{
423          DEBOUTMSG(CERR, "cs is a member of pi");
424          iss = adjoin(factorps(factorset),qs,qqi); }
425        DEBOUTLN(CERR, "iss is: ", iss);
426        DEBOUTLN(CERR, "   factorps(factorset)= ", factorps(factorset));
427        DEBOUTLN(CERR, "   qs= ", qs);
428        DEBOUTLN(CERR, "   qqi= ", qqi);
429      }
430      // next is preliminary: should be !=0
431      if ( ts2 > 0 ){
432        is = factorps(factorset);
433        DEBOUTLN(CERR, "is is: ", is);
434        if ( ts2 > 1 ){
435          // setup cst: need it later for adjoinb
436          CFList cst;
437          for ( CFListIterator i=cs ; i.hasItem(); i++){
438            if ( i.getItem() == reducible ) { break; }
439            else { cst.append(i.getItem()); }
440          }
441          is = Union(initalset1(cst), is);
442          iss = MyUnion(adjoin(is,qs,qqi), adjoinb(ts,qs,qqi,cst));
443        }
444        else{ iss = adjoin(Union(is,ts),qs,qqi); }
445        DEBOUTLN(CERR, "iss is: ", iss);
446      }
447    }
448    else{
449      iss = adjoin(factorps(factorset),qs,qqi);
450      DEBOUTMSG(CERR, "case: cs is a constant.");
451      DEBOUTLN(CERR, "  qs = ", qs);
452      DEBOUTLN(CERR, "  qqi = ", qqi);
453      DEBOUTLN(CERR, "  iss = adjoin(factorps(factorset),qs,qqi) = ",iss);
454    }
455    if ( qhi.length() > 1 ){ qhi.removeFirst(); qhi = MyUnion(qhi,iss); }
456    else{ qhi = iss; }
457    DEBOUTLN(CERR, "iss is: ", iss);
458  }
459  if ( ! qsi.isEmpty() ){
460    DEBOUTLN(CERR, "qsi before contract= ", qsi);
461    if ( opt == 0 ){
462       return contract( qsi );
463    }
464    else { return qsi; }
465  }
466  else{ return ListCFList() ; }
467}
468
469// tests for characteristic sets
470//////////////////////////////////
471#ifdef IRRASDEBUG
472#  define DEBUGOUTPUT
473#else
474#  undef DEBUGOUTPUT
475#endif
476
477#include <libfac/factor/debug.h>
478
479static CFList
480irras( CFList & AS, int & ja, CanonicalForm & reducible)
481{
482  CFFList qs;
483  CFList ts,as;
484  CanonicalForm elem;
485  int ind=1,nr=0, success=-1;
486  CFListIterator i;
487
488  ja = 0;
489  DEBOUTLN(CERR, "irras: called with: AS= ", AS);
490  for ( i=AS; i.hasItem(); i++ )
491  {
492    elem = i.getItem();
493    nr += 1;
494    DEBOUT(CERR, "irras: factoring: ", elem);
495    if ( degree(elem) > 1 ) // linear poly's are irreduzible
496    {
497      qs = factorize(elem);
498      // remove a constant
499      if (qs.getFirst().factor().degree()==0) qs.removeFirst();
500    }
501    else
502    {
503      qs=(CFFactor(elem,1));
504    }
505    DEBOUTLN(CERR, "  = ", qs);
506    // INTERRUPTHANDLER
507    if ( interrupt_handle() ) return CFList() ;
508    // INTERRUPTHANDLER
509
510    if ( (qs.length() >= 2 ) || (qs.getFirst().exp() > 1))
511    {
512      DEBOUTLN(CERR, "irras: Setting ind=0, ja= ", nr);
513      ja=nr; ind=0; reducible= elem;
514      break;
515    }
516    //    else{ as.append(elem) ; }
517  }
518  //  CERR << "ind= " << ind << "\n";
519  if ( ind == 1 ) //&& ( as.length() > 1) )
520  {
521    if ( irreducible(AS) )
522    { // as quasilinear? => irreducible!
523      ja = 0;
524      DEBOUTLN(CERR, "as is irreducible. as= ", AS);
525    }
526    else
527    {
528      i=AS;
529      for ( nr=1; nr< AS.length(); nr++)
530      {
531        as.append(i.getItem());
532        i++;
533        if ( degree(i.getItem()) > 1 )
534        {  // search for a non linear elem
535          elem=i.getItem();
536          //if (as.length()==1)
537          //  qs = Factorize2(elem,as.getFirst());
538          //else
539            qs= newfactoras(elem,as,success);
540          if ( qs.length() > 1 || qs.getFirst().exp() > 1 )
541          { //found elem is reducible
542            reducible=elem;
543            ja=nr+1;
544            break;
545          }
546        }
547      }
548    }
549  }
550  for ( CFFListIterator k=qs; k.hasItem();k++)
551    ts.append(k.getItem().factor());
552  return ts;
553}
554
555///////////////////////////////////////////////////////////////////////////////
Note: See TracBrowser for help on using the repository browser.