Changeset 49f1f45 in git

Timestamp:

Nov 20, 2007, 11:08:40 AM (16 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

62f8cca6dc508c925bc4d657aea450dafba04fb9

Parents:

b1d37f6a1e89cd93b4ecab9f73e8d297d77180c0

Message:

*hannes: EZGCD for char p


git-svn-id: file:///usr/local/Singular/svn/trunk@10429 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

factory

Files:

• GNUmakefile.in (modified) (3 diffs)
• cf_defs.h (modified) (2 diffs)
• cf_gcd.cc (modified) (4 diffs)
• cf_gcd_charp.cc (modified) (16 diffs)
• cf_reval.h (modified) (2 diffs)
• cf_switches.cc (modified) (2 diffs)
• cf_switches.h (modified) (2 diffs)
• ffreval.cc (added)
• ffreval.h (added)
• winnt/factory.h (modified) (40 diffs)
• winnt/factoryconf.h (modified) (4 diffs)

factory/GNUmakefile.in

@@ -1 +1 @@
 # @configure_input@
-# $Id: GNUmakefile.in,v 1.52 2007-11-14 16:00:28 Singular Exp $
+# $Id: GNUmakefile.in,v 1.53 2007-11-20 10:08:02 Singular Exp $
 
 #
@@ -161 +161 @@
                 fac_util.cc \
                 ffops.cc \
+                ffreval.cc \
                 gf_tabutil.cc \
                 gfops.cc \
@@ -229 +230 @@
                 fac_util.h \
                 ffops.h \
+                ffreval.h \
                 ftmpl_array.h \
                 ftmpl_factor.h \

factory/cf_defs.h

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_defs.h,v 1.12 2007-10-31 08:40:52 Singular Exp $ */
+/* $Id: cf_defs.h,v 1.13 2007-11-20 10:08:02 Singular Exp $ */
 
 #ifndef INCL_CF_DEFS_H
@@ -34 +34 @@
 const int SW_FAC_QUADRATICLIFT = 5;
 const int SW_USE_EZGCD = 6;
-const int SW_USE_SPARSEMOD = 7;
-const int SW_USE_NTL=8;
-const int SW_USE_NTL_GCD_0=9;
-const int SW_USE_NTL_GCD_P=10;
-const int SW_USE_NTL_SORT=11;
-const int SW_USE_CHINREM_GCD=12;
-const int SW_USE_GCD_P=13;
+const int SW_USE_EZGCD_P = 7;
+const int SW_USE_SPARSEMOD = 8;
+const int SW_USE_NTL=9;
+const int SW_USE_NTL_GCD_0=10;
+const int SW_USE_NTL_GCD_P=11;
+const int SW_USE_NTL_SORT=12;
+const int SW_USE_CHINREM_GCD=13;
+const int SW_USE_GCD_P=14;
 //}}}
 

factory/cf_gcd.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_gcd.cc,v 1.54 2007-10-31 08:40:52 Singular Exp $ */
+/* $Id: cf_gcd.cc,v 1.55 2007-11-20 10:08:03 Singular Exp $ */
 
 #include <config.h>
@@ -15 +15 @@
 #include "fac_util.h"
 #include "ftmpl_functions.h"
+#include "ffreval.h"
 
 #ifdef HAVE_NTL
@@ -490 +491 @@
   if( gcd_avoid_mtaildegree ( fc, gc, d1 ) )
       return d1;
+  bool fc_isUnivariate=fc.isUnivariate();
   if ( getCharacteristic() != 0 )
   {
-    if (isOn(SW_USE_GCD_P))
+    if (isOn( SW_USE_EZGCD_P ) && (!fc_isUnivariate))
+    {
+      if ( pe == 1 )
+        fc = fin_ezgcd( fc, gc );
+      else if ( pe > 0 )// no variable at position 1
+      {
+        fc = replacevar( fc, Variable(pe), Variable(1) );
+        gc = replacevar( gc, Variable(pe), Variable(1) );
+        fc = replacevar( fin_ezgcd( fc, gc ), Variable(1), Variable(pe) );
+      }
+      else
+      {
+        pe = -pe;
+        fc = swapvar( fc, Variable(pe), Variable(1) );
+        gc = swapvar( gc, Variable(pe), Variable(1) );
+        fc = swapvar( fin_ezgcd( fc, gc ), Variable(1), Variable(pe) );
+      }
+    } 
+    else if (isOn(SW_USE_GCD_P))
     {
       fc=newGCD(fc,gc);
@@ -505 +525 @@
     }
   }
-  else if (!fc.isUnivariate())
+  else if (!fc_isUnivariate)
   {
     if ( isOn( SW_USE_EZGCD ) )

factory/cf_gcd_charp.cc

@@ -1 @@
-#include <factory.h>
+#include "config.h"
+#include <stdio.h>
 #ifndef NOSTREAMIO
-#include <stdio.h>
 #include <iostream.h>
 #endif
 #include <math.h>
+#include <cf_factory.h>
+#include <variable.h>
+#include <canonicalform.h>
+#include <cf_iter.h>
+#include <cf_random.h>
+#include <cf_algorithm.h>
+#include <cf_map.h>
 
 static CanonicalForm contentWRT(const CanonicalForm & F, const int lev);
-static int degWRT(const CanonicalForm & F, const int lev);
+static int degWRT(CanonicalForm F, const int lev);
 static CanonicalForm lcoefWRT( const CanonicalForm & F, const int lev);
 static CanonicalForm newtonInterp(CFList &alpha, CFList &u, const Variable & x);
@@ -20 +27 @@
 
 
-static CanonicalForm
+static CanonicalForm 
+contentWRT0(const CanonicalForm & F, const int lev, const int lev0)
+// Computes the content of a polynomial, considering the variables of level
+// larger than lev as as parameters.
+{
+  if(F.inBaseDomain() || (F.mvar().level() <= lev))
+  {
+    return(1);
+  }
+  else
+  {
+    if (F.isUnivariate())
+    {
+      return(F);
+    }
+    else
+    {
+      CanonicalForm pol;
+      CFIterator i = CFIterator(F);
+      CanonicalForm c = 0;
+      for(; i.hasTerms(); i++)
+      {
+        CanonicalForm cc=i.coeff();
+        if (cc.level() > lev0) 
+          pol = contentWRT0(cc, lev, lev0-1 );
+        else
+          pol = contentWRT(cc, lev -1);
+        c = gcd(c, pol);
+        if(c.isOne())
+        {
+          return c;
+        }
+      }
+      return c;
+    }
+  }
+}
+
+static CanonicalForm 
 contentWRT(const CanonicalForm & F, const int lev)
 // Computes the content of a polynomial, considering the variables of level
 // larger than lev as as parameters.
 {
+  //if (lev <0)
+  //  cout << "contentWRT:" <<F << " " << lev <<"\n";//printf("level=%d\n",lev);
   //int debug = 0;
   //if(debug == 1)cout << "contentWRT input - F:  " << F << " lev: " << lev << endl;
-  CanonicalForm pol;
-  if(F.mvar().level() <= lev){
+  if(F.inBaseDomain() || (F.mvar().level() <= lev))
+  {
     //if(debug == 1)cout << "output 1:" << F << endl;
     return(1);
-  } else {
-    if (F.isUnivariate() == 1){
+  }
+  else
+  {
+    if (F.isUnivariate())
+    {
       //if(debug == 1)cout << "output 2:" << F << endl;
       return(F);
-    } else {
-      CFIterator i = CFIterator(F, lev);
+    }
+    else
+    {
+      CanonicalForm pol;
+      CFIterator i = CFIterator(F);
       CanonicalForm c = 0;
-      for(; i.hasTerms(); i++){
-        pol = contentWRT(i.coeff(), lev - 1);
+      for(; i.hasTerms(); i++)
+      {
+        CanonicalForm cc=i.coeff();
+        if (cc.level() > lev) 
+          pol = contentWRT0(cc, lev, cc.level());
+        else
+          pol = contentWRT(i.coeff(), lev - 1);
         //if(debug == 1)cout << "c: " << c << " - pol : " << pol << endl;
         c = gcd(c, pol);
         //if(debug == 1)cout << "c temp:" << c << endl;
-        if(c.isOne()){
+        if(c.isOne())
+        {
           //if(debug == 1)cout << "output 3:" << c << endl;
           return c;
@@ -55 +114 @@
 
 // Degree of F wrt all variables of level smaller than or equal to lev
-static int
-degWRT(const CanonicalForm & F, const int lev)
+static int degWRT(CanonicalForm F, const int lev)
+{
+  int deg = F.degree(lev);
+  for(int i = lev; i >= 1; i--)
+  {
+    F = F.LC(i);
+    deg = deg + F.degree(i - 1);
+  }
+  return deg;
+}
+
+// Leading coefficient of F wrt all variables of level smaller than or equal to lev.
+static CanonicalForm lcoefWRT(const CanonicalForm & F, const int lev)
 {
   CanonicalForm FL;
   FL = F;
 
-  int deg = FL.degree(lev);
-  for(int i = lev; i >= 1; i--){
+  for(int i = lev; i >= 1; i--)
+  {
     FL = FL.LC(i);
-    deg = deg + FL.degree(i - 1);
-  }
-  return deg;
-}
-
-// Leading coefficient of F wrt all variables of level smaller than or equal to lev.
+  }
+  return FL;
+}
+
+
 static CanonicalForm
-lcoefWRT(const CanonicalForm & F, const int lev)
-{
-  CanonicalForm FL;
-  FL = F;
-  
-  for(int i = lev; i >= 1; i--){
-    FL = FL.LC(i);
-  }
-  return FL;
-}
-
-
-static CanonicalForm 
 newtonInterp(const CanonicalForm alpha, const CanonicalForm u, const CanonicalForm newtonPoly, const CanonicalForm oldInterPoly, const Variable & x)
 // Newton interpolation - Incremental algorithm.
 // Given a list of values alpha_i and a list of polynomials u_i, 1 <= i <= n,
-// computes the interpolation polynomial assuming that 
-// the polynomials in u are the results of evaluating the variabe x 
+// computes the interpolation polynomial assuming that
+// the polynomials in u are the results of evaluating the variabe x
 // of the unknown polynomial at the alpha values.
-// This incremental version receives only the values of alpha_n and u_n and 
+// This incremental version receives only the values of alpha_n and u_n and
 // the previous interpolation polynomial for points 1 <= i <= n-1, and computes
 // the polynomial interpolating in all the points.
@@ -97 +153 @@
   /*
   int debug = 0;
-  if(debug){
+  if(debug)
+  {
     cout << "newtonInterpIncremental input - variable " << x <<endl;
     cout << "newtonInterpIncremental input - alpha:" << alpha << " - u: " << u << endl;
@@ -114 +171 @@
 
 // Univariate GCD
-// Naive implementation of Euclidean Algorithm. 
+// Naive implementation of Euclidean Algorithm.
 // Should be used only for GCD of univariate polys over finite fields,
 // where there is no coefficient growth.
-static CanonicalForm
-simpleGCD(const CanonicalForm & A, const CanonicalForm & B)
+static CanonicalForm simpleGCD(const CanonicalForm & A, const CanonicalForm & B)
 {
   //int debug = 0;
   CanonicalForm P1, P2;
   /*
-  if(debug == 1){
+  if(debug == 1)
+  {
     cout << "simpleGCD input" << endl;
     cout << "A: " << A << endl;
@@ -129 +186 @@
   }
   */
-  if (A.degree() > B.degree()){
+  if (A.degree() > B.degree())
+  {
     P1 = A;
     P2 = B;
-  } else {
+  }
+  else
+  {
     P1 = B;
     P2 = A;
@@ -150 +210 @@
 
 
-static CanonicalForm
-GFPowDown(const CanonicalForm & A, int k)
+static CanonicalForm GFPowDown(const CanonicalForm & A, int k)
 // Replaces all coefficients of A in the ground field by their k-th roots.
-// It assumes that the k-th roots exist. 
+// It assumes that the k-th roots exist.
 // This procedure is used to map down a polynomial from an extension field.
 {
@@ -166 +225 @@
       //cout << "i: " << i << endl;
       //cout << "A[i]: " << A[i] << endl;
-      if(A[i].inBaseDomain()){
+      if(A[i].inBaseDomain())
+      {
         //cout << "GFPowDown - inBaseDomain" << endl;
         g = getGFGenerator();
@@ -175 +235 @@
           j++;
         }
-        if(j == fieldSize + 1)return(-1);
+        if(j == fieldSize + 1)  return(-1);
         result = result + power(g, j) * power(A.mvar(), i);
         //cout << "power(A[i], k): " << power(A[i], k) << endl;
         //cout << "result: " << result << endl;
-      } else {
-        //cout << "not inBaseDomain" << endl;  
+      }
+      else
+      {
+        //cout << "not inBaseDomain" << endl;
         result = result + GFPowDown(A[i], k) * power(A.mvar(), i);;
         // power(pol[i], k) * power(A.mvar(), i);
@@ -190 +252 @@
 }
 
-static CanonicalForm
-GFPowUp(const CanonicalForm & A, int k)
+static CanonicalForm GFPowUp(const CanonicalForm & A, int k)
 // Raises all coefficients of A in the ground field to the power k.
 // Used for maping a polynomial to an extension field.
 {
+  //cout << "A:" << A <<"\n";
   CanonicalForm result = 0;
   int i;
@@ -203 +265 @@
       //cout << "i: " << i << endl;
       //cout << "A[i]: " << A[i] << endl;
-      if(A[i].inBaseDomain()){
+      if(A[i].inBaseDomain())
+      {
         //cout << "inBaseDomain" << endl;
         result = result + power(A[i], k) * power(A.mvar(), i);
         //cout << "power(A[i], k): " << power(A[i], k) << endl;
         //cout << "result: " << result << endl;
-      } else {
-        //cout << "not inBaseDomain" << endl;  
+      }
+      else
+      {
+        //cout << "not inBaseDomain" << endl;
         result = result + GFPowUp(A[i], k) * power(A.mvar(), i);;
       }
     }
   }
+  //cout << "result:" << result <<"\n";
   return(result);
 }
 
-CanonicalForm
-GFMapUp(const CanonicalForm & A, int k)
+CanonicalForm GFMapUp(const CanonicalForm & A, int k)
 // Maps all coefficients of A to the base domain, asumming A is in GF(p^k).
+// The current base domain must be GF(p^j), with j a multiple of k.
+{
+  int p = getCharacteristic();
+  int expon = getGFDegree();
+  int extExp = expon / k;
+    // Assumes that we are using Conway polynomials
+  return(GFPowUp(A, extExp));
+}
+
+CanonicalForm GFMapDown(const CanonicalForm & A, int k)
+// Maps all coefficients of A from the base domain to GF(p^k).
 // The current base domain must be GF(p^j), with j a multiple of k.
 {
@@ -225 +301 @@
   int expon = getGFDegree();
   //cout << "Expon: " << expon << endl;
-  int extExp = (pow(p, expon) - 1) / (pow(p, k) - 1); // Assumes that we are using Conway polynomials
-  return(GFPowUp(A, extExp));
-}
-
-CanonicalForm
-GFMapDown(const CanonicalForm & A, int k)
-// Maps all coefficients of A from the base domain to GF(p^k).
-// The current base domain must be GF(p^j), with j a multiple of k.
-{
-  int p = getCharacteristic();
-  int expon = getGFDegree();
-  //cout << "Expon: " << expon << endl;
-  int extExp = (pow(p, expon) - 1) / (pow(p, k) - 1); // Assumes that we are using Conway polynomials
+  int extExp = expon / k;
+    // Assumes that we are using Conway polynomials
   return(GFPowDown(A, extExp));
 }
 
-CanonicalForm
-newGCD(CanonicalForm A, CanonicalForm B)
+CanonicalForm newGCD(CanonicalForm A, CanonicalForm B)
 // Computes the GCD of two polynomials over a prime field.
 // Based on Algorithm 7.2 from "Algorithms for Computer Algebra"
 {
-  /*
-  int debug = 0;
-  if(debug){
-    cout << "newGCD input" << endl;
-    cout << "A: " << A << endl;
-    cout << "B: " << B << endl;
-  }
-  */
-
-  if(A*1 == 0){
+  //int debug = 1;
+  //if(debug)
+  //{
+  //  cout << "newGCD input" << endl;
+  //  cout << "A: " << A << endl;
+  //  cout << "B: " << B << endl;
+  //}
+
+  if(A*1 == 0)
+  {
     //if(debug)cout << "A Zero!" << endl;
-    return(B);
-  }
-  if(B*1 == 0){
+    return(abs(B));
+  }
+  if(B*1 == 0)
+  {
     //if(debug)cout << "B Zero!" << endl;
-    return(A);
-  }
-
+    return(abs(A));
+  }
+  if (A.inBaseDomain()) return A.genOne();
+  if (B.inBaseDomain()) return B.genOne();
 
   CanonicalForm pol;
   int p = getCharacteristic();
-  int k = getGFDegree();
-  int fieldSize = pow(p, k);
-
-  /*
-  if(debug){
-    cout << "p: " << p << endl;
-    cout << "k: " << k << endl;
-    cout << "fieldSize: " << fieldSize << endl;
-    cout << "pow: " << pow(p, k) << endl;
-  }
-  */
-
+  int k = 1;
+  int fieldSize = p;
+  if (CFFactory::gettype() == GaloisFieldDomain)
+  {
+    k=getGFDegree();
+    fieldSize = pow(p, k);
+  }
+
+  //if(debug)
+  //{
+  //  cout << "p: " << p << endl;
+  //  cout << "k: " << k << endl;
+  //  cout << "fieldSize: " << fieldSize << endl;
+  //  cout << "pow: " << pow(p, k) << endl;
+  //}
+  
+  CFMap M,N;
+  compress(A,B,M,N);
+  A=M(A);
+  B=M(B);
   // Compute the main variable (the largest in A and B)
-  int mv;
-  Variable x;
-  x = A.mvar();
-  mv = x.level();
-  if(B.mvar().level() > mv) {
-    x = A.mvar();
+  Variable x = A.mvar();
+  int mv = x.level();
+  if(B.mvar().level() > mv)
+  {
+    x = B.mvar();
     mv = x.level();
   }
   //cout << "main variable " << x << endl << endl;
 
-    // Checks for univariate polynomial
+  // Checks for univariate polynomial
   if ( mv == 1 )
-    {
+  {
     // This call can be replaced by a faster GCD algorithm
     pol = simpleGCD(A, B); // Univariate GCD
     //cout << "newGCD output 1: " << pol << endl;
-    return pol;
+    return N(pol);
   }
 
   CanonicalForm b;
   CFArray bArray(0, fieldSize-1);    // Stores the bs already used
-  int sizebArray = 0;
+  int sizebArray;
 
   GFRandom genGF;
@@ -307 +380 @@
   int i, j;
   int used;
-  
+
   CanonicalForm c;    // gcd of the contents
   CanonicalForm C;
@@ -331 +404 @@
 
   CanonicalForm Ab, Bb, gb;  // A, B and g evaluated at b
-  
+
   int m;          // degree of the gcd of Ab and Bb
   int n = degWRT(Ap, mv - 1);
-  if(degWRT(Bp, mv - 1) < n){
+  if(degWRT(Bp, mv - 1) < n)
+  {
     n = degWRT(Bp, mv - 1);
   }
-  
+
   int fail = 0;
   int goodb;
   // The main loop
-  do{
-    // Searches for a good b. If there are no more possible b, the algorithm fails.
+  //cout << "start loop\n";
+  sizebArray = 0;
+  do
+  {
+    // Searches for a good b.
+    // If there are no more possible b, the algorithm fails.
     goodb = 0;
-    if(sizebArray == (fieldSize - 1)){
+    if(sizebArray >= fieldSize-1)
+    {
       // An extension field is needed.
       fail = 1;
-    } else {
-      do{
+    }
+    else
+    {
+      do
+      {
         // Searches for a new element of the ground field
-        do{
+        do
+        {
           // New element of the ground field
-          if(k > 1){
+          if(k > 1)
+          {
             b = genGF.generate();
-          } else {
+          }
+          else
+          {
             b = genFF.generate();
           }
+          //cout << "try(" << sizebArray << "):" << b;
           // Checks if this element was already used
           used = 0;
-          for(i = 0; i < sizebArray; i++){
+          for(i = 0; i < sizebArray; i++)
+          {
             // Multiplication by 1 is used to prevent a bug which
             // produces b=a^(q-1) as a random element.
-            if((bArray[i]*1) == (b*1)){
+            if((bArray[i]*1) == (b*1))
+            {
               used = 1;
+              //cout << " used\n";
             }
           }
           //if(debug==1)cout << "b: " << b << endl;
-        } while(used == 1);
+        }
+        while(used == 1);
         bArray[sizebArray] = b;
         sizebArray++;
         // b must not cancel the gcd of the leading coefficients
-        if(g(b, mv) != 0){
+        if(g(b, mv) != 0)
+        {
           goodb = 1;
+          //  cout << " good\n";
         }
         else
-        {
+        {
+          //  cout << " bad";
           if(sizebArray == fieldSize - 1)
-          {
+          {
             fail = 1;
+            //cout << " out of elems " << sizebArray << "tried";
           }
-        }
-      } while((goodb == 0) && (fail == 0));
-    }
-    if(fail == 1){
+          //cout << "\n";
+        }
+      }
+      while((goodb == 0) && (fail == 0));
+    }
+    if(fail)
+    {
       // Algorithm fails. An extension is needed.
-      
+
       // Computes the exponent of the ring extension so as to have enough interpolation points.
       int degMax;
-      if(totaldegree(A) > totaldegree(B)){
+      if(totaldegree(A) > totaldegree(B))
+      {
         degMax = totaldegree(A);
-      } else {
+      }
+      else
+      {
         degMax = totaldegree(B);
       }
-      int expon = 1;
-      while(pow(fieldSize, expon) < degMax){
+      int expon = 2; // expon <= will not extend the field
+      while(pow(fieldSize, expon) < degMax)
+      {
         expon++;
       }
       //if(debug)cout << "Not enough elements in the base field. An extension to " << p << "^" << k*expon << " is needed." << endl;
-      if(k > 1){
-        setCharacteristic(p, k * expon, 'b');
-        CanonicalForm P1 = GFMapUp(A, k);
-        CanonicalForm P2 = GFMapUp(B, k);
-        pol = newGCD(P1, P2);
-        pol = GFMapDown(pol, k);
-        setCharacteristic(p, k, 'a');
-        //if(debug)cout << "newGCD output 5: " << pol << endl;
-        return pol;
-      } else {
-        setCharacteristic(p, k * expon, 'a');
-        CanonicalForm P1 = A.mapinto();
-        CanonicalForm P2 = B.mapinto();
-        pol = newGCD(P1, P2);
-        setCharacteristic(p);
-        //if(debug)cout << "newGCD output 4: " << pol << endl;
-        return(pol);
-      }
-    } else {
+      if(k > 1)
+      {
+        if(pow(p,k * expon) < (1<<16))
+        {
+          setCharacteristic(p, k * expon, 'b');
+          CanonicalForm P1 = GFMapUp(A, k);
+          CanonicalForm P2 = GFMapUp(B, k);
+          //cout << "newGCD(mapped):" << P1 << " , " << P2 <<"\n";
+          pol = newGCD(P1, P2);
+          pol = GFMapDown(pol, k);
+          setCharacteristic(p, k, 'a');
+          //if(debug)cout << "newGCD output 5: " << pol << endl;
+          CanonicalForm temp=N(pol);
+          temp/=temp.lc();
+          return temp;
+        }
+        else
+        {
+          Off(SW_USE_GCD_P);
+          CanonicalForm temp=N(gcd( A, B));
+          On(SW_USE_GCD_P);
+          return temp;
+        } 
+      }
+      else
+      {
+        if(pow(p,k * expon) < (1<<16))
+        {
+          setCharacteristic(p, k * expon, 'a');
+          CanonicalForm P1 = A.mapinto();
+          CanonicalForm P2 = B.mapinto();
+          pol = newGCD(P1, P2);
+          setCharacteristic(p);
+          //if(debug)cout << "newGCD output 4: " << pol << endl;
+          CanonicalForm temp=N(pol);
+          temp/=temp.lc();
+          return temp;
+        }
+        else
+        {
+          Off(SW_USE_GCD_P);
+          CanonicalForm temp=N(gcd( A, B));
+          On(SW_USE_GCD_P);
+          return temp;
+        } 
+      }
+    }
+    else
+    {
       // Evaluate the polynomials in b
       Ab = Ap(b, mv);
@@ -429 +561 @@
       Cb /= Cblc;
       // Test for unlucky homomorphism
-      if(m < n){
+      if(m < n)
+      {
         // The degree decreased, we have to start it all over.
         H = Cb;
         newtonPoly = newtonPoly * (x - b);
         n = m;
-      } else if(m == n) {
+      }
+      else if(m == n)
+      {
         // Good b
         H = newtonInterp(b, Cb, newtonPoly, H, x);
         newtonPoly = newtonPoly * (x - b);
-        if(lcoefWRT(H, mv - 1) == g){
+        if(lcoefWRT(H, mv - 1) == g)
+        {
           C = H / contentWRT(H, mv - 1);  // primpart
-          if(fdivides(C, B) && fdivides(C, B))
-          {
+          if(fdivides(C, A) && fdivides(C, B))
+          {
             //if(debug)cout << "newGCD output 2: " << c * C<< endl;
-            return(c * C);
+            return N(c * C);
           }
-          else
-          {
+          else
+          {
             if(m == 0)
-            {
+            {
               //if(debug)cout << "newGCD output 3: " << c << endl;
-              return(c);
+              return N(c);
             }
           }
@@ -473 +609 @@
   cout << "setCharacteristic(2, 4, 'a')" << endl;
   setCharacteristic(2, 4, 'a');
-  
+
   int k = getGFDegree();
   int p = getCharacteristic();

factory/cf_reval.h

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_reval.h,v 1.5 2005-11-18 10:03:49 pohl Exp $ */
+/* $Id: cf_reval.h,v 1.6 2007-11-20 10:08:03 Singular Exp $ */
 
 #ifndef INCL_CF_REVAL_H
@@ -15 +15 @@
 class REvaluation : public Evaluation
 {
-private:
+protected: // neeeded in FFREvaluation
     CFRandom * gen;
 public:

factory/cf_switches.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_switches.cc,v 1.8 2007-09-26 09:17:40 Singular Exp $ */
+/* $Id: cf_switches.cc,v 1.9 2007-11-20 10:08:03 Singular Exp $ */
 
 //{{{ docu
@@ -36 +36 @@
 #endif
   On(SW_USE_EZGCD);
+  //On(SW_USE_EZGCD_P); // still testing
 }
 //}}}

factory/cf_switches.h

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_switches.h,v 1.11 2007-10-31 08:40:53 Singular Exp $ */
+/* $Id: cf_switches.h,v 1.12 2007-11-20 10:08:03 Singular Exp $ */
 
 #ifndef INCL_CF_SWITCHES_H
@@ -19 +19 @@
 //
 //}}}
-const int CFSwitchesMax = 14;
+const int CFSwitchesMax = 15;
 //}}}
 

factory/winnt/factory.h

@@ -1 @@
-/* ../factory/winnt/factory.h automatically generated by makeheader from ../factory/factory.template */
+/* winnt/factory.h automatically generated by makeheader from factory.template */
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: factory.h,v 1.5 1997-12-09 16:37:34 schmidt Exp $ */
+/* $Id: factory.h,v 1.6 2007-11-20 10:08:03 Singular Exp $ */
 
 #ifndef INCL_FACTORY_H
@@ -26 +26 @@
 
 #ifndef NOSTREAMIO
+#ifdef HAVE_IOSTREAM
+#include <iostream>
+#define OSTREAM std::ostream
+#define ISTREAM std::istream
+#elif defined(HAVE_IOSTREAM_H)
 #include <iostream.h>
+#define OSTREAM ostream
+#define ISTREAM istream
+#endif
 #endif /* ! NOSTREAMIO */
 
 #ifdef SINGULAR
-extern "C" {
+#include "cf_gmp.h"
+#else
 #include <gmp.h>
-}
 #endif /* SINGULAR */
 
 #ifdef macintosh
-#include <::templates:ftmpl_array.h>
-#include <::templates:ftmpl_factor.h>
-#include <::templates:ftmpl_list.h>
-#include <::templates:ftmpl_matrix.h>
+#include <:templates:ftmpl_array.h>
+#include <:templates:ftmpl_factor.h>
+#include <:templates:ftmpl_list.h>
+#include <:templates:ftmpl_matrix.h>
 #else
 #include <templates/ftmpl_array.h>
@@ -47 +55 @@
 #endif
 
-/* stuff included from ../factory/cf_globals.h */
+/* stuff included from ./cf_globals.h */
 
 
@@ -54 +62 @@
 
 
-/* stuff included from ../factory/cf_primes.h */
+/* stuff included from ./cf_primes.h */
 
 
@@ -70 +78 @@
 
 
-/* stuff included from ../factory/cf_defs.h */
+/* stuff included from ./cf_defs.h */
 
 
@@ -99 +107 @@
 const int SW_USE_EZGCD = 6;
 const int SW_USE_SPARSEMOD = 7;
-//}}}
-
-
-/* stuff included from ../factory/variable.h */
+const int SW_USE_NTL=8;
+const int SW_USE_NTL_GCD_0=9;
+const int SW_USE_NTL_GCD_P=10;
+const int SW_USE_NTL_SORT=11;
+const int SW_USE_CHINREM_GCD=12;
+const int SW_USE_GCD_P=13;
+//}}}
+
+
+/* stuff included from ./variable.h */
 
 
@@ -153 +167 @@
     }
 #ifndef NOSTREAMIO
-    friend ostream & operator << ( ostream & os, const Variable & v );
+    friend OSTREAM & operator << ( OSTREAM & os, const Variable & v );
 #endif /* NOSTREAMIO */
-    friend Variable rootOf( const CanonicalForm &, char name = '@' );
-};
+    friend void swap_levels();
+    friend Variable rootOf( const CanonicalForm &, char name );
+};
+Variable rootOf( const CanonicalForm &, char name = '@' );
 
 inline int level( const Variable & v ) { return v.level(); }
@@ -166 +182 @@
 char getDefaultExtName();
 
-
-/* stuff included from ../factory/canonicalform.h */
+int ExtensionLevel();
+
+
+/* stuff included from ./canonicalform.h */
+
+
+#undef CF_INLINE
+#define CF_INLINE
+#undef CF_NO_INLINE
+#define CF_NO_INLINE
+
+
+class InternalCF;
+
+inline int is_imm ( const InternalCF * const ptr )
+{
+    // returns 0 if ptr is not immediate       
+    return ( ((int)((long)ptr)) & 3 );
+}
 
 
@@ -173 +206 @@
 
 static int cf_is_initialized_now = initCanonicalForm();
-
-class InternalCF;
 
 //{{{ class CanonicalForm
@@ -183 +214 @@
 public:
     // constructors, destructors, selectors
-    CanonicalForm();
-    CanonicalForm( const CanonicalForm& );
-    CanonicalForm( InternalCF* );
-    CanonicalForm( const int );
-    CanonicalForm( const Variable & );
-    CanonicalForm( const Variable &, int );
-    CanonicalForm( const char * ); // use with caution - does only handle integers !!!
-
-    ~CanonicalForm();
+    CF_INLINE CanonicalForm();
+    CF_INLINE CanonicalForm( const CanonicalForm& );
+    CF_INLINE CanonicalForm( InternalCF* );
+    CF_INLINE CanonicalForm( const int );
+    CF_INLINE CanonicalForm( const Variable & );
+    CF_INLINE CanonicalForm( const Variable &, int );
+    CanonicalForm( const char *, const int base=10 ); // use with caution - does only handle integers !!!
+
+    CF_NO_INLINE ~CanonicalForm();
 
     InternalCF* getval() const; // use with caution !!!
@@ -198 +229 @@
 
     // predicates
-    bool isOne() const;
-    bool isZero() const;
-    bool isImm() const;
+    CF_NO_INLINE bool isOne() const;
+    CF_NO_INLINE bool isZero() const;
+    inline bool isImm() const { return is_imm( value ); };
 
     bool inZ() const;
@@ -215 +246 @@
     bool isFFinGF() const;
     bool isUnivariate() const;
+    bool isHomogeneous() const;
 
     // conversion functions
@@ -238 +270 @@
 
     // assignment operators
-    CanonicalForm& operator = ( const CanonicalForm& );
-    CanonicalForm& operator = ( const int );
+    CF_NO_INLINE CanonicalForm& operator = ( const CanonicalForm& );
+    CF_NO_INLINE CanonicalForm& operator = ( const int );
 
     CanonicalForm& operator += ( const CanonicalForm& );
@@ -269 +301 @@
 
     // arithmetic operators
-    friend CanonicalForm operator - ( const CanonicalForm& );
-
-    friend CanonicalForm operator + ( const CanonicalForm&, const CanonicalForm& );
-    friend CanonicalForm operator - ( const CanonicalForm&, const CanonicalForm& );
-    friend CanonicalForm operator * ( const CanonicalForm&, const CanonicalForm& );
-    friend CanonicalForm operator / ( const CanonicalForm&, const CanonicalForm& );
-    friend CanonicalForm operator % ( const CanonicalForm&, const CanonicalForm& );
-
-    friend CanonicalForm div ( const CanonicalForm&, const CanonicalForm& );
-    friend CanonicalForm mod ( const CanonicalForm&, const CanonicalForm& );
+    friend CF_NO_INLINE CanonicalForm operator - ( const CanonicalForm& );
 
     friend void divrem ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
     friend bool divremt ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
 
+    friend CanonicalForm bgcd ( const CanonicalForm &, const CanonicalForm & );
+    friend CanonicalForm bextgcd ( const CanonicalForm &, const CanonicalForm &, CanonicalForm &, CanonicalForm & );
+
+    // input/output
 #ifndef NOSTREAMIO
-    void print( ostream&, char * ) const;
-    friend ostream& operator << ( ostream&, const CanonicalForm& );
-    friend istream& operator >> ( istream&, CanonicalForm& );
+    void print( OSTREAM&, char * ) const;
+    void print( OSTREAM& ) const;
+    friend OSTREAM& operator << ( OSTREAM&, const CanonicalForm& );
+    friend ISTREAM& operator >> ( ISTREAM&, CanonicalForm& );
 #endif /* NOSTREAMIO */
 
@@ -298 +326 @@
 //}}}
 
-// some useful functions
+CF_INLINE CanonicalForm
+operator + ( const CanonicalForm&, const CanonicalForm& );
+
+CF_NO_INLINE CanonicalForm
+operator - ( const CanonicalForm&, const CanonicalForm& );
+
+CF_INLINE CanonicalForm
+operator * ( const CanonicalForm&, const CanonicalForm& );
+
+CF_NO_INLINE CanonicalForm
+operator / ( const CanonicalForm&, const CanonicalForm& );
+
+CF_NO_INLINE CanonicalForm
+operator % ( const CanonicalForm&, const CanonicalForm& );
+
+CF_NO_INLINE CanonicalForm
+div ( const CanonicalForm&, const CanonicalForm& );
+
+CF_NO_INLINE CanonicalForm
+mod ( const CanonicalForm&, const CanonicalForm& );
+
 
 //{{{ function declarations from canonicalform.cc
+CanonicalForm blcm ( const CanonicalForm & f, const CanonicalForm & g );
+
 CanonicalForm power ( const CanonicalForm & f, int n );
 
 CanonicalForm power ( const Variable & v, int n );
-
-bool divides ( const CanonicalForm & f, const CanonicalForm & g );
 //}}}
 
@@ -313 +361 @@
 CanonicalForm extgcd ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
 
-CanonicalForm iextgcd ( const CanonicalForm&, const CanonicalForm&, CanonicalForm&, CanonicalForm& );
-
 CanonicalForm lcm ( const CanonicalForm&, const CanonicalForm& );
 
@@ -324 +370 @@
 
 CanonicalForm icontent ( const CanonicalForm & f );
+
+CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x );
 //}}}
 
@@ -386 +434 @@
 level ( const CanonicalForm & f ) { return f.level(); }
 
-inline CanonicalForm
+inline Variable
 mvar ( const CanonicalForm & f ) { return f.mvar(); }
 
@@ -394 +442 @@
 inline CanonicalForm
 den ( const CanonicalForm & f ) { return f.den(); }
+
+inline int
+sign ( const CanonicalForm & a ) { return a.sign(); }
 
 inline CanonicalForm
@@ -418 +469 @@
 }
 
-inline CanonicalForm
-abs ( const CanonicalForm & f )
-{
-    if ( f < 0 )
-        return -f;
-    else
-        return f;
-}
-
 inline int
 headdegree ( const CanonicalForm & f ) { return totaldegree( head( f ) ); }
+
+
 //}}}
 
@@ -456 +500 @@
 
 
-/* stuff included from ../factory/cf_binom.h */
+/* stuff included from ./cf_binom.h */
 
 
@@ -462 +506 @@
 
 
-/* stuff included from ../factory/cf_algorithm.h */
+/* stuff included from ./cf_algorithm.h */
 
 
@@ -472 +516 @@
 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x );
 
-CanonicalForm common_den ( const CanonicalForm & f );
+CanonicalForm bCommonDen ( const CanonicalForm & f );
+
+bool fdivides ( const CanonicalForm & f, const CanonicalForm & g );
+
+CanonicalForm maxNorm ( const CanonicalForm & f );
+
+CanonicalForm euclideanNorm ( const CanonicalForm & f );
 //}}}
 
@@ -479 +529 @@
 
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew );
+
+CanonicalForm Farey ( const CanonicalForm & f, const CanonicalForm & q );
 //}}}
 
 //{{{ function declarations from cf_factor.cc
+bool isPurePoly(const CanonicalForm & f);
+
+bool isPurePoly_m(const CanonicalForm & f);
+
 CFFList factorize ( const CanonicalForm & f, bool issqrfree = false );
 
@@ -489 +545 @@
 
 bool isSqrFree ( const CanonicalForm & f );
+
+CanonicalForm homogenize( const CanonicalForm & f, const Variable & x);
+CanonicalForm homogenize( const CanonicalForm & f, const Variable & x,
+                                const Variable & v1, const Variable & v2);
+Variable get_max_degree_Variable(const CanonicalForm & f);
+CFList get_Terms( const CanonicalForm & f );
+void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
+
+
 //}}}
 
@@ -503 +568 @@
 //}}}
 
-
-/* stuff included from ../factory/cf_eval.h */
+//{{{ inline CanonicalForm abs ( const CanonicalForm & f )
+//{{{ docu
+//
+// abs() - return absolute value of `f'.
+//
+// The absolute value is defined in terms of the function
+// `sign()'.  If it reports negative sign for `f' than -`f' is
+// returned, otherwise `f'.
+//
+// This behaviour is most useful for integers and rationals.  But
+// it may be used to sign-normalize the leading coefficient of
+// arbitrary polynomials, too.
+//
+// Type info:
+// ----------
+// f: CurrentPP
+//
+//}}}
+inline CanonicalForm
+abs ( const CanonicalForm & f )
+{
+    // it is not only more general to use `sign()' instead of a
+    // direct comparison `f < 0', it is faster, too
+    if ( sign( f ) < 0 )
+        return -f;
+    else
+        return f;
+}
+//}}}
+
+
+/* stuff included from ./cf_eval.h */
 
 
@@ -525 +620 @@
     virtual void nextpoint();
 #ifndef NOSTREAMIO
-    friend ostream& operator<< ( ostream& s, const Evaluation &e );
+    friend OSTREAM& operator<< ( OSTREAM& s, const Evaluation &e );
 #endif /* NOSTREAMIO */
 };
 
 
-/* stuff included from ../factory/cf_generator.h */
+/* stuff included from ./cf_generator.h */
 
 
@@ -574 +669 @@
 };
 
-class AlgExtGenerator : public CFGenerator
+class AlgExtGenerator //??? : public CFGenerator
 {
 private:
     Variable algext;
-    CFGenerator **gens;
+    FFGenerator **gensf;
+    GFGenerator **gensg;
     int n;
     bool nomoreitems;
@@ -603 +699 @@
 
 
-/* stuff included from ../factory/cf_iter.h */
+/* stuff included from ./cf_iter.h */
+
+
+#undef CF_INLINE
+#define CF_INLINE
+#undef CF_NO_INLINE
+#define CF_NO_INLINE
 
 
@@ -625 +727 @@
     CFIterator& operator= ( const CanonicalForm& );
 
-    CFIterator& operator++ ();
-    CFIterator& operator++ ( int );
-    int hasTerms () const;
-    CanonicalForm coeff () const;
-    int exp () const;
-};
-
-
-/* stuff included from ../factory/cf_random.h */
+    CF_NO_INLINE CFIterator& operator++ ();
+    CF_NO_INLINE CFIterator& operator++ ( int );
+    CF_NO_INLINE int hasTerms () const;
+    CF_NO_INLINE CanonicalForm coeff () const;
+    CF_NO_INLINE int exp () const;
+};
+
+
+/* stuff included from ./cf_random.h */
 
 
@@ -700 +802 @@
 
 
-/* stuff included from ../factory/cf_irred.h */
+/* stuff included from ./cf_irred.h */
 
 
@@ -706 +808 @@
 
 
-/* stuff included from ../factory/fac_util.h */
+/* stuff included from ./fac_util.h */
 
 
@@ -736 +838 @@
 void divremainder( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & quot, CanonicalForm & rem, const modpk & pk );
 
-CanonicalForm maxCoeff( const CanonicalForm & f );
-
 bool Hensel ( const CanonicalForm & U, CFArray & G, const CFArray & lcG, const Evaluation & A, const modpk & bound, const Variable & x );
 
@@ -753 +853 @@
 
 
-/* stuff included from ../factory/cf_map.h */
+/* stuff included from ./cf_map.h */
 
 
@@ -789 +889 @@
     CanonicalForm subst () const { return S; }
 #ifndef NOSTREAMIO
-    friend ostream & operator << ( ostream & s, const MapPair & p );
+    void print( OSTREAM&) const;
+    friend OSTREAM & operator << ( OSTREAM & s, const MapPair & p );
 #endif /* NOSTREAMIO */
 };
@@ -827 +928 @@
   CanonicalForm operator () ( const CanonicalForm & f ) const;
 #ifndef NOSTREAMIO
-  friend ostream & operator << ( ostream & s, const CFMap & m );
+  friend OSTREAM & operator << ( OSTREAM & s, const CFMap & m );
 #endif /* NOSTREAMIO */
 };
@@ -837 +938 @@
 
 
-/* stuff included from ../factory/cf_reval.h */
+/* stuff included from ./cf_reval.h */
 
 
@@ -856 +957 @@
 #ifdef SINGULAR
 
-/* stuff included from ../factory/gfops.h */
+/* stuff included from ./gfops.h */
 
 
@@ -864 +965 @@
 
 
-/* stuff included from ../factory/singext.h */
+/* stuff included from ./singext.h */
 
 
@@ -871 +972 @@
 MP_INT gmp_denominator ( const CanonicalForm & f );
 
+int gf_value (const CanonicalForm & f );
+
 CanonicalForm make_cf ( const MP_INT & n );
 
 CanonicalForm make_cf ( const MP_INT & n, const MP_INT & d, bool normalize );
 
+CanonicalForm make_cf_from_gf ( const int z );
+
 
 #endif /* SINGULAR */
 
+#ifdef HAVE_BIFAC
+/* stuff included from ./bifac.h */
+
+
+CFFList AbsFactorize( const CanonicalForm  & a );
+
+class BIFAC
+{
+////////////////////////////////////////////////////////////////
+  public:
+////////////////////////////////////////////////////////////////  
+
+  // === KONST-/ DESTRUKTOREN ====
+  BIFAC         ( void );  // Konstruktor
+  virtual ~BIFAC( void );  // DESTRUKTOR
+
+  // === Funktionen =======
+  void     bifac(CanonicalForm f, bool absolute=true);
+  CFFList  getFactors( void ){ return  gl_RL; };
+
+
+////////////////////////////////////////////////////////////////
+ private:
+////////////////////////////////////////////////////////////////
+
+  // === Funktionen =======
+  void   passedTime();
+  void   biGanzMachen(  CanonicalForm & f );
+  void   biNormieren( CanonicalForm & f ) ;
+  void   convertResult(  CanonicalForm & f, int ch, int sw);
+  int    findCharacteristic(CanonicalForm f);
+//  void   matrix_drucken( CFMatrix M );
+  long int  anz_terme(  CanonicalForm & f );
+
+  CFList matrix2basis(CFMatrix A, int dim, int m, int n, CanonicalForm f);
+  CFList basisOfG(CanonicalForm f);
+  CFMatrix createA (CFList G, CanonicalForm f);
+  CanonicalForm  create_g    (CFList G);
+  CFList         createRg    (CFList G, CanonicalForm f);
+  CFList         createEg    (CFList G, CanonicalForm f);
+  CFList         createEgUni (CFList G, CanonicalForm f);
+
+  void     unifac(CanonicalForm f, int grad);
+  CanonicalForm RationalFactor (CanonicalForm phi, CanonicalForm f, \
+                                CanonicalForm fx, CanonicalForm g);
+  void   RationalFactorizationOnly (CFFList Phis, CanonicalForm f, CanonicalForm g);
+  CFList getAbsoluteFactors (CanonicalForm f1, CanonicalForm phi);
+  void   AbsoluteFactorization (CFFList Phis, CanonicalForm f, CanonicalForm g);
+  void   bifacSqrFree( CanonicalForm f );
+  void   bifacMain(CanonicalForm f);
+  
+
+  // === Variable =======
+  CFFList gl_RL;    // where to store the rational factorization
+  CFList  gl_AL;    // where to store the absolute factorization
+  bool   absolute;  // Compute an absolute factorization as well? 
+  int    exponent;  // 
+};
+
+#endif /* HAVE_BIFAC */
+
 #endif /* ! INCL_FACTORY_H */

factory/winnt/factoryconf.h

@@ -1 @@
-/* ../factory/winnt/factoryconf.h automatically generated by makeheader from ../factory/factoryconf.template */
+/* winnt/factoryconf.h automatically generated by makeheader from factoryconf.template */
 /* emacs edit mode for this file is -*- C -*- */
-/* $Id: factoryconf.h,v 1.5 1997-12-09 16:37:58 schmidt Exp $ */
+/* $Id: factoryconf.h,v 1.6 2007-11-20 10:08:03 Singular Exp $ */
 
 #ifndef INCL_FACTORYCONF_H
@@ -20 +20 @@
 /* }}} */
 
-/* stuff included from ../factory/winnt/config.h */
+/* stuff included from ./winnt/config.h */
 
 /* emacs edit mode for this file is -*- C -*- */
-/* $Id: factoryconf.h,v 1.5 1997-12-09 16:37:58 schmidt Exp $ */
+/* $Id: factoryconf.h,v 1.6 2007-11-20 10:08:03 Singular Exp $ */
 
 #ifndef INCL_CONFIG_H
@@ -102 +102 @@
 #endif /* ! INCL_CONFIG_H */
 
-/* stuff included from ../factory/assert.h */
+/* stuff included from ./assert.h */
 
 /* emacs edit mode for this file is -*- C -*- */
-/* $Id: factoryconf.h,v 1.5 1997-12-09 16:37:58 schmidt Exp $ */
+/* $Id: factoryconf.h,v 1.6 2007-11-20 10:08:03 Singular Exp $ */
 
 /* This is for compatibility with standard assert.h */
@@ -134 +134 @@
 /* }}} */
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 #include <stdio.h>
 #include <stdlib.h>
+
+#ifdef __cplusplus
+}
+#endif
 
 /* {{{ permanent macro definitions */