source: git/libfac/factor/Truefactor.cc @ 8444b0

spielwiese
Last change on this file since 8444b0 was 8444b0, checked in by Hans Schönemann <hannes@…>, 23 years ago
*hannes: Dan's HAVE_SINGULAR_ERROR git-svn-id: file:///usr/local/Singular/svn/trunk@5574 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 13.6 KB
Line 
1/* Copyright 1996 Michael Messollen. All rights reserved. */
2///////////////////////////////////////////////////////////////////////////////
3// emacs edit mode for this file is -*- C++ -*-
4//static char * rcsid = "@(#) $Id: Truefactor.cc,v 1.9 2001-08-08 14:26:56 Singular Exp $";
5///////////////////////////////////////////////////////////////////////////////
6// Factory - Includes
7#include <factory.h>
8#ifndef NOSTREAMIO
9#include <iostream.h>
10#endif
11// Factor - Includes
12#include "tmpl_inst.h"
13#include "helpstuff.h"
14// some CC's need this:
15#include "Truefactor.h"
16
17#ifdef SINGULAR
18#define HAVE_SINGULAR_ERROR
19#endif
20
21#ifdef HAVE_SINGULAR_ERROR
22   extern "C" { void WerrorS(char *); }
23#endif
24
25#ifdef TRUEFACTORDEBUG
26#  define DEBUGOUTPUT
27#else
28#  undef DEBUGOUTPUT
29#endif
30
31#include "debug.h"
32#include "timing.h"
33
34int hasAlgVar(const CanonicalForm &f, const Variable &v)
35{
36  if (f.inBaseDomain()) return 0;
37  if (f.inCoeffDomain())
38  {
39    if (f.mvar()==v) return 1;
40    return hasAlgVar(f.LC(),v);
41  }
42  if (f.inPolyDomain())
43  {
44    if (hasAlgVar(f.LC(),v)) return 1;
45    for( CFIterator i=f; i.hasTerms(); i++)
46    {
47      if (hasAlgVar(i.coeff(),v)) return 1;
48    }
49  }
50  return 0;
51}
52
53int hasVar(const CanonicalForm &f, const Variable &v)
54{
55  if (f.inBaseDomain()) return 0;
56  if (f.inCoeffDomain())
57  {
58    if (f.mvar()==v) return 1;
59    return hasAlgVar(f.LC(),v);
60  }
61  if (f.inPolyDomain())
62  {
63    if (f.mvar()==v) return 1;
64    if (hasVar(f.LC(),v)) return 1;
65    for( CFIterator i=f; i.hasTerms(); i++)
66    {
67      if (hasVar(i.coeff(),v)) return 1;
68    }
69  }
70  return 0;
71}
72
73int hasAlgVar(const CanonicalForm &f)
74{
75  if (f.inBaseDomain()) return 0;
76  if (f.inCoeffDomain())
77  {
78    if (f.level()!=0)
79    {
80      //cout << "hasAlgVar:" << f.mvar() <<endl;
81      return 1;
82    }
83    return hasAlgVar(f.LC());
84  }
85  if (f.inPolyDomain())
86  {
87    if (hasAlgVar(f.LC())) return 1;
88    for( CFIterator i=f; i.hasTerms(); i++)
89    {
90      if (hasAlgVar(i.coeff())) return 1;
91    }
92  }
93  return 0;
94}
95
96///////////////////////////////////////////////////////////////
97// generate all different k-subsets of the set with n        //
98// elements and return them in returnlist.                   //
99///////////////////////////////////////////////////////////////
100static void
101combinat( int k, int n, List<IntList> & returnlist ){
102  ListIntList ListofLists;
103  IntList intermediate,intermediate2;
104  int value,j;
105
106  if ( k == 1 ){                     // k=1
107    for ( j=1; j<=n; j++)
108      returnlist.append( IntList(j) );
109  }
110  else{                              // k-1 --> k
111    combinat(k-1,n,returnlist);  // generate (k-1,n)
112    for ( ListIntListIterator l=returnlist; l.hasItem(); l++ ){
113      intermediate = l.getItem();
114      value = intermediate.getLast();
115      if ( value != n )
116        for ( j=value+1; j<=n; j++ ){
117          intermediate2 = intermediate; intermediate2.append(j);
118          ListofLists.append( intermediate2 );
119        }
120    }
121    returnlist = ListofLists;
122  }
123}
124
125///////////////////////////////////////////////////////////////
126// Return the CanonicalForm number nr in  Factorlist.        //
127///////////////////////////////////////////////////////////////
128static CanonicalForm
129getItemNr(int nr, const CFFList & Factorlist ){
130  ListIterator<CFFactor> i=Factorlist;
131  int Nr=nr;
132
133  for ( Nr=1; Nr<nr; Nr++ ) i++;
134  return i.getItem().factor();
135}
136
137///////////////////////////////////////////////////////////////
138// Generate all sets of m factors out of LiftedFactors list. //
139///////////////////////////////////////////////////////////////
140static CFFList
141combine( int m, const CFFList & LiftedFactors ){
142  CFFList result;
143  ListIntList CombinatList;
144  CanonicalForm intermediate;
145
146  combinat(m, LiftedFactors.length(), CombinatList);
147  for ( ListIntListIterator j=CombinatList ; j.hasItem(); j++ ){
148    intermediate=1;
149    for ( IntListIterator k=j.getItem(); k.hasItem(); k++ )
150      intermediate *= getItemNr(k.getItem(), LiftedFactors);
151    if (!hasAlgVar(intermediate))
152    result.append(CFFactor(intermediate,1));
153  }
154  return result;
155}
156
157///////////////////////////////////////////////////////////////
158// Remove element elem from the list L.                      //
159///////////////////////////////////////////////////////////////
160static CFFList
161Remove_from_List( const CFFList & L, const CanonicalForm & elem ){
162  CFFList Returnlist;
163
164  DEBOUTLN(cout, "Remove_from_List called with L= ",L);
165  DEBOUTLN(cout, "                     and  elem= ",elem);
166  for ( ListIterator<CFFactor> i = L ; i.hasItem(); i++)
167    if ( i.getItem().factor() != elem )
168      Returnlist.append( i.getItem() );
169
170  return Returnlist;
171}
172
173///////////////////////////////////////////////////////////////
174// Here we solve:          G= F mod ( P, S^h )               //
175///////////////////////////////////////////////////////////////
176static CanonicalForm
177Multmod_power( const CanonicalForm & F, const SFormList & Substituionlist, int h, int levelF){
178  CanonicalForm G;
179
180  G= change_poly(F, Substituionlist, 0);
181  G= mod_power(G, h, levelF);
182  G= change_poly(G, Substituionlist, 1);
183
184  return G;
185}
186
187///////////////////////////////////////////////////////////////
188// Determine the right degree for the list of combinations   //
189// of factors, i.e. delete any element from list CombL which //
190// degree in the main variable levelU exceeeds degU.         //
191///////////////////////////////////////////////////////////////
192static CFFList
193Rightdegree( const CFFList & CombL, int degU, int levelU ){
194  CFFList Returnlist;
195  CFFactor factor;
196
197  for ( ListIterator<CFFactor> i= CombL; i.hasItem(); i++ ){
198    factor= i.getItem();
199    if ( degree(factor.factor(), levelU) <= degU )
200      Returnlist.append(factor);
201  }
202
203  return Returnlist;
204}
205
206///////////////////////////////////////////////////////////////
207// We have properly lifted all the specialized factors. See  //
208// which one works.                                          //
209// We use the (modified) algorithm TRUEFACTORS given by      //
210// Paul S. Wang and Linda Preiss Rothschild:                 //
211// Factoring Multivariate Polynomials Over the Integers      //
212// Math. Comp. V29 Nr131 (July 1975) p. 935-950              //
213///////////////////////////////////////////////////////////////
214CFFList
215Truefactors( const CanonicalForm Ua, int levelU, const SFormList & SubstitutionList, const CFFList & PiList){
216  CanonicalForm U=Ua,a,b,Y;
217  CFFactor factor;
218  CFFList L,FAC,E_all;
219  int c,r = PiList.length(),degU, onemore,M, h = subvardegree(Ua,levelU) + 1;
220  ListIterator<CFFactor> i;
221
222  //cout << "SubstitutionList="<< SubstitutionList<<endl;
223// step 1: simply test the generated factors alone
224  for ( i= PiList; i.hasItem();i++){
225    factor = i.getItem();
226    //CanonicalForm test_f=change_poly(factor.factor(),SubstitutionList,0);
227    CanonicalForm test_f=factor.factor();
228    //cout <<"f:" << factor.factor() << " -> test_f:"<<test_f <<endl;
229    //cout << "           1:" << change_poly(factor.factor(),SubstitutionList,1) <<endl;
230    c= mydivremt(U,test_f,a,b);
231    if (  c  && b == U.genZero() && !hasAlgVar(test_f))
232    // factor.getFactor() divides U
233    {
234      //cout << " teilt:" << test_f <<endl;
235      U= a;
236      FAC.append(factor);
237    }
238    else{
239      //cout << " teilt nicht:" << test_f <<endl;
240      L.append(factor);
241    }
242  }
243  DEBOUTLN(cout,"Truefactors: (step1) L  = ", L);
244  DEBOUTLN(cout,"                     FAC= ", FAC);
245
246// step 2: Do we have to check combinations?
247  degU = L.length();
248  if ( degU == 0 ) // No elements: Return
249    return FAC;
250  else
251    if ( degU < 4 ){ // Less then four elements: no combinations possible
252      FAC.append( CFFactor(U,1) );
253      return FAC;
254    }
255    else {
256      M = 1; r = r - FAC.length(); degU = degree(U, levelU)/2;
257    }
258
259  DEBOUTLN(cout,"Truefactors: (step2) M   = ", M);
260  DEBOUTLN(cout,"                     r   = ", r);
261  DEBOUTLN(cout,"                     degU= ", degU);
262
263// Now do the real work!
264// Test all the combinations of possible factors.
265
266  onemore=1;
267// steps 3 to 6
268  while (1){
269    // step 3 iff onemore == 1
270    if ( onemore ) M+= 1;  else onemore = 1;
271    // step 4
272    if ( U == U.genOne() ) break; // Return FAC
273    if ( ( r == 1 ) || ( M >= ( r-1 ) ) || ( M > degU ) ) {
274      FAC.append( CFFactor(U,1) );
275      break; // Return FAC union {U}
276    }
277    // step 5
278    E_all = combine(M, L); // generate all combinations of M elements from L
279    DEBOUTLN(cout,"Truefactors: (step5) E_all= ", E_all);
280    // select combinations with the degree not to exceed degU:
281    E_all = Rightdegree( E_all, degU, levelU );
282    DEBOUTLN(cout,"Truefactors: (step5) E_all(Rightdegree)= ", E_all);
283    if ( E_all.length() == 0 ){
284      FAC.append( CFFactor(U,1) );
285      break; // Return FAC union {U}
286    }
287    for ( i=E_all; i.hasItem(); i++){
288      factor = i.getItem();
289      Y = Multmod_power( factor.factor(), SubstitutionList, h, levelU);
290      DEBOUTLN(cout, "Truefactors: (step6) Testing Y  = ", Y);
291      c = mydivremt(U,Y,a,b);
292      //      if (  c  && b == U.genZero()) { // Y divides U
293      if ( c && b.isZero() ){
294        DEBOUT(cout,"Truefactors: (step6): ",Y );
295        DEBOUTLN(cout, "  divides  ",U);
296        U = a;
297        FAC.append(Y); // Y is a real factor
298        onemore = 0;
299        degU = degree(U, levelU)/2; // new degU
300        // L = L \ {factor}
301        // Hier ist noch etwas faul; wir muessen (f=prod(f_i)) die f_i
302        // entfernen und nicht f!
303        L = Remove_from_List( L, factor.factor() );
304        r -= 1;
305        // delete from L any element with degree greater than degU
306        L = Rightdegree( L, degU, levelU );
307      }
308    }
309  }
310
311  return FAC;
312}
313
314///////////////////////////////////////////////////////////////
315// Check if poly f is in Fp (returns true) or in Fp(a)       //
316///////////////////////////////////////////////////////////////
317static bool
318is_in_Fp( const CanonicalForm & f ){
319  if ( f.inCoeffDomain() )
320    return f.inBaseDomain() ;
321  else {
322    CFIterator i=f;
323    bool ok=true;
324    while ( ok && i.hasTerms() ){
325      ok = is_in_Fp( i.coeff() );
326      i++ ;
327    }
328    return ok;
329  }
330}
331
332///////////////////////////////////////////////////////////////
333// We have factors which possibly lie in an extension of the //
334// base field. If one of these is not over the base field,   //
335// find its norm by (the theoretically handicapped method    //
336// of) multiplying by other elements.                        //
337///////////////////////////////////////////////////////////////
338CFFList
339TakeNorms(const CFFList & PiList){
340  CFFList CopyPossibleFactors, PossibleFactors, TrueFactors;
341  CFFListIterator i;
342  CFFactor Factor;
343  CanonicalForm intermediate;
344  ListIntList CombinatList;
345  ListIntListIterator j;
346  IntListIterator k;
347
348  // First check if the factors in PiList already lie in Fp-Domain
349  for ( i=PiList; i.hasItem(); i++ ){
350    Factor = i.getItem();
351    if ( is_in_Fp( Factor.factor() ) )
352      TrueFactors.append(Factor);
353    else
354      PossibleFactors.append(Factor);
355  }
356  // Now we have to check if combinations of the remaining factors
357  // (now in PossibleFactors) do lie in Fp-Domain
358  if ( PossibleFactors.length() > 0 ){ // there are (at least two) items
359    int n=2;
360    if ( PossibleFactors.length() < n ) { // a little check
361#ifdef HAVE_SINGULAR_ERROR
362      WerrorS("libfac: ERROR: TakeNorms less then two items remaining!");
363#else
364#ifndef NOSTREAMIO
365      cerr << "libfac: ERROR: TakeNorms less then two items remaining! "
366           << endl;
367#else
368      ;
369#endif
370#endif
371    }
372    while ( n < PossibleFactors.length() ){
373      // generate all combinations of n elements
374      combinat(n, PossibleFactors.length(), CombinatList);
375      for ( j=CombinatList ; j.hasItem(); j++ ){
376        intermediate=1;
377        for ( k=j.getItem(); k.hasItem(); k++ )
378          intermediate *= getItemNr( k.getItem(), PossibleFactors );
379        if ( is_in_Fp( intermediate ) ){
380          TrueFactors.append(intermediate); // found a true factor
381          CopyPossibleFactors=PossibleFactors; // save list
382          for ( k=j.getItem(); k.hasItem(); k++ )
383            //remove combined factors from PossibleFactors
384            PossibleFactors=Remove_from_List(PossibleFactors,
385                                getItemNr( k.getItem(), CopyPossibleFactors ));
386          n-=1; // look for the same number of combined factors:
387          break;
388        }
389        else {
390          //cout << "Schade!" << endl;
391        }
392        DEBOUT(cout, "Truefactor: Combined ", n);
393        DEBOUTLN(cout, " factors to: ", intermediate);
394      }
395      n += 1;
396    }
397  // All remaining factors in PossibleFactors multiplied
398  // should lie in Fp domain
399    if ( PossibleFactors.length() >=1 ){
400      for ( i=PossibleFactors; i.hasItem(); i++ )
401        intermediate *= i.getItem().factor();
402      // a last check:
403      if ( is_in_Fp(intermediate) ){
404        TrueFactors.append(CFFactor(intermediate,1));
405      }
406      else{
407#ifdef HAVE_SINGULAR_ERROR
408        WerrorS("libfac: TakeNorms: somethings wrong with remaining factors!");
409#else
410#ifndef NOSTREAMIO
411        cerr << "libfac: TakeNorms: somethings wrong with remaining factors!"
412             << endl;
413#endif
414#endif
415      }
416    }
417  }
418  return TrueFactors;
419}
420
421////////////////////////////////////////////////////////////
422/*
423$Log: not supported by cvs2svn $
424Revision 1.8  2001/08/08 11:59:13  Singular
425*hannes: Dan's NOSTREAMIO changes
426
427Revision 1.7  2001/08/06 08:32:54  Singular
428* hannes: code cleanup
429
430Revision 1.6  2001/06/27 13:58:06  Singular
431*hannes/GP: debug newfactoras, char_series, ...
432
433Revision 1.5  2001/06/21 14:57:06  Singular
434*hannes/GP: Factorize, newfactoras, ...
435
436Revision 1.4  1997/11/18 16:39:07  Singular
437* hannes: moved WerrorS from C++ to C
438     (Factor.cc MVMultiHensel.cc SqrFree.cc Truefactor.cc)
439
440Revision 1.3  1997/09/12 07:19:52  Singular
441* hannes/michael: libfac-0.3.0
442
443Revision 1.3  1997/04/25 22:39:11  michael
444changed cerr and cout messages for use with Singular
445Version for libfac-0.2.1
446
447*/
Note: See TracBrowser for help on using the repository browser.