source: git/libfac/factor/Truefactor.cc @ 456842

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