My Project  debian-1:4.1.1-p2+ds-4
Functions | Variables
cfGcdAlgExt.cc File Reference
#include "config.h"
#include <stdio.h>
#include <iostream>
#include "cf_assert.h"
#include "timing.h"
#include "templates/ftmpl_functions.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_iter.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfGcdAlgExt.h"
#include "cfUnivarGcd.h"
#include "cf_map.h"
#include "cf_generator.h"
#include "facMul.h"
#include "cfNTLzzpEXGCD.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (alg_content_p) TIMING_DEFINE_PRINT(alg_content) TIMING_DEFINE_PRINT(alg_compress) TIMING_DEFINE_PRINT(alg_termination) TIMING_DEFINE_PRINT(alg_termination_p) TIMING_DEFINE_PRINT(alg_reconstruction) TIMING_DEFINE_PRINT(alg_newton_p) TIMING_DEFINE_PRINT(alg_recursion_p) TIMING_DEFINE_PRINT(alg_gcd_p) TIMING_DEFINE_PRINT(alg_euclid_p) static int myCompress(const CanonicalForm &F
 compressing two polynomials F and G, M is used for compressing, N to reverse the compression More...
 
 for (int i=0;i<=n;i++) degsf[i]
 
 if (topLevel)
 
 DELETE_ARRAY (degsg)
 
void tryInvert (const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
 
static CanonicalForm trycontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
 
static CanonicalForm tryvcontent (const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
 
static CanonicalForm trycf_content (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
 
static CanonicalForm tryNewtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
 
void tryBrownGCD (const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
 modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true. More...
 
static CanonicalForm myicontent (const CanonicalForm &f, const CanonicalForm &c)
 
static CanonicalForm myicontent (const CanonicalForm &f)
 
CanonicalForm QGCD (const CanonicalForm &F, const CanonicalForm &G)
 gcd over Q(a) More...
 
int * leadDeg (const CanonicalForm &f, int *degs)
 
bool isLess (int *a, int *b, int lower, int upper)
 
bool isEqual (int *a, int *b, int lower, int upper)
 
CanonicalForm firstLC (const CanonicalForm &f)
 

Variables

const CanonicalFormG
 
const CanonicalForm CFMapM
 
const CanonicalForm CFMap CFMapN
 
const CanonicalForm CFMap CFMap bool topLevel
 
int * degsf = NEW_ARRAY(int,n + 1)
 
int * degsg = NEW_ARRAY(int,n + 1)
 
int both_non_zero = 0
 
int f_zero = 0
 
int g_zero = 0
 
int both_zero = 0
 
int Flevel =F.level()
 
int Glevel =G.level()
 
 else
 
 return
 

Function Documentation

◆ DELETE_ARRAY()

DELETE_ARRAY ( degsg  )

◆ firstLC()

CanonicalForm firstLC ( const CanonicalForm f)

Definition at line 956 of file cfGcdAlgExt.cc.

957 { // returns the leading coefficient (LC) of level <= 1
958  CanonicalForm ret = f;
959  while(ret.level() > 1)
960  ret = LC(ret);
961  return ret;
962 }

◆ for()

for ( int  i = 0;i<=n;i++)

Definition at line 65 of file cfEzgcd.cc.

66  {
67  if (degsf[i] != 0 && degsg[i] != 0)
68  {
69  both_non_zero++;
70  continue;
71  }
72  if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
73  {
74  f_zero++;
75  continue;
76  }
77  if (degsg[i] == 0 && degsf[i] && i <= F.level())
78  {
79  g_zero++;
80  continue;
81  }
82  }

◆ if()

if ( topLevel  )

Definition at line 75 of file cfGcdAlgExt.cc.

76  {
77  for (int i= 1; i <= n; i++)
78  {
79  if (degsf[i] != 0 && degsg[i] != 0)
80  {
81  both_non_zero++;
82  continue;
83  }
84  if (degsf[i] == 0 && degsg[i] != 0 && i <= Glevel)
85  {
86  f_zero++;
87  continue;
88  }
89  if (degsg[i] == 0 && degsf[i] && i <= Flevel)
90  {
91  g_zero++;
92  continue;
93  }
94  }
95 
96  if (both_non_zero == 0)
97  {
100  return 0;
101  }
102 
103  // map Variables which do not occur in both polynomials to higher levels
104  int k= 1;
105  int l= 1;
106  for (int i= 1; i <= n; i++)
107  {
108  if (degsf[i] != 0 && degsg[i] == 0 && i <= Flevel)
109  {
110  if (k + both_non_zero != i)
111  {
112  M.newpair (Variable (i), Variable (k + both_non_zero));
113  N.newpair (Variable (k + both_non_zero), Variable (i));
114  }
115  k++;
116  }
117  if (degsf[i] == 0 && degsg[i] != 0 && i <= Glevel)
118  {
119  if (l + g_zero + both_non_zero != i)
120  {
121  M.newpair (Variable (i), Variable (l + g_zero + both_non_zero));
122  N.newpair (Variable (l + g_zero + both_non_zero), Variable (i));
123  }
124  l++;
125  }
126  }
127 
128  // sort Variables x_{i} in increasing order of
129  // min(deg_{x_{i}}(f),deg_{x_{i}}(g))
130  int m= tmax (Flevel, Glevel);
131  int min_max_deg;
132  k= both_non_zero;
133  l= 0;
134  int i= 1;
135  while (k > 0)
136  {
137  if (degsf [i] != 0 && degsg [i] != 0)
138  min_max_deg= tmax (degsf[i], degsg[i]);
139  else
140  min_max_deg= 0;
141  while (min_max_deg == 0)
142  {
143  i++;
144  min_max_deg= tmax (degsf[i], degsg[i]);
145  if (degsf [i] != 0 && degsg [i] != 0)
146  min_max_deg= tmax (degsf[i], degsg[i]);
147  else
148  min_max_deg= 0;
149  }
150  for (int j= i + 1; j <= m; j++)
151  {
152  if (tmax (degsf[j],degsg[j]) <= min_max_deg && degsf[j] != 0 && degsg [j] != 0)
153  {
154  min_max_deg= tmax (degsf[j], degsg[j]);
155  l= j;
156  }
157  }
158  if (l != 0)
159  {
160  if (l != k)
161  {
162  M.newpair (Variable (l), Variable(k));
163  N.newpair (Variable (k), Variable(l));
164  degsf[l]= 0;
165  degsg[l]= 0;
166  l= 0;
167  }
168  else
169  {
170  degsf[l]= 0;
171  degsg[l]= 0;
172  l= 0;
173  }
174  }
175  else if (l == 0)
176  {
177  if (i != k)
178  {
179  M.newpair (Variable (i), Variable (k));
180  N.newpair (Variable (k), Variable (i));
181  degsf[i]= 0;
182  degsg[i]= 0;
183  }
184  else
185  {
186  degsf[i]= 0;
187  degsg[i]= 0;
188  }
189  i++;
190  }
191  k--;
192  }
193  }

◆ isEqual()

bool isEqual ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 947 of file cfGcdAlgExt.cc.

948 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
949  for(int i=lower; i<=upper; i++)
950  if(a[i] != b[i])
951  return false;
952  return true;
953 }

◆ isLess()

bool isLess ( int *  a,
int *  b,
int  lower,
int  upper 
)

Definition at line 936 of file cfGcdAlgExt.cc.

937 { // compares the degree vectors a,b on the specified part. Note: x(i+1) > x(i)
938  for(int i=upper; i>=lower; i--)
939  if(a[i] == b[i])
940  continue;
941  else
942  return a[i] < b[i];
943  return true;
944 }

◆ leadDeg()

int* leadDeg ( const CanonicalForm f,
int *  degs 
)

Definition at line 919 of file cfGcdAlgExt.cc.

920 { // leading degree vector w.r.t. lex. monomial order x(i+1) > x(i)
921  // if f is in a coeff domain, the zero pointer is returned
922  // 'a' should point to an array of sufficient size level(f)+1
923  if(f.inCoeffDomain())
924  return 0;
925  CanonicalForm tmp = f;
926  do
927  {
928  degs[tmp.level()] = tmp.degree();
929  tmp = LC(tmp);
930  }
931  while(!tmp.inCoeffDomain());
932  return degs;
933 }

◆ myicontent() [1/2]

static CanonicalForm myicontent ( const CanonicalForm f)
static

Definition at line 706 of file cfGcdAlgExt.cc.

707 {
708 #ifdef HAVE_NTL
709  return myicontent( f, 0 );
710 #else
711  return 1;
712 #endif
713 }

◆ myicontent() [2/2]

static CanonicalForm myicontent ( const CanonicalForm f,
const CanonicalForm c 
)
static

Definition at line 656 of file cfGcdAlgExt.cc.

657 {
658 #ifdef HAVE_NTL
659  if (f.isOne() || c.isOne())
660  return 1;
661  if ( f.inBaseDomain() && c.inBaseDomain())
662  {
663  if (c.isZero()) return abs(f);
664  return bgcd( f, c );
665  }
666  else if ( (f.inCoeffDomain() && c.inCoeffDomain()) ||
667  (f.inCoeffDomain() && c.inBaseDomain()) ||
668  (f.inBaseDomain() && c.inCoeffDomain()))
669  {
670  if (c.isZero()) return abs (f);
671 #ifdef HAVE_FLINT
672  fmpz_poly_t FLINTf, FLINTc;
673  convertFacCF2Fmpz_poly_t (FLINTf, f);
674  convertFacCF2Fmpz_poly_t (FLINTc, c);
675  fmpz_poly_gcd (FLINTc, FLINTc, FLINTf);
677  if (f.inCoeffDomain())
678  result= convertFmpz_poly_t2FacCF (FLINTc, f.mvar());
679  else
680  result= convertFmpz_poly_t2FacCF (FLINTc, c.mvar());
681  fmpz_poly_clear (FLINTc);
682  fmpz_poly_clear (FLINTf);
683  return result;
684 #else
685  ZZX NTLf= convertFacCF2NTLZZX (f);
686  ZZX NTLc= convertFacCF2NTLZZX (c);
687  NTLc= GCD (NTLc, NTLf);
688  if (f.inCoeffDomain())
689  return convertNTLZZX2CF(NTLc,f.mvar());
690  else
691  return convertNTLZZX2CF(NTLc,c.mvar());
692 #endif
693  }
694  else
695  {
696  CanonicalForm g = c;
697  for ( CFIterator i = f; i.hasTerms() && ! g.isOne(); i++ )
698  g = myicontent( i.coeff(), g );
699  return g;
700  }
701 #else
702  return 1;
703 #endif
704 }

◆ QGCD()

gcd over Q(a)

Definition at line 715 of file cfGcdAlgExt.cc.

716 { // f,g in Q(a)[x1,...,xn]
717  if(F.isZero())
718  {
719  if(G.isZero())
720  return G; // G is zero
721  if(G.inCoeffDomain())
722  return CanonicalForm(1);
723  CanonicalForm lcinv= 1/Lc (G);
724  return G*lcinv; // return monic G
725  }
726  if(G.isZero()) // F is non-zero
727  {
728  if(F.inCoeffDomain())
729  return CanonicalForm(1);
730  CanonicalForm lcinv= 1/Lc (F);
731  return F*lcinv; // return monic F
732  }
733  if(F.inCoeffDomain() || G.inCoeffDomain())
734  return CanonicalForm(1);
735  // here: both NOT inCoeffDomain
736  CanonicalForm f, g, tmp, M, q, D, Dp, cl, newq, mipo;
737  int p, i;
738  int *bound, *other; // degree vectors
739  bool fail;
740  bool off_rational=!isOn(SW_RATIONAL);
741  On( SW_RATIONAL ); // needed by bCommonDen
742  f = F * bCommonDen(F);
743  g = G * bCommonDen(G);
745  CanonicalForm contf= myicontent (f);
746  CanonicalForm contg= myicontent (g);
747  f /= contf;
748  g /= contg;
749  CanonicalForm gcdcfcg= myicontent (contf, contg);
750  TIMING_END_AND_PRINT (alg_content, "time for content in alg gcd: ")
751  Variable a, b;
752  if(hasFirstAlgVar(f,a))
753  {
754  if(hasFirstAlgVar(g,b))
755  {
756  if(b.level() > a.level())
757  a = b;
758  }
759  }
760  else
761  {
762  if(!hasFirstAlgVar(g,a))// both not in extension
763  {
764  Off( SW_RATIONAL );
765  Off( SW_USE_QGCD );
766  tmp = gcdcfcg*gcd( f, g );
767  On( SW_USE_QGCD );
768  if (off_rational) Off(SW_RATIONAL);
769  return tmp;
770  }
771  }
772  // here: a is the biggest alg. var in f and g AND some of f,g is in extension
773  setReduce(a,false); // do not reduce expressions modulo mipo
774  tmp = getMipo(a);
775  M = tmp * bCommonDen(tmp);
776  // here: f, g in Z[a][x1,...,xn], M in Z[a] not necessarily monic
777  Off( SW_RATIONAL ); // needed by mod
778  // calculate upper bound for degree vector of gcd
779  int mv = f.level(); i = g.level();
780  if(i > mv)
781  mv = i;
782  // here: mv is level of the largest variable in f, g
783  bound = new int[mv+1]; // 'bound' could be indexed from 0 to mv, but we will only use from 1 to mv
784  other = new int[mv+1];
785  for(int i=1; i<=mv; i++) // initialize 'bound', 'other' with zeros
786  bound[i] = other[i] = 0;
787  bound = leadDeg(f,bound); // 'bound' is set the leading degree vector of f
788  other = leadDeg(g,other);
789  for(int i=1; i<=mv; i++) // entry at i=0 not visited
790  if(other[i] < bound[i])
791  bound[i] = other[i];
792  // now 'bound' is the smaller vector
793  cl = lc(M) * lc(f) * lc(g);
794  q = 1;
795  D = 0;
796  CanonicalForm test= 0;
797  bool equal= false;
798  for( i=cf_getNumBigPrimes()-1; i>-1; i-- )
799  {
800  p = cf_getBigPrime(i);
801  if( mod( cl, p ).isZero() ) // skip lc-bad primes
802  continue;
803  fail = false;
805  mipo = mapinto(M);
806  mipo /= mipo.lc();
807  // here: mipo is monic
808  TIMING_START (alg_gcd_p)
809  tryBrownGCD( mapinto(f), mapinto(g), mipo, Dp, fail );
810  TIMING_END_AND_PRINT (alg_gcd_p, "time for alg gcd mod p: ")
811  if( fail ) // mipo splits in char p
812  {
814  continue;
815  }
816  if( Dp.inCoeffDomain() ) // early termination
817  {
818  tryInvert(Dp,mipo,tmp,fail); // check if zero divisor
820  if(fail)
821  continue;
822  setReduce(a,true);
823  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
824  delete[] other;
825  delete[] bound;
826  return gcdcfcg;
827  }
829  // here: Dp NOT inCoeffDomain
830  for(int i=1; i<=mv; i++)
831  other[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
832  other = leadDeg(Dp,other);
833 
834  if(isEqual(bound, other, 1, mv)) // equal
835  {
836  chineseRemainder( D, q, mapinto(Dp), p, tmp, newq );
837  // tmp = Dp mod p
838  // tmp = D mod q
839  // newq = p*q
840  q = newq;
841  if( D != tmp )
842  D = tmp;
843  On( SW_RATIONAL );
844  TIMING_START (alg_reconstruction)
845  tmp = Farey( D, q ); // Farey
846  tmp *= bCommonDen (tmp);
847  TIMING_END_AND_PRINT (alg_reconstruction,
848  "time for rational reconstruction in alg gcd: ")
849  setReduce(a,true); // reduce expressions modulo mipo
850  On( SW_RATIONAL ); // needed by fdivides
851  if (test != tmp)
852  test= tmp;
853  else
854  equal= true; // modular image did not add any new information
855  TIMING_START (alg_termination)
856 #ifdef HAVE_NTL
857 #ifdef HAVE_FLINT
858  if (equal && tmp.isUnivariate() && f.isUnivariate() && g.isUnivariate()
859  && f.level() == tmp.level() && tmp.level() == g.level())
860  {
861  CanonicalForm Q, R;
862  newtonDivrem (f, tmp, Q, R);
863  if (R.isZero())
864  {
865  newtonDivrem (g, tmp, Q, R);
866  if (R.isZero())
867  {
868  Off (SW_RATIONAL);
869  setReduce (a,true);
870  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
871  TIMING_END_AND_PRINT (alg_termination,
872  "time for successful termination test in alg gcd: ")
873  delete[] other;
874  delete[] bound;
875  return tmp*gcdcfcg;
876  }
877  }
878  }
879  else
880 #endif
881 #endif
882  if(equal && fdivides( tmp, f ) && fdivides( tmp, g )) // trial division
883  {
884  Off( SW_RATIONAL );
885  setReduce(a,true);
886  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
887  TIMING_END_AND_PRINT (alg_termination,
888  "time for successful termination test in alg gcd: ")
889  delete[] other;
890  delete[] bound;
891  return tmp*gcdcfcg;
892  }
893  TIMING_END_AND_PRINT (alg_termination,
894  "time for unsuccessful termination test in alg gcd: ")
895  Off( SW_RATIONAL );
896  setReduce(a,false); // do not reduce expressions modulo mipo
897  continue;
898  }
899  if( isLess(bound, other, 1, mv) ) // current prime unlucky
900  continue;
901  // here: isLess(other, bound, 1, mv) ) ==> all previous primes unlucky
902  q = p;
903  D = mapinto(Dp); // shortcut CRA // shortcut CRA
904  for(int i=1; i<=mv; i++) // tighten bound
905  bound[i] = other[i];
906  }
907  // hopefully, we never reach this point
908  setReduce(a,true);
909  delete[] other;
910  delete[] bound;
911  Off( SW_USE_QGCD );
912  D = gcdcfcg*gcd( f, g );
913  On( SW_USE_QGCD );
914  if (off_rational) Off(SW_RATIONAL); else On(SW_RATIONAL);
915  return D;
916 }

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( alg_content_p  ) const &

compressing two polynomials F and G, M is used for compressing, N to reverse the compression

◆ tryBrownGCD()

void tryBrownGCD ( const CanonicalForm F,
const CanonicalForm G,
const CanonicalForm M,
CanonicalForm result,
bool &  fail,
bool  topLevel 
)

modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail is set to true.

Definition at line 372 of file cfGcdAlgExt.cc.

373 { // assume F,G are multivariate polys over Z/p(a) for big prime p, M "univariate" polynomial in an algebraic variable
374  // M is assumed to be monic
375  if(F.isZero())
376  {
377  if(G.isZero())
378  {
379  result = G; // G is zero
380  return;
381  }
382  if(G.inCoeffDomain())
383  {
384  tryInvert(G,M,result,fail);
385  if(fail)
386  return;
387  result = 1;
388  return;
389  }
390  // try to make G monic modulo M
391  CanonicalForm inv;
392  tryInvert(Lc(G),M,inv,fail);
393  if(fail)
394  return;
395  result = inv*G;
396  result= reduce (result, M);
397  return;
398  }
399  if(G.isZero()) // F is non-zero
400  {
401  if(F.inCoeffDomain())
402  {
403  tryInvert(F,M,result,fail);
404  if(fail)
405  return;
406  result = 1;
407  return;
408  }
409  // try to make F monic modulo M
410  CanonicalForm inv;
411  tryInvert(Lc(F),M,inv,fail);
412  if(fail)
413  return;
414  result = inv*F;
415  result= reduce (result, M);
416  return;
417  }
418  // here: F,G both nonzero
419  if(F.inCoeffDomain())
420  {
421  tryInvert(F,M,result,fail);
422  if(fail)
423  return;
424  result = 1;
425  return;
426  }
427  if(G.inCoeffDomain())
428  {
429  tryInvert(G,M,result,fail);
430  if(fail)
431  return;
432  result = 1;
433  return;
434  }
435  TIMING_START (alg_compress)
436  CFMap MM,NN;
437  int lev= myCompress (F, G, MM, NN, topLevel);
438  if (lev == 0)
439  {
440  result= 1;
441  return;
442  }
443  CanonicalForm f=MM(F);
444  CanonicalForm g=MM(G);
445  TIMING_END_AND_PRINT (alg_compress, "time to compress in alg gcd: ")
446  // here: f,g are compressed
447  // compute largest variable in f or g (least one is Variable(1))
448  int mv = f.level();
449  if(g.level() > mv)
450  mv = g.level();
451  // here: mv is level of the largest variable in f, g
452  Variable v1= Variable (1);
453 #ifdef HAVE_NTL
454  Variable v= M.mvar();
456  {
458  zz_p::init (getCharacteristic());
459  }
460  zz_pX NTLMipo= convertFacCF2NTLzzpX (M);
461  zz_pE::init (NTLMipo);
462  zz_pEX NTLResult;
463  zz_pEX NTLF;
464  zz_pEX NTLG;
465 #endif
466  if(mv == 1) // f,g univariate
467  {
468  TIMING_START (alg_euclid_p)
469 #ifdef HAVE_NTL
470  NTLF= convertFacCF2NTLzz_pEX (f, NTLMipo);
471  NTLG= convertFacCF2NTLzz_pEX (g, NTLMipo);
472  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
473  if (fail)
474  return;
475  result= convertNTLzz_pEX2CF (NTLResult, f.mvar(), v);
476 #else
477  tryEuclid(f,g,M,result,fail);
478  if(fail)
479  return;
480 #endif
481  TIMING_END_AND_PRINT (alg_euclid_p, "time for euclidean alg mod p: ")
482  result= NN (reduce (result, M)); // do not forget to map back
483  return;
484  }
485  TIMING_START (alg_content_p)
486  // here: mv > 1
487  CanonicalForm cf = tryvcontent(f, Variable(2), M, fail); // cf is univariate poly in var(1)
488  if(fail)
489  return;
490  CanonicalForm cg = tryvcontent(g, Variable(2), M, fail);
491  if(fail)
492  return;
493  CanonicalForm c;
494 #ifdef HAVE_NTL
495  NTLF= convertFacCF2NTLzz_pEX (cf, NTLMipo);
496  NTLG= convertFacCF2NTLzz_pEX (cg, NTLMipo);
497  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
498  if (fail)
499  return;
500  c= convertNTLzz_pEX2CF (NTLResult, v1, v);
501 #else
502  tryEuclid(cf,cg,M,c,fail);
503  if(fail)
504  return;
505 #endif
506  // f /= cf
507  f.tryDiv (cf, M, fail);
508  if(fail)
509  return;
510  // g /= cg
511  g.tryDiv (cg, M, fail);
512  if(fail)
513  return;
514  TIMING_END_AND_PRINT (alg_content_p, "time for content in alg gcd mod p: ")
515  if(f.inCoeffDomain())
516  {
517  tryInvert(f,M,result,fail);
518  if(fail)
519  return;
520  result = NN(c);
521  return;
522  }
523  if(g.inCoeffDomain())
524  {
525  tryInvert(g,M,result,fail);
526  if(fail)
527  return;
528  result = NN(c);
529  return;
530  }
531  int *L = new int[mv+1]; // L is addressed by i from 2 to mv
532  int *N = new int[mv+1];
533  for(int i=2; i<=mv; i++)
534  L[i] = N[i] = 0;
535  L = leadDeg(f, L);
536  N = leadDeg(g, N);
537  CanonicalForm gamma;
538  TIMING_START (alg_euclid_p)
539 #ifdef HAVE_NTL
540  NTLF= convertFacCF2NTLzz_pEX (firstLC (f), NTLMipo);
541  NTLG= convertFacCF2NTLzz_pEX (firstLC (g), NTLMipo);
542  tryNTLGCD (NTLResult, NTLF, NTLG, fail);
543  if (fail)
544  return;
545  gamma= convertNTLzz_pEX2CF (NTLResult, v1, v);
546 #else
547  tryEuclid( firstLC(f), firstLC(g), M, gamma, fail );
548  if(fail)
549  return;
550 #endif
551  TIMING_END_AND_PRINT (alg_euclid_p, "time for gcd of lcs in alg mod p: ")
552  for(int i=2; i<=mv; i++) // entries at i=0,1 not visited
553  if(N[i] < L[i])
554  L[i] = N[i];
555  // L is now upper bound for degrees of gcd
556  int *dg_im = new int[mv+1]; // for the degree vector of the image we don't need any entry at i=1
557  for(int i=2; i<=mv; i++)
558  dg_im[i] = 0; // initialize
559  CanonicalForm gamma_image, m=1;
560  CanonicalForm gm=0;
561  CanonicalForm g_image, alpha, gnew;
562  FFGenerator gen = FFGenerator();
563  Variable x= Variable (1);
564  bool divides= true;
565  for(FFGenerator gen = FFGenerator(); gen.hasItems(); gen.next())
566  {
567  alpha = gen.item();
568  gamma_image = reduce(gamma(alpha, x),M); // plug in alpha for var(1)
569  if(gamma_image.isZero()) // skip lc-bad points var(1)-alpha
570  continue;
571  TIMING_START (alg_recursion_p)
572  tryBrownGCD( f(alpha, x), g(alpha, x), M, g_image, fail, false ); // recursive call with one var less
573  TIMING_END_AND_PRINT (alg_recursion_p,
574  "time for recursive calls in alg gcd mod p: ")
575  if(fail)
576  return;
577  g_image = reduce(g_image, M);
578  if(g_image.inCoeffDomain()) // early termination
579  {
580  tryInvert(g_image,M,result,fail);
581  if(fail)
582  return;
583  result = NN(c);
584  return;
585  }
586  for(int i=2; i<=mv; i++)
587  dg_im[i] = 0; // reset (this is necessary, because some entries may not be updated by call to leadDeg)
588  dg_im = leadDeg(g_image, dg_im); // dg_im cannot be NIL-pointer
589  if(isEqual(dg_im, L, 2, mv))
590  {
591  CanonicalForm inv;
592  tryInvert (firstLC (g_image), M, inv, fail);
593  if (fail)
594  return;
595  g_image *= inv;
596  g_image *= gamma_image; // multiply by multiple of image lc(gcd)
597  g_image= reduce (g_image, M);
598  TIMING_START (alg_newton_p)
599  gnew= tryNewtonInterp (alpha, g_image, m, gm, x, M, fail);
600  TIMING_END_AND_PRINT (alg_newton_p,
601  "time for Newton interpolation in alg gcd mod p: ")
602  // gnew = gm mod m
603  // gnew = g_image mod var(1)-alpha
604  // mnew = m * (var(1)-alpha)
605  if(fail)
606  return;
607  m *= (x - alpha);
608  if((firstLC(gnew) == gamma) || (gnew == gm)) // gnew did not change
609  {
610  TIMING_START (alg_termination_p)
611  cf = tryvcontent(gnew, Variable(2), M, fail);
612  if(fail)
613  return;
614  divides = true;
615  g_image= gnew;
616  g_image.tryDiv (cf, M, fail);
617  if(fail)
618  return;
619  divides= tryFdivides (g_image,f, M, fail); // trial division (f)
620  if(fail)
621  return;
622  if(divides)
623  {
624  bool divides2= tryFdivides (g_image,g, M, fail); // trial division (g)
625  if(fail)
626  return;
627  if(divides2)
628  {
629  result = NN(reduce (c*g_image, M));
630  TIMING_END_AND_PRINT (alg_termination_p,
631  "time for successful termination test in alg gcd mod p: ")
632  return;
633  }
634  }
635  TIMING_END_AND_PRINT (alg_termination_p,
636  "time for unsuccessful termination test in alg gcd mod p: ")
637  }
638  gm = gnew;
639  continue;
640  }
641 
642  if(isLess(L, dg_im, 2, mv)) // dg_im > L --> current point unlucky
643  continue;
644 
645  // here: isLess(dg_im, L, 2, mv) --> all previous points were unlucky
646  m = CanonicalForm(1); // reset
647  gm = 0; // reset
648  for(int i=2; i<=mv; i++) // tighten bound
649  L[i] = dg_im[i];
650  }
651  // we are out of evaluation points
652  fail = true;
653 }

◆ trycf_content()

static CanonicalForm trycf_content ( const CanonicalForm f,
const CanonicalForm g,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1067 of file cfGcdAlgExt.cc.

1068 { // as cf_content, but takes care of zero divisors
1069  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
1070  {
1071  CFIterator i = f;
1072  CanonicalForm tmp = g, result;
1073  while ( i.hasTerms() && ! tmp.isOne() && ! fail )
1074  {
1075  tryBrownGCD( i.coeff(), tmp, M, result, fail );
1076  tmp = result;
1077  i++;
1078  }
1079  return result;
1080  }
1081  return abs( f );
1082 }

◆ trycontent()

static CanonicalForm trycontent ( const CanonicalForm f,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1036 of file cfGcdAlgExt.cc.

1037 { // as 'content', but takes care of zero divisors
1038  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
1039  Variable y = f.mvar();
1040  if ( y == x )
1041  return trycf_content( f, 0, M, fail );
1042  if ( y < x )
1043  return f;
1044  return swapvar( trycontent( swapvar( f, y, x ), y, M, fail ), y, x );
1045 }

◆ tryInvert()

void tryInvert ( const CanonicalForm F,
const CanonicalForm M,
CanonicalForm inv,
bool &  fail 
)

Definition at line 221 of file cfGcdAlgExt.cc.

222 { // F, M are required to be "univariate" polynomials in an algebraic variable
223  // we try to invert F modulo M
224  if(F.inBaseDomain())
225  {
226  if(F.isZero())
227  {
228  fail = true;
229  return;
230  }
231  inv = 1/F;
232  return;
233  }
235  Variable a = M.mvar();
236  Variable x = Variable(1);
237  if(!extgcd( replacevar( F, a, x ), replacevar( M, a, x ), inv, b ).isOne())
238  fail = true;
239  else
240  inv = replacevar( inv, x, a ); // change back to alg var
241 }

◆ tryNewtonInterp()

static CanonicalForm tryNewtonInterp ( const CanonicalForm alpha,
const CanonicalForm u,
const CanonicalForm newtonPoly,
const CanonicalForm oldInterPoly,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
inlinestatic

Definition at line 357 of file cfGcdAlgExt.cc.

360 {
361  CanonicalForm interPoly;
362 
363  CanonicalForm inv;
364  tryInvert (newtonPoly (alpha, x), M, inv, fail);
365  if (fail)
366  return 0;
367 
368  interPoly= oldInterPoly+reduce ((u - oldInterPoly (alpha, x))*inv*newtonPoly, M);
369  return interPoly;
370 }

◆ tryvcontent()

static CanonicalForm tryvcontent ( const CanonicalForm f,
const Variable x,
const CanonicalForm M,
bool &  fail 
)
static

Definition at line 1048 of file cfGcdAlgExt.cc.

1049 { // as vcontent, but takes care of zero divisors
1050  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
1051  if ( f.mvar() <= x )
1052  return trycontent( f, x, M, fail );
1053  CFIterator i;
1054  CanonicalForm d = 0, e, ret;
1055  for ( i = f; i.hasTerms() && ! d.isOne() && ! fail; i++ )
1056  {
1057  e = tryvcontent( i.coeff(), x, M, fail );
1058  if(fail)
1059  break;
1060  tryBrownGCD( d, e, M, ret, fail );
1061  d = ret;
1062  }
1063  return d;
1064 }

Variable Documentation

◆ both_non_zero

int both_non_zero = 0

Definition at line 68 of file cfGcdAlgExt.cc.

◆ both_zero

int both_zero = 0

Definition at line 71 of file cfGcdAlgExt.cc.

◆ degsf

degsf = NEW_ARRAY(int,n + 1)

Definition at line 59 of file cfGcdAlgExt.cc.

◆ degsg

degsg = NEW_ARRAY(int,n + 1)

Definition at line 60 of file cfGcdAlgExt.cc.

◆ else

else
Initial value:
{
for (int i= 1; i <= n; i++)
{
if (degsf[i] == 0 && degsg[i] == 0)
{
continue;
}
else
{
if (both_zero != 0)
{
M.newpair (Variable (i), Variable (i - both_zero));
N.newpair (Variable (i - both_zero), Variable (i));
}
}
}
}

Definition at line 195 of file cfGcdAlgExt.cc.

◆ f_zero

int f_zero = 0

Definition at line 69 of file cfGcdAlgExt.cc.

◆ Flevel

int Flevel =F.level()

Definition at line 72 of file cfGcdAlgExt.cc.

◆ G

Definition at line 55 of file cfGcdAlgExt.cc.

◆ g_zero

int g_zero = 0

Definition at line 70 of file cfGcdAlgExt.cc.

◆ Glevel

int Glevel =G.level()

Definition at line 73 of file cfGcdAlgExt.cc.

◆ M

Definition at line 55 of file cfGcdAlgExt.cc.

◆ N

Definition at line 55 of file cfGcdAlgExt.cc.

◆ return

return

Definition at line 218 of file cfGcdAlgExt.cc.

◆ topLevel

const CanonicalForm CFMap CFMap bool topLevel
Initial value:
{
int n= tmax (F.level(), G.level())

Definition at line 57 of file cfGcdAlgExt.cc.

test
CanonicalForm test
Definition: cfModGcd.cc:4037
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
tryvcontent
static CanonicalForm tryvcontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:1048
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
N
const CanonicalForm CFMap CFMap & N
Definition: cfGcdAlgExt.cc:55
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
firstLC
CanonicalForm firstLC(const CanonicalForm &f)
Definition: cfGcdAlgExt.cc:956
k
int k
Definition: cfEzgcd.cc:92
CanonicalForm::tryDiv
CanonicalForm & tryDiv(const CanonicalForm &, const CanonicalForm &, bool &)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
Definition: canonicalform.cc:840
equal
bool equal
Definition: cfModGcd.cc:4067
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
if
if(topLevel)
Definition: cfGcdAlgExt.cc:75
result
return result
Definition: facAbsBiFact.cc:76
g_zero
int g_zero
Definition: cfGcdAlgExt.cc:70
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
degsg
int * degsg
Definition: cfGcdAlgExt.cc:60
cf
CanonicalForm cf
Definition: cfModGcd.cc:4024
CFMap
class CFMap
Definition: cf_map.h:84
isEqual
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:947
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition: cf_ops.cc:646
g
g
Definition: cfModGcd.cc:4031
else
else
Definition: cfGcdAlgExt.cc:195
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
trycontent
static CanonicalForm trycontent(const CanonicalForm &f, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:1036
tryFdivides
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
Definition: cf_algorithm.cc:454
tryNewtonInterp
static CanonicalForm tryNewtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:357
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:173
cl
cl
Definition: cfModGcd.cc:4041
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:77
degsg
int * degsg
Definition: cfEzgcd.cc:53
next
ListNode * next
Definition: janet.h:31
leadDeg
int * leadDeg(const CanonicalForm &f, int *degs)
Definition: cfGcdAlgExt.cc:919
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
gcdcfcg
CanonicalForm gcdcfcg
Definition: cfModGcd.cc:4042
tryBrownGCD
void tryBrownGCD(const CanonicalForm &F, const CanonicalForm &G, const CanonicalForm &M, CanonicalForm &result, bool &fail, bool topLevel)
modular gcd over F_p[x]/(M) for not necessarily irreducible M. If a zero divisor is encountered fail ...
Definition: cfGcdAlgExt.cc:372
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
TIMING_START
TIMING_START(fac_alg_resultant)
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
D
#define D(A)
Definition: gentable.cc:128
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
FFGenerator
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
cg
CanonicalForm cg
Definition: cfModGcd.cc:4024
for
for(int i=0;i<=n;i++) degsf[i]
Definition: cfEzgcd.cc:65
return
return
Definition: cfGcdAlgExt.cc:218
convertNTLzz_pEX2CF
CanonicalForm convertNTLzz_pEX2CF(const zz_pEX &f, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:1091
false
return false
Definition: cfModGcd.cc:84
chineseRemainder
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:52
myicontent
static CanonicalForm myicontent(const CanonicalForm &f, const CanonicalForm &c)
Definition: cfGcdAlgExt.cc:656
f_zero
int f_zero
Definition: cfEzgcd.cc:62
both_zero
int both_zero
Definition: cfGcdAlgExt.cc:71
Variable::level
int level() const
Definition: factory.h:134
DELETE_ARRAY
DELETE_ARRAY(degsg)
f_zero
int f_zero
Definition: cfGcdAlgExt.cc:69
g_zero
int g_zero
Definition: cfEzgcd.cc:63
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
newtonDivrem
void newtonDivrem(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &Q, CanonicalForm &R)
division with remainder of univariate polynomials over Q and Q(a) using Newton inversion,...
Definition: facMul.cc:342
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
both_non_zero
const CanonicalForm CFMap CFMap int & both_non_zero
Definition: cfEzgcd.cc:50
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
convertFmpz_poly_t2FacCF
CanonicalForm convertFmpz_poly_t2FacCF(const fmpz_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z to CanonicalForm
Definition: FLINTconvert.cc:101
trycf_content
static CanonicalForm trycf_content(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
Definition: cfGcdAlgExt.cc:1067
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
setReduce
void setReduce(const Variable &alpha, bool reduce)
Definition: variable.cc:238
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
Glevel
int Glevel
Definition: cfGcdAlgExt.cc:73
both_non_zero
int both_non_zero
Definition: cfGcdAlgExt.cc:68
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
degsf
int * degsf
Definition: cfEzgcd.cc:52
Variable
factory's class for variables
Definition: factory.h:117
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition: canonicalform.cc:381
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
topLevel
const CanonicalForm CFMap CFMap bool topLevel
Definition: cfGcdAlgExt.cc:57
M
const CanonicalForm CFMap & M
Definition: cfGcdAlgExt.cc:55
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition: canonicalform.h:348
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition: canonicalform.cc:304
m
int m
Definition: cfEzgcd.cc:121
l
int l
Definition: cfEzgcd.cc:93
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
Definition: canonicalform.cc:1589
R
#define R
Definition: sirandom.c:26
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
Flevel
int Flevel
Definition: cfGcdAlgExt.cc:72
replacevar
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
tryInvert
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
Farey
static number Farey(number p, number n, const coeffs)
Definition: flintcf_Q.cc:468
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
Q
#define Q
Definition: sirandom.c:25
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
tryNTLGCD
void tryNTLGCD(zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
compute the GCD x of a and b, fail is set to true if a zero divisor is encountered
Definition: cfNTLzzpEXGCD.cc:242
G
const CanonicalForm & G
Definition: cfGcdAlgExt.cc:55
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition: FLINTconvert.cc:74
G
const CanonicalForm & G
Definition: cfEzgcd.cc:48
myCompress
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition: cfModGcd.cc:93
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
degsf
int * degsf
Definition: cfGcdAlgExt.cc:59
alg_content
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
isLess
bool isLess(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:936