Changeset 20c540 in git for libpolys/polys

Timestamp:

Oct 4, 2012, 7:47:33 PM (12 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

db347cb0bbec256ffb358817738b700f8da08253

Parents:

dc79bd7d1e331302a1fc20150a37e81890e6300a

git-author:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-10-04 19:47:33+02:00

git-committer:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-10-05 19:05:33+02:00

Message:

Preparing the removal of Frank's p_Monic/p_Gcd/p_ExtGcd from common use

chg: moved most of the functions (with helpers) into algext.cc and made them static

NOTE: p_PolyDiv stayed in p_polys.cc as it is used in convFactoryASingA
NOTE: p_ExtGcd also is made public via algext.h (needed elsewhere?)

Location:

libpolys/polys

Files:

• clapconv.cc (modified) (1 diff)
• ext_fields/algext.cc (modified) (1 diff)
• ext_fields/algext.h (modified) (1 diff)
• monomials/p_polys.cc (modified) (2 diffs)
• monomials/p_polys.h (modified) (1 diff)

libpolys/polys/clapconv.cc

@@ -290 +290 @@
   if (a!=NULL)
   {
-    if (r->cf->extRing->qideal->m[0]!=NULL)
-    {
-      poly l=r->cf->extRing->qideal->m[0];
-      if (p_GetExp(a,1,r->cf->extRing) >= p_GetExp(l,1,r->cf->extRing))
-        a = p_PolyDiv (a, l, FALSE, r->cf->extRing);
-    }
+    if( r->cf->extRing != NULL )
+      if (r->cf->extRing->qideal->m[0]!=NULL)
+      {
+        poly l=r->cf->extRing->qideal->m[0];
+        if (p_GetExp(a,1,r->cf->extRing) >= p_GetExp(l,1,r->cf->extRing))
+          a = p_PolyDiv (a, l, FALSE, r->cf->extRing); // ???
+      }
   }
   return a;

libpolys/polys/ext_fields/algext.cc

@@ -111 +111 @@
 
 static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param);
+
+
+/// returns NULL if p == NULL, otherwise makes p monic by dividing
+///   by its leading coefficient (only done if this is not already 1);
+///   this assumes that we are over a ground field so that division
+///   is well-defined;
+///   modifies p
+// void      p_Monic(poly p, const ring r);
+
+///   assumes that p and q are univariate polynomials in r,
+///   mentioning the same variable;
+///   assumes a global monomial ordering in r;
+///   assumes that not both p and q are NULL;
+///   returns the gcd of p and q;
+///   leaves p and q unmodified
+// poly      p_Gcd(const poly p, const poly q, const ring r);
+
+/* returns NULL if p == NULL, otherwise makes p monic by dividing
+   by its leading coefficient (only done if this is not already 1);
+   this assumes that we are over a ground field so that division
+   is well-defined;
+   modifies p */
+static inline void p_Monic(poly p, const ring r)
+{
+  if (p == NULL) return;
+  number n = n_Init(1, r->cf);
+  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
+  poly pp = p;
+  number lc = p_GetCoeff(p, r);
+  if (n_IsOne(lc, r->cf)) return;
+  number lcInverse = n_Invers(lc, r->cf);
+  p_SetCoeff(p, n, r);   // destroys old leading coefficient!
+  pIter(p);
+  while (p != NULL)
+  {
+    number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
+    n_Normalize(n,r->cf);
+    p_SetCoeff(p, n, r);   // destroys old leading coefficient!
+    pIter(p);
+  }
+  n_Delete(&lcInverse, r->cf);
+  p = pp;
+}
+
+/// see p_Gcd;
+///   additional assumption: deg(p) >= deg(q);
+///   must destroy p and q (unless one of them is returned)
+static inline poly p_GcdHelper(poly &p, poly &q, const ring r)
+{
+  while (q != NULL)
+  {
+    p_PolyDiv(p, q, FALSE, r);
+    // swap p and q:
+    poly& t = q;
+    q = p;
+    p = t;
+
+  }
+  return p;
+}
+
+/* assumes that p and q are univariate polynomials in r,
+   mentioning the same variable;
+   assumes a global monomial ordering in r;
+   assumes that not both p and q are NULL;
+   returns the gcd of p and q;
+   leaves p and q unmodified */
+static inline poly      p_Gcd(const poly p, const poly q, const ring r)
+{
+  assume((p != NULL) || (q != NULL));
+
+  poly a = p; poly b = q;
+  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
+  a = p_Copy(a, r); b = p_Copy(b, r);
+
+  /* We have to make p monic before we return it, so that if the
+     gcd is a unit in the ground field, we will actually return 1. */
+  a = p_GcdHelper(a, b, r);
+  p_Monic(a, r);
+  return a;
+}
+
+/* see p_ExtGcd;
+   additional assumption: deg(p) >= deg(q);
+   must destroy p and q (unless one of them is returned) */
+static inline poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor,
+                                  ring r)
+{
+  if (q == NULL)
+  {
+    qFactor = NULL;
+    pFactor = p_ISet(1, r);
+    p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
+    p_Monic(p, r);
+    return p;
+  }
+  else
+  {
+    poly pDivQ = p_PolyDiv(p, q, TRUE, r);
+    poly ppFactor = NULL; poly qqFactor = NULL;
+    poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
+    pFactor = ppFactor;
+    qFactor = p_Add_q(qqFactor,
+                      p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
+                      r);
+    return theGcd;
+  }
+}
+
+/* assumes that p and q are univariate polynomials in r,
+   mentioning the same variable;
+   assumes a global monomial ordering in r;
+   assumes that not both p and q are NULL;
+   returns the gcd of p and q;
+   moreover, afterwards pFactor and qFactor contain appropriate
+   factors such that gcd(p, q) = p * pFactor + q * qFactor;
+   leaves p and q unmodified */
+poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
+{
+  assume((p != NULL) || (q != NULL));
+  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
+  if (p_Deg(a, r) < p_Deg(b, r))
+    { a = q; b = p; aCorrespondsToP = FALSE; }
+  a = p_Copy(a, r); b = p_Copy(b, r);
+  poly aFactor = NULL; poly bFactor = NULL;
+  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
+  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
+  else                 { pFactor = bFactor; qFactor = aFactor; }
+  return theGcd;
+}
+
+
 
 #ifdef LDEBUG

libpolys/polys/ext_fields/algext.h

@@ -49 +49 @@
 int naIsParam(number, const coeffs);
 
+struct  spolyrec;
+typedef struct spolyrec    polyrec;
+typedef polyrec *          poly;
+
+/// assumes that p and q are univariate polynomials in r,
+///   mentioning the same variable;
+///   assumes a global monomial ordering in r;
+///   assumes that not both p and q are NULL;
+///   returns the gcd of p and q;
+///   moreover, afterwards pFactor and qFactor contain appropriate
+///   factors such that gcd(p, q) = p * pFactor + q * qFactor;
+///   leaves p and q unmodified
+poly      p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r);
+
+
 #endif
 /* ALGEXT_H */

libpolys/polys/monomials/p_polys.cc

@@ -1506 +1506 @@
        case, the method will be slightly faster.)
    leaves divisor unmodified */
-poly p_PolyDiv(poly &p, poly divisor, BOOLEAN needResult, ring r)
+poly      p_PolyDiv(poly &p, const poly divisor, const BOOLEAN needResult, const ring r)
 {
   assume(divisor != NULL);
@@ -1527 +1527 @@
   }
   return result;
-}
-
-/* returns NULL if p == NULL, otherwise makes p monic by dividing
-   by its leading coefficient (only done if this is not already 1);
-   this assumes that we are over a ground field so that division
-   is well-defined;
-   modifies p */
-void p_Monic(poly p, const ring r)
-{
-  if (p == NULL) return;
-  number n = n_Init(1, r->cf);
-  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
-  poly pp = p;
-  number lc = p_GetCoeff(p, r);
-  if (n_IsOne(lc, r->cf)) return;
-  number lcInverse = n_Invers(lc, r->cf);
-  p_SetCoeff(p, n, r);   // destroys old leading coefficient!
-  pIter(p);
-  while (p != NULL)
-  {
-    number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
-    n_Normalize(n,r->cf);
-    p_SetCoeff(p, n, r);   // destroys old leading coefficient!
-    pIter(p);
-  }
-  n_Delete(&lcInverse, r->cf);
-  p = pp;
-}
-
-/* see p_Gcd;
-   additional assumption: deg(p) >= deg(q);
-   must destroy p and q (unless one of them is returned) */
-poly p_GcdHelper(poly &p, poly &q, ring r)
-{
-  if (q == NULL)
-  {
-    /* We have to make p monic before we return it, so that if the
-       gcd is a unit in the ground field, we will actually return 1. */
-    p_Monic(p, r);
-    return p;
-  }
-  else
-  {
-    p_PolyDiv(p, q, FALSE, r);
-    return p_GcdHelper(q, p, r);
-  }
-}
-
-/* assumes that p and q are univariate polynomials in r,
-   mentioning the same variable;
-   assumes a global monomial ordering in r;
-   assumes that not both p and q are NULL;
-   returns the gcd of p and q;
-   leaves p and q unmodified */
-poly p_Gcd(poly p, poly q, ring r)
-{
-  assume((p != NULL) || (q != NULL));
-
-  poly a = p; poly b = q;
-  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
-  a = p_Copy(a, r); b = p_Copy(b, r);
-  return p_GcdHelper(a, b, r);
-}
-
-/* see p_ExtGcd;
-   additional assumption: deg(p) >= deg(q);
-   must destroy p and q (unless one of them is returned) */
-poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor,
-                    ring r)
-{
-  if (q == NULL)
-  {
-    qFactor = NULL;
-    pFactor = p_ISet(1, r);
-    p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
-    p_Monic(p, r);
-    return p;
-  }
-  else
-  {
-    poly pDivQ = p_PolyDiv(p, q, TRUE, r);
-    poly ppFactor = NULL; poly qqFactor = NULL;
-    poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
-    pFactor = ppFactor;
-    qFactor = p_Add_q(qqFactor,
-                      p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
-                      r);
-    return theGcd;
-  }
-}
-
-/* assumes that p and q are univariate polynomials in r,
-   mentioning the same variable;
-   assumes a global monomial ordering in r;
-   assumes that not both p and q are NULL;
-   returns the gcd of p and q;
-   moreover, afterwards pFactor and qFactor contain appropriate
-   factors such that gcd(p, q) = p * pFactor + q * qFactor;
-   leaves p and q unmodified */
-poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
-{
-  assume((p != NULL) || (q != NULL));
-  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
-  if (p_Deg(a, r) < p_Deg(b, r))
-  { a = q; b = p; aCorrespondsToP = FALSE; }
-  a = p_Copy(a, r); b = p_Copy(b, r);
-  poly aFactor = NULL; poly bFactor = NULL;
-  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
-  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
-  else                 { pFactor = bFactor; qFactor = aFactor; }
-  return theGcd;
 }
 

libpolys/polys/monomials/p_polys.h

@@ -1825 +1825 @@
 int       p_Weight(int c, const ring r);
 
-/* assumes that p and divisor are univariate polynomials in r,
-   mentioning the same variable;
-   assumes divisor != NULL;
-   p may be NULL;
-   assumes a global monomial ordering in r;
-   performs polynomial division of p by divisor:
-     - afterwards p contains the remainder of the division, i.e.,
-       p_before = result * divisor + p_afterwards;
-     - if needResult == TRUE, then the method computes and returns 'result',
-       otherwise NULL is returned (This parametrization can be used when
-       one is only interested in the remainder of the division. In this
-       case, the method will be slightly faster.)
-   leaves divisor unmodified */
-poly      p_PolyDiv(poly &p, poly divisor, BOOLEAN needResult, ring r);
-
-/* returns NULL if p == NULL, otherwise makes p monic by dividing
-   by its leading coefficient (only done if this is not already 1);
-   this assumes that we are over a ground field so that division
-   is well-defined;
-   modifies p */
-void      p_Monic(poly p, const ring r);
-
-/* assumes that p and q are univariate polynomials in r,
-   mentioning the same variable;
-   assumes a global monomial ordering in r;
-   assumes that not both p and q are NULL;
-   returns the gcd of p and q;
-   leaves p and q unmodified */
-poly      p_Gcd(poly p, poly q, ring r);
-
-/* assumes that p and q are univariate polynomials in r,
-   mentioning the same variable;
-   assumes a global monomial ordering in r;
-   assumes that not both p and q are NULL;
-   returns the gcd of p and q;
-   moreover, afterwards pFactor and qFactor contain appropriate
-   factors such that gcd(p, q) = p * pFactor + q * qFactor;
-   leaves p and q unmodified */
-poly      p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r);
+///   assumes that p and divisor are univariate polynomials in r,
+///   mentioning the same variable;
+///   assumes divisor != NULL;
+///   p may be NULL;
+///   assumes a global monomial ordering in r;
+///   performs polynomial division of p by divisor:
+///     - afterwards p contains the remainder of the division, i.e.,
+///       p_before = result * divisor + p_afterwards;
+///     - if needResult == TRUE, then the method computes and returns 'result',
+///       otherwise NULL is returned (This parametrization can be used when
+///       one is only interested in the remainder of the division. In this
+///       case, the method will be slightly faster.)
+///   leaves divisor unmodified
+poly      p_PolyDiv(poly &p, const poly divisor, const BOOLEAN needResult, const ring r);
 
 /* syszygy stuff */