source: git/libfac/factor/SqrFree.cc @ 7d889c

spielwiese
Last change on this file since 7d889c was 7d889c, checked in by Hans Schönemann <hannes@…>, 26 years ago
* hannes: moved WerrorS from C++ to C (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc) git-svn-id: file:///usr/local/Singular/svn/trunk@910 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 11.3 KB
Line 
1/* Copyright 1996 Michael Messollen. All rights reserved. */
2///////////////////////////////////////////////////////////////////////////////
3// emacs edit mode for this file is -*- C++ -*-
4static char * rcsid = "$Id: SqrFree.cc,v 1.4 1997-11-18 16:39:06 Singular Exp $";
5static 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///////////////////////////////////////////////////////////////////////////////
7// FACTORY - Includes
8#include<factory.h>
9// Factor - Includes
10#include "tmpl_inst.h"
11#include "helpstuff.h"
12// some CC's need this:
13#include "SqrFree.h"
14
15#ifdef SINGULAR
16#  define HAVE_SINGULAR
17   extern "C" { void WerrorS(char *); }
18#endif
19
20#ifdef SQRFREEDEBUG
21# define DEBUGOUTPUT
22#else
23# undef DEBUGOUTPUT
24#endif
25
26#include "debug.h"
27#include "timing.h"
28TIMING_DEFINE_PRINT(squarefree_time);
29TIMING_DEFINE_PRINT(gcd_time);
30
31
32static inline CFFactor
33Powerup( const CFFactor & F , int exp=1){ 
34  return CFFactor(F.factor(), exp*F.exp()) ; 
35}
36
37static CFFList
38Powerup( const CFFList & Inputlist , int exp=1 ){
39  CFFList Outputlist;
40
41  for ( CFFListIterator i=Inputlist; i.hasItem(); i++ )
42    Outputlist.append(Powerup(i.getItem(), exp));
43  return Outputlist ;
44}
45
46///////////////////////////////////////////////////////////////
47// Compute the Pth root of a polynomial in characteristic p  //
48// f must be a polynomial which we can take the Pth root of. //
49// Domain is q=p^m , f a uni/multivariate polynomial         //
50///////////////////////////////////////////////////////////////
51static CanonicalForm
52PthRoot( const CanonicalForm & f ){
53  CanonicalForm RES, R = f;
54  int n= max(level(R),getNumVars(R)), p= getCharacteristic();
55 
56  if (n==0){ // constant
57    if (R.inExtension()) // not in prime field; f over |F(q=p^k)
58      R = power(R,Powerup(p,getGFDegree() - 1)) ;
59    // if f in prime field, do nothing
60    return R;
61  }
62  // we assume R is a Pth power here
63  RES = R.genZero();
64  Variable x(n);
65  for (int i=0; i<= (int) (degree(R,level(R))/p) ; i++)
66    RES += PthRoot( R[i*p] ) * power(x,i);
67  return RES;
68}
69
70///////////////////////////////////////////////////////////////
71// A uni/multivariate SqrFreeTest routine.                   //
72// Cheaper to run if all you want is a test.                 //
73// Works for charcteristic 0 and q=p^m                       //
74// Returns 1 if poly r is SqrFree, 0 if SqrFree will do some //
75// kind of factorization.                                    //
76// Would be much more effcient iff we had *good*             //
77//  uni/multivariate gcd's and/or gcdtest's                  //
78///////////////////////////////////////////////////////////////
79int
80SqrFreeTest( const CanonicalForm & r, int opt){
81  CanonicalForm f=r, g;
82  int n=level(f);
83
84  if (getNumVars(f)==0) return 1 ; // a constant is SqrFree
85  if ( f.isUnivariate() ) {
86    g= f.deriv();
87    if ( getCharacteristic() > 0 && g.isZero() ) return 0 ;
88    // Next: it would be best to have a *univariate* gcd-test which returns
89    // 0 iff gcdtest(f,g) == 1 or a constant ( for real Polynomials )
90    g = mygcd(f,g);
91    if ( g.isOne() || (-g).isOne() ) return 1;
92    else 
93      if ( getNumVars(g) == 0 ) return 1;// <- totaldegree!!!
94      else return 0 ;
95  }
96  else { // multivariate case
97    for ( int k=1; k<=n; k++ ) {
98      g = swapvar(f,k,n); g = content(g);
99      // g = 1 || -1 : sqr-free, g poly : not sqr-free, g number : opt helps
100      if ( ! (g.isOne() || (-g).isOne() || getNumVars(g)==0 ) ) {
101        if ( opt==0 ) return 0;
102        else {
103          if ( SqrFreeTest(g,1) == 0 ) return 0;
104          g = swapvar(g,k,n);
105          f /=g ;
106        }
107      }
108    }
109    // Now f is primitive
110    n = level(f); // maybe less indeterminants
111    //    if ( totaldegree(f) <= 1 ) return 1;
112   
113    // Let`s look if it is a Pth root
114    if ( getCharacteristic() > 0 )
115      for (int k=1; k<=n; k++ ) {
116        g=swapvar(f,k,n); g=g.deriv();
117        if ( ! g.isZero() ) break ;
118        else if ( k==n) return 0 ; // really is Pth root
119      }
120    g = f.deriv() ;
121    // Next: it would be best to have a *multivariate* gcd-test which returns
122    // 0 iff gcdtest(f,g) == 1 or a constant ( for real Polynomials )
123    g= mygcd(f,g);
124    if ( g.isOne() || (-g).isOne() || (g==f) || (getNumVars(g)==0) ) return 1 ;
125    else return 0 ;
126  }
127#ifdef HAVE_SINGULAR
128  WerrorS("libfac: ERROR: SqrFreeTest: we should never fall trough here!");
129#else
130  cerr << "\nlibfac: ERROR: SqrFreeTest: we should never fall trough here!\n" 
131       << rcsid << errmsg << endl;
132#endif
133  return 0;
134}
135
136///////////////////////////////////////////////////////////////
137// A uni/multivariate SqrFree routine.Works for polynomials  //
138// which don\'t have a constant as the content.              //
139// Works for charcteristic 0 and q=p^m                       //
140// returns a list of polys each of sqrfree, but gcd(f_i,f_j) //
141// needs not to be 1 !!!!!                                   //
142///////////////////////////////////////////////////////////////
143static CFFList
144SqrFreed( const CanonicalForm & r ){
145  CanonicalForm h, g, f = r;
146  CFFList Outputlist;
147  int n = level(f);
148
149  DEBINCLEVEL(cout, "SqrFreed");
150  DEBOUTLN(cout, "Called with r= ", r);
151  if (getNumVars(f)==0 ) { // just a constant; return it
152    Outputlist= myappend(Outputlist,CFFactor(f,1));
153    return Outputlist ;
154  }
155
156// We look if we do have a content; if so, SqrFreed the content
157// and continue computations with pp(f)
158  for (int k=1; k<=n; k++) {
159    g = swapvar(f,k,n); g = content(g);
160    if ( ! (g.isOne() || (-g).isOne() || degree(g)==0 )) {
161      g = swapvar(g,k,n);
162      DEBOUTLN(cout, "We have a content: ", g);
163      Outputlist = myUnion(InternalSqrFree(g),Outputlist); // should we add a
164                                                // SqrFreeTest(g) first ?
165      DEBOUTLN(cout, "Outputlist is now: ", Outputlist);
166      f /=g;
167      DEBOUTLN(cout, "f is now: ", f);
168    }
169  }
170
171// Now f is primitive; Let`s look if f is univariate
172  if ( f.isUnivariate() ) {
173    DEBOUTLN(cout, "f is univariate: ", f);
174    g = content(g);
175    if ( ! (g.isOne() || (-g).isOne() ) ){
176      Outputlist= myappend(Outputlist,CFFactor(g,1)) ;
177      f /= g;
178    }
179    Outputlist = Union(sqrFree(f),Outputlist) ; 
180    DEBOUTLN(cout, "Outputlist after univ. sqrFree(f) = ", Outputlist);
181    DEBDECLEVEL(cout, "SqrFreed");
182    return Outputlist ;
183  }
184
185// Linear?
186  if ( totaldegree(f) <= 1 ) {
187    Outputlist= myappend(Outputlist,CFFactor(f,1)) ;
188    DEBDECLEVEL(cout, "SqrFreed");
189    return Outputlist ;
190  }
191
192// is it Pth root?
193  n=level(f); // maybe less indeterminants
194  g= f.deriv();
195  if ( getCharacteristic() > 0 && g.isZero() ){  // Pth roots only apply to char > 0
196    for (int k=1; k<=n; k++) {
197      g=swapvar(f,k,n) ; g = g.deriv();
198      if ( ! g.isZero() ){ // can`t be Pth root
199        CFFList Outputlist2= SqrFreed(swapvar(f,k,n)); 
200        for (CFFListIterator inter=Outputlist2; inter.hasItem(); inter++){
201          Outputlist= myappend(Outputlist, CFFactor(swapvar(inter.getItem().factor(),k,n), inter.getItem().exp()));
202        }
203        return Outputlist;
204      }
205      else 
206        if ( k==n ) { // really is Pth power
207          DEBOUTLN(cout, "f is a p'th root: ", f);
208          CFMap m;
209          g = compress(f,m);
210          f = m(PthRoot(g));
211          DEBOUTLN(cout, "  that is       : ", f);
212          // now : Outputlist union ( SqrFreed(f) )^getCharacteristic()
213          Outputlist=myUnion(Powerup(InternalSqrFree(f),getCharacteristic()),Outputlist);
214          DEBDECLEVEL(cout, "SqrFreed");
215          return Outputlist ;
216        }
217    }
218  }
219  g = f.deriv();
220  DEBOUTLN(cout, "calculating mygcd of ", f);
221  DEBOUTLN(cout, "               and ", g);
222  h = mygcd(f,pp(g));  h /= lc(h);
223  DEBOUTLN(cout,"mygcd(f,g)= ",h);
224  if ( (h.isOne()) || ( h==f) || ((-h).isOne()) || getNumVars(h)==0 ) { // no common factor
225    Outputlist= myappend(Outputlist,CFFactor(f,1)) ;
226    DEBOUTLN(cout, "Outputlist= ", Outputlist);
227    DEBDECLEVEL(cout, "SqrFreed");
228    return Outputlist ;
229  }
230  else { // we can split into two nontrivial pieces
231    f /= h; // Now we have split the poly into f and h
232    g = lc(f);
233    if ( g != f.genOne() && getNumVars(g) == 0 ){
234       Outputlist= myappend(Outputlist,CFFactor(g,1)) ;
235       f /= g;
236    }
237    DEBOUTLN(cout, "Split into f= ", f);
238    DEBOUTLN(cout, "       and h= ", h);
239    // For char > 0 the polys f and h can have Pth roots; so we need a test
240    // Test is disabled because timing is the same
241//    if ( SqrFreeTest(f,0) )
242//      Outputlist= myappend(Outputlist,CFFactor(f,1)) ;
243//    else
244    Outputlist=myUnion(Outputlist, InternalSqrFree(f));
245//    if ( SqrFreeTest(h,0) )
246//      Outputlist= myappend(Outputlist,CFFactor(h,1)) ;
247//    else
248    Outputlist=myUnion(Outputlist,InternalSqrFree(h));
249    DEBOUTLN(cout, "Returning list ", Outputlist);
250    DEBDECLEVEL(cout, "SqrFreed");
251    return Outputlist ;
252  }
253#ifdef HAVE_SINGULAR
254  WerrorS("libfac: ERROR: SqrFreed: we should never fall trough here!");
255#else
256  cerr << "\nlibfac: ERROR: SqrFreed: we should never fall trough here!\n" 
257       << rcsid << errmsg << endl;
258#endif
259  DEBDECLEVEL(cout, "SqrFreed");
260  return Outputlist; // for safety purpose
261}
262
263///////////////////////////////////////////////////////////////
264// The user front-end for the SqrFreed routine.              //
265// Input can have a constant as content                      //
266///////////////////////////////////////////////////////////////
267CFFList
268InternalSqrFree( const CanonicalForm & r ){
269  CanonicalForm g=icontent(r), f = r;
270  CFFList Outputlist, Outputlist2;
271
272  DEBINCLEVEL(cout, "InternalSqrFree");
273  DEBOUTMSG(cout, rcsid);
274  DEBOUTLN(cout,"Called with f= ", f);
275
276  // Take care of stupid users giving us constants
277  if ( getNumVars(f) == 0 ) { // a constant ; Exp==1 even if f==0
278      Outputlist= myappend(Outputlist,CFFactor(f,1));
279  }
280  else{
281      // Now we are sure: we have a nonconstant polynomial
282      g = lc(f);
283      while ( getNumVars(g) != 0 ) g=content(g);
284      if ( ! g.isOne() ) Outputlist= myappend(Outputlist,CFFactor(g,1)) ;
285      f /= g;
286      if ( getNumVars(f) != 0 ) // a real polynomial
287        Outputlist=myUnion(SqrFreed(f),Outputlist) ;
288  }
289  DEBOUTLN(cout,"Outputlist = ", Outputlist);
290  for ( CFFListIterator i=Outputlist; i.hasItem(); i++ )
291    if ( getNumVars(i.getItem().factor()) > 0 )
292      Outputlist2.append(i.getItem());
293
294  DEBOUTLN(cout,"Outputlist2 = ", Outputlist2);
295  DEBDECLEVEL(cout, "InternalSqrFree");
296  return Outputlist2 ;
297}
298
299CFFList
300SqrFree(const CanonicalForm & r ){
301  CFFList outputlist, sqrfreelist = InternalSqrFree(r);
302  CFFListIterator i;
303  CanonicalForm elem;
304  int n=totaldegree(r);
305
306  DEBINCLEVEL(cout, "SqrFree");
307
308  if ( sqrfreelist.length() < 2 ){
309    DEBDECLEVEL(cout, "SqrFree");
310    return sqrfreelist;
311  }
312  for ( int j=1; j<=n; j++ ){
313    elem =1;
314    for ( i = sqrfreelist; i.hasItem() ; i++ ){
315      if ( i.getItem().exp() == j ) elem *= i.getItem().factor();
316    }
317    if ( elem != 1 ) outputlist.append(CFFactor(elem,j));
318  }
319  elem=1;
320  for ( i=outputlist; i.hasItem(); i++ )
321    if ( getNumVars(i.getItem().factor()) > 0 )
322      elem*= power(i.getItem().factor(),i.getItem().exp());
323  elem= r/elem;
324  outputlist.insert(CFFactor(elem,1));
325
326  DEBOUTLN(cout, "SqrFree returns list:", outputlist);
327  DEBDECLEVEL(cout, "SqrFree");
328  return outputlist;
329}
330
331/*
332$Log: not supported by cvs2svn $
333Revision 1.3  1997/09/12 07:19:50  Singular
334* hannes/michael: libfac-0.3.0
335
336Revision 1.4  1997/04/25 22:19:46  michael
337changed cerr and cout messages for use with Singular
338Version for libfac-0.2.1
339
340*/
Note: See TracBrowser for help on using the repository browser.