Changeset 5038cd in git

Timestamp:

Nov 23, 2000, 6:34:13 PM (23 years ago)

Author:

Olaf Bachmann <obachman@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

85342036e5a4c81e1cace3f56c0dc8c1c1c655e0

Parents:

3d3d161d5697190f14e10031ef2c3cbb81a36c9f

Message:

* buckets in local case


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

Location:

Singular

Files:

• kInline.cc (modified) (11 diffs)
• kbuckets.cc (modified) (3 diffs)
• kspoly.cc (modified) (6 diffs)
• kstd1.cc (modified) (41 diffs)
• kstd2.cc (modified) (17 diffs)
• kutil.cc (modified) (82 diffs)
• kutil.h (modified) (10 diffs)
• pInline0.h (modified) (4 diffs)
• pInline2.h (modified) (7 diffs)
• p_Minus_mm_Mult_qq__Template.cc (modified) (4 diffs)
• p_Mult_q.cc (modified) (2 diffs)
• p_Procs.h (modified) (2 diffs)
• p_polys.cc (modified) (8 diffs)
• p_polys.h (modified) (5 diffs)
• polys.h (modified) (3 diffs)
• polys1.cc (modified) (2 diffs)
• pp_Mult_mm__Template.cc (modified) (5 diffs)
• ring.cc (modified) (4 diffs)

Singular/kInline.cc

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: kInline.cc,v 1.16 2000-11-16 09:54:49 obachman Exp $
+ *  Version: $Id: kInline.cc,v 1.17 2000-11-23 17:34:07 obachman Exp $
  *******************************************************************/
 #ifndef KINLINE_CC
@@ -37 +37 @@
   tailBin = omGetStickyBinOfBin(currRing->PolyBin);
 #endif
+  pOrigFDeg = pFDeg;
+  pOrigLDeg = pLDeg;
 }
 
@@ -49 +51 @@
   if (currRing != tailRing)
     rKillModifiedRing(tailRing);
+  pLDeg = pOrigLDeg;
+  pFDeg = pOrigFDeg;
 }
 
@@ -284 +288 @@
     p = p_LmDeleteAndNext(p, currRing);
   }
+  is_normalized = FALSE;
 }
 
@@ -436 +441 @@
 }
 
-KINLINE void sLObject::SetLmTail(poly lm, poly p_tail, int p_Length, int use_bucket, ring tailRing)
-{
+KINLINE void sLObject::PrepareRed(BOOLEAN use_bucket)
+{
+  if (bucket == NULL)
+  {
+    int l = GetpLength();
+    if (use_bucket && l > 1)
+    {
+      poly tp = GetLmTailRing();
+      bucket = kBucketCreate(tailRing);
+      kBucketInit(bucket, pNext(tp), l-1);
+      pNext(tp) = NULL;
+      if (p != NULL) pNext(p) = NULL;
+      pLength = 0;
+    }
+  }
+}
+
+KINLINE void sLObject::SetLmTail(poly lm, poly p_tail, int p_Length, int use_bucket, ring tailRing, poly _last)
+{
+  
   Set(lm, tailRing);
   if (use_bucket)
@@ -449 +472 @@
   {
     pNext(lm) = p_tail;
-    pLength = p_Length;
-  }
+    pLength = p_Length + 1;
+    last = _last;
+  }
+  
 }
 
@@ -478 +503 @@
     poly _p = (t_p != NULL ? t_p : p);
     assume(_p != NULL);
-    int dummy;
+    int shorter;
     pNext(_p) = tailRing->p_Procs->p_Minus_mm_Mult_qq(pNext(_p), m, q, 
-                                                      dummy,spNoether,tailRing);
+                                                      shorter,spNoether,
+                                                      tailRing, last);
+    pLength += lq - shorter;
   }
 }
@@ -493 +520 @@
     {
       kBucketDestroy(&bucket);
+      p = t_p = NULL;
       return;
     }
     Set(_p, tailRing);
   }
-}
-
-KINLINE void sLObject::CanonicalizeP()
+  else
+  {
+    pLength--;
+  }
+}
+
+KINLINE poly sLObject::CanonicalizeP()
 {
   kTest_L(this);
+  int i = -1;
 
   if (bucket != NULL)
-    kBucketCanonicalize(bucket);
+    i = kBucketCanonicalize(bucket);
 
   if (p == NULL)
     p = k_LmInit_tailRing_2_currRing(t_p, tailRing);
+
+  if (i >= 0) pNext(p) = bucket->buckets[i];
+  return p;
 }
 
@@ -554 +590 @@
 }
 
+KINLINE void sLObject::Copy()
+{
+  if (bucket != NULL)
+  {
+    int i = kBucketCanonicalize(bucket);
+    kBucket_pt new_bucket = kBucketCreate(tailRing);
+    kBucketInit(new_bucket, 
+                p_Copy(bucket->buckets[i], tailRing), 
+                bucket->buckets_length[i]);
+    bucket = new_bucket;
+    if (t_p != NULL) pNext(t_p) = NULL;
+    if (p != NULL) pNext(p) = NULL;
+  }
+  TObject::Copy();
+  last = NULL;
+}
+
+KINLINE poly sLObject::CopyGetP()
+{
+  last = NULL;
+  if (bucket != NULL)
+  {
+    int i = kBucketCanonicalize(bucket);
+    poly bp = p_Copy(bucket->buckets[i], tailRing);
+    pLength = bucket->buckets_length[i] + 1;
+    if (bp != NULL)
+    {
+      assume(t_p != NULL || p != NULL);
+      if (t_p != NULL) pNext(t_p) = bp;
+      else pNext(p) = bp;
+    }
+    bucket = NULL;
+  }
+  return sLObject::GetP();
+}
+
+
 KINLINE long sLObject::pLDeg()
 {
@@ -569 +642 @@
     return ::pLDeg(tp, &length, tailRing);
 }
+KINLINE long sLObject::pLDeg(BOOLEAN deg_last)
+{
+  if (! deg_last || bucket != NULL) return sLObject::pLDeg();
+  
+  if (last == NULL || pLength == 0) 
+    last = pLast((t_p != NULL ? t_p : p), pLength);
+#ifdef HAVE_ASSUME
+  long fdeg;
+  fdeg = ::pLDeg(GetLmTailRing(), &length, tailRing);
+  assume (pLength == length && fdeg == ::pFDeg(last, tailRing));
+  return fdeg;
+#else
+  length = pLength;
+  return ::pFDeg(last, tailRing);
+#endif
+}
+
 KINLINE long sLObject::SetDegStuffReturnLDeg()
 {
@@ -576 +666 @@
   return d;
 }
-KINLINE long sLObject::SetLength()
-{
-  // this can be improved
-  this->pLDeg();
+KINLINE long sLObject::SetDegStuffReturnLDeg(BOOLEAN use_last)
+{
+  FDeg = this->pFDeg();
+  long d = this->pLDeg(use_last);
+  ecart = d - FDeg;
+  return d;
+}
+KINLINE int sLObject::GetpLength()
+{
+  if (bucket == NULL) 
+    return sTObject::GetpLength();
+  int i = kBucketCanonicalize(bucket);
+  return bucket->buckets_length[i] + 1;
+}
+KINLINE int sLObject::SetLength(BOOLEAN length_pLength)
+{
+  if (length_pLength) 
+    length = this->GetpLength();
+  else
+    this->pLDeg();
   return length;
 }

Singular/kbuckets.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kbuckets.cc,v 1.19 2000-10-26 06:39:26 obachman Exp $ */
+/* $Id: kbuckets.cc,v 1.20 2000-11-23 17:34:08 obachman Exp $ */
 
 #include "mod2.h"
@@ -445 +445 @@
   int i, l1;
   poly p1 = p;
+  poly last;
 
   if (*l <= 0)
@@ -482 +483 @@
   else
   {
+    int shorter = 0;
     pSetCoeff0(m, nNeg(pGetCoeff(m)));
-    p1 = bucket->bucket_ring->p_Procs->pp_Mult_mm(p1, m, spNoether, bucket->bucket_ring);
+    p1 = bucket->bucket_ring->p_Procs->pp_Mult_mm(p1, m, shorter, spNoether, bucket->bucket_ring, last);
     pSetCoeff0(m, nNeg(pGetCoeff(m)));
+    l1 -= shorter;
   }
 

Singular/kspoly.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kspoly.cc,v 1.19 2000-11-14 16:04:53 obachman Exp $ */
+/* $Id: kspoly.cc,v 1.20 2000-11-23 17:34:08 obachman Exp $ */
 /*
 *  ABSTRACT -  Routines for Spoly creation and reductions
@@ -101 +101 @@
   
   // and finally, 
-  PR->Tail_Minus_mm_Mult_qq(lm, t2, 
-                            (PR->bucket != NULL ? PW->GetpLength() - 1 : 0), 
-                            spNoether);
+  PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
   PR->LmDeleteAndIter();
   return ret;
@@ -121 +119 @@
   poly p1 = Pair->p1;
   poly p2 = Pair->p2;
+  poly last;
   Pair->tailRing = tailRing;
   
@@ -131 +130 @@
   int co=0, ct = ksCheckCoeff(&lc1, &lc2);
 
-  int l1=0, l2=0;
+  int l1=0, l2=0, shorter=0;
   
   if (p_GetComp(p1, currRing)!=p_GetComp(p2, currRing))
@@ -155 +154 @@
   pSetCoeff0(m2, lc1);  // and now, m1 * LT(p1) == m2 * LT(p2)
 
-  if (use_buckets && R != NULL)
-  {
-    l1 = (R[Pair->i_r1])->pLength - 1;
-    l2 = (R[Pair->i_r2])->pLength - 1;
+  if (R != NULL)
+  {
+    l1 = (R[Pair->i_r1])->GetpLength() - 1;
+    l2 = (R[Pair->i_r2])->GetpLength() - 1;
   }
   
   // get m2 * a2
-  a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, spNoether, tailRing);
-  Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
+  a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, shorter,spNoether,tailRing,last);
+  Pair->SetLmTail(m2, a2, l2-shorter, use_buckets, tailRing, last);
 
   // get m2*a2 - m1*a1
@@ -208 +207 @@
   number coef;
 
+  pAssume(!pHaveCommonMonoms(Red.p, With.p));
   ret = ksReducePoly(&Red, &With, spNoether, &coef);
   

Singular/kstd1.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kstd1.cc,v 1.65 2000-11-22 17:35:33 Singular Exp $ */
+/* $Id: kstd1.cc,v 1.66 2000-11-23 17:34:08 obachman Exp $ */
 /*
 * ABSTRACT:
@@ -77 +77 @@
 //static BOOLEAN posInLOldFlag;
            /*FALSE, if posInL == posInL10*/
-
-/*0 implementation*/
-
-/*2
-*p is a polynomial in the set s;
-*recompute p and its ecart e with respect to the new noether
-*(cut every monomial of pNext(p) above noether)
-*/
-void deleteHCs (TObject* p,kStrategy strat)
-{
-  poly p1;
-  int o;
-
-  if (strat->kHEdgeFound)
-  {
-    p1 = (*p).p;
-    o = pFDeg(p1);
-    while (pNext(p1) != NULL)
-    {
-      if (pLmCmp(pNext(p1),strat->kNoether) == -1)
-      {
-        pDelete(&(pNext(p1)));
-        (*p).ecart = pLDeg((*p).p,&((*p).length))-o;
-        p->pLength = 0;
-      }
-      else
-      {
-        pIter(p1);
-      }
-    }
-  }
-}
-
-
+// returns TRUE if mora should use buckets, false otherwise
+static BOOLEAN kMoraUseBucket(kStrategy strat);
+
+static void kOptimizeLDeg(pFDegProc fdeg, pLDegProc ldeg, kStrategy strat)
+{
+  if (fdeg == pDeg)
+  {
+    if (ldeg == pLDeg1) 
+      pLDeg = pLDeg1_Deg;
+    if (ldeg == pLDeg1c)
+      pLDeg = pLDeg1c_Deg;
+  }
+  else if (fdeg == pTotaldegree)
+  {
+    if (ldeg == pLDeg1) 
+      pLDeg = pLDeg1_Totaldegree;
+    if (ldeg == pLDeg1c)
+      pLDeg = pLDeg1c_Totaldegree;
+  }
+
+  if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
+    strat->length_pLength = TRUE;
+    
+  if ((ldeg == pLDeg0c && !rIsSyzIndexRing(currRing)) ||
+      (ldeg == pLDeg0 && strat->ak == 0))
+  {
+    strat->LDegLast = TRUE;
+  }
+  else
+  {
+    strat->LDegLast = FALSE;
+  }
+}
+
+  
 static int doRed (LObject* h, TObject* with,BOOLEAN intoT,kStrategy strat)
 {
@@ -135 +136 @@
     L.Copy();
     h->GetP();
+    h->SetLength(strat->length_pLength);
     ret = ksReducePoly(&L, with, strat->kNoether, NULL, strat);
     if (ret)
@@ -158 +160 @@
 }
 
-#if 0
-/*2
-* reduces h with elements from T choosing first possible
-* element in T with respect to the given ecart
-*/
 int redEcart (LObject* h,kStrategy strat)
 {
@@ -169 +166 @@
   int j = 0;
   int pass = 0;
-  unsigned long not_sev;
-
-  d = pFDeg((*h).p)+(*h).ecart;
-  reddeg = strat->LazyDegree+d;
-  h->sev = pGetShortExpVector(h->p);
-  not_sev = ~ h->sev;
-  loop
-  {
-    if (j > strat->tl)
-    {
-      if (strat->honey) pLDeg((*h).p,&((*h).length));
-      return 1;
-    }
-    if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], (*h).p, not_sev))
-    {
-      //if (strat->interpt) test_int_std(strat->kIdeal);
-      /*- compute the s-polynomial -*/
-      pi = strat->T[j].p;
-      ei = strat->T[j].ecart;
-      li = strat->T[j].length;
-      ii = j;
-      /*
-      * the polynomial to reduce with (up to the moment) is;
-      * pi with ecart ei and length li
-      */
-      i = j;
-      loop
-      {
-      /*- takes the first possible with respect to ecart -*/
-        if (ei <= (*h).ecart) break;
-        i++;
-        if (i > strat->tl) break;
-        if ((((strat->T[i]).ecart < ei)
-          || (((strat->T[i]).ecart == ei)
-          && ((strat->T[i]).length < li)))
-          && pLmShortDivisibleBy(strat->T[i].p, strat->sevT[i],
-                               (*h).p, not_sev))
-        {
-          /*
-           * the polynomial to reduce with is now;
-           */
-          pi = strat->T[i].p;
-          ei = strat->T[i].ecart;
-          li = strat->T[i].length;
-          ii = i;
-        }
-      }
-      /*
-      * end of search: have to reduce with pi
-      */
-      if (ei > (*h).ecart)
-      {
-        /*
-        * It is not possible to reduce h with smaller ecart;
-        * if possible h goes to the lazy-set L,i.e
-        * if its position in L would be not the last one
-        */
-        strat->fromT = TRUE;
-        if (strat->Ll >= 0) /*- L is not empty -*/
-        {
-          if (strat->honey) pLDeg((*h).p,&((*h).length));
-          at = strat->posInL(strat->L,strat->Ll,(*h),strat);
-          if (at <= strat->Ll)
-          {
-            /*- h will not become the next element to reduce -*/
-            enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
-            if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
-            (*h).p = NULL;
-            strat->fromT = FALSE;
-            return -1;
-          }
-        }
-      }
-      doRed(h,&(strat->T[ii]),strat->fromT,strat);
-      strat->fromT=FALSE;
-      if ((*h).p == NULL)
-      {
-        if (h->lcm!=NULL) pLmFree((*h).lcm);
-        return 0;
-      }
-      h->sev = pGetShortExpVector(h->p);
-      not_sev = ~ h->sev;
-      /*computes the ecart*/
-      if (strat->honey)
-      {
-        if (ei <= (*h).ecart)
-          (*h).ecart = d-pFDeg((*h).p);
-        else
-          (*h).ecart = d-pFDeg((*h).p)+ei-(*h).ecart;
-        // pLDeg((*h).p,&((*h).length));
-        //(*h).length = pLength((*h).p);
-      }
-      else
-        (*h).ecart = pLDeg((*h).p,&((*h).length))-pFDeg((*h).p);
-      if (strat->syzComp!=0)
-      {
-        if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
-        {
-          if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
-          return -2;
-        }
-
-      }
-      /*- try to reduce the s-polynomial -*/
-      pass++;
-      d = pFDeg((*h).p)+(*h).ecart;
-      /*
-      *test whether the polynomial should go to the lazyset L
-      *-if the degree jumps
-      *-if the number of pre-defined reductions jumps
-      */
-      if ((strat->Ll >= 0)
-      && ((d >= reddeg) || (pass > strat->LazyPass)))
-      {
-        if (strat->honey) pLDeg((*h).p,&((*h).length));
-        at = strat->posInL(strat->L,strat->Ll,*h,strat);
-        if (at <= strat->Ll)
-        {
-          i=strat->sl+1;
-          do
-          {
-            i--;
-            if (i<0) return 1;
-          } while (!pLmShortDivisibleBy(strat->S[i], strat->sevS[i],
-                                      (*h).p, not_sev));
-          enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
-          if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
-          (*h).p = NULL;
-          return -1;
-        }
-      }
-      else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
-      {
-        Print(".%d",d);mflush();
-        reddeg = d+1;
-      }
-      j = 0;
-    }
-    else
-    {
-      j++;
-    }
-  }
-}
-#else
-int redEcart (LObject* h,kStrategy strat)
-{
-  poly pi;
-  int i,at,reddeg,d,ei,li,ii;
-  int j = 0;
-  int pass = 0;
 
   d = h->GetpFDeg()+ h->ecart;
@@ -329 +175 @@
     if (j < 0)
     {
-      if (strat->honey) h->SetLength();
+      if (strat->honey) h->SetLength(strat->length_pLength);
       return 1;
     }
@@ -347 +193 @@
         /*- takes the first possible with respect to ecart -*/
         i++;
-//        i = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, i);
+#if 1
         if (i > strat->tl) break;
         if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
@@ -353 +199 @@
             &&
             pLmShortDivisibleBy(strat->T[i].p, strat->sevT[i], h->p, ~h->sev))
+#else
+          j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h, i);
+        if (j < 0) break;
+        i = j;
+        if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
+                                        strat->T[i].length < li))
+#endif
         {
           // the polynomial to reduce with is now
@@ -373 +226 @@
       {
         h->SetLmCurrRing();
-        if (strat->honey) h->SetLength();
+        if (strat->honey && strat->posInLDependsOnLength)
+          h->SetLength(strat->length_pLength);
         assume(h->FDeg == h->pFDeg());
-        at = strat->posInL(strat->L,strat->Ll,(*h),strat);
+        at = strat->posInL(strat->L,strat->Ll,h,strat);
         if (at <= strat->Ll)
         {
+          h->CanonicalizeP();
           /*- h will not become the next element to reduce -*/
-          h->CanonicalizeP();
           enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
 #ifdef KDEBUG
@@ -415 +269 @@
     else
       // this has the side effect of setting h->length
-      h->ecart = h->pLDeg() - h->GetpFDeg();
+      h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
 
     if (strat->syzComp!=0)
@@ -440 +294 @@
     {
       h->SetLmCurrRing();
-      if (strat->honey) h->SetLength();
+      if (strat->honey && strat->posInLDependsOnLength) 
+        h->SetLength(strat->length_pLength);
       assume(h->FDeg == h->pFDeg());
-      at = strat->posInL(strat->L,strat->Ll,*h,strat);
+      at = strat->posInL(strat->L,strat->Ll,h,strat);
       if (at <= strat->Ll)
       {
         if (kFindDivisibleByInS(strat->S, strat->sevS, strat->sl, h) < 0)
+        {
+          if (strat->honey && !strat->posInLDependsOnLength) 
+            h->SetLength(strat->length_pLength);
           return 1;
+        }
         h->CanonicalizeP();
         enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
@@ -463 +322 @@
   }
 }
-#endif
 
 /*2
@@ -488 +346 @@
     if (j < 0)
     {
-      if (! strat->homog)
-        h->SetDegStuffReturnLDeg();
+      if (strat->homog) 
+        h->SetDegStuffReturnLDeg(strat->LDegLast);
       return 1;
     }
@@ -529 +387 @@
         if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
 #endif
+        if (strat->homog) 
+          h->SetDegStuffReturnLDeg(strat->LDegLast);
         return -2;
       }
@@ -534 +394 @@
     if (!strat->homog)
     {
-      d = h->SetDegStuffReturnLDeg();
+      d = h->SetDegStuffReturnLDeg(strat->LDegLast);
       /*- try to reduce the s-polynomial -*/
       pass++;
@@ -546 +406 @@
       {
         h->SetLmCurrRing();
-        at = strat->posInL(strat->L,strat->Ll,*h,strat);
+        at = strat->posInL(strat->L,strat->Ll,h,strat);
         if (at <= strat->Ll)
         {
@@ -579 +439 @@
   int j = 0;
   int z = 10;
-  int o = pFDeg(h);
+  int o = H.SetpFDeg();
   H.ecart = pLDeg(H.p,&H.length)-o;
   if (flag==0) cancelunit(&H);
@@ -657 +517 @@
       }
       /*- try to reduce the s-polynomial -*/
-      o = pFDeg(H.p);
+      o = H.SetpFDeg();
       cancelunit(&H);
       H.ecart = pLDeg(H.p,&(H.length))-o;
@@ -681 +541 @@
   for (i=1; i<=strat->Ll; i++)
   {
-    at = strat->posInL(strat->L,i-1,strat->L[i],strat);
+    at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
     if (at != i)
     {
@@ -762 +622 @@
 *(should be minimal)
 */
-BOOLEAN hasPurePower (poly p,int last, int *length,kStrategy strat)
+BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
 {
   poly h;
@@ -769 +629 @@
   if (pNext(p) == strat->tail)
     return FALSE;
-  if (pMinComp(p) == strat->ak)
-  {
-    *length = 0;
-    h = p;
+  pp_Test(p, currRing, strat->tailRing);
+  if (p_MinComp(p, currRing, strat->tailRing) == strat->ak)
+  {
+    i = p_IsPurePower(p, currRing);
+    if (i == last) 
+    {
+      *length = 0;
+      return TRUE;
+    }
+    *length = 1;
+    h = pNext(p);
     while (h != NULL)
     {
-      i = pIsPurePower(h);
+      i = p_IsPurePower(h, strat->tailRing);
       if (i==last) return TRUE;
       (*length)++;
@@ -782 +649 @@
   }
   return FALSE;
+}
+
+BOOLEAN hasPurePower (LObject *L,int last, int *length,kStrategy strat)
+{
+  if (L->bucket != NULL)
+  {
+    poly p = L->CanonicalizeP();
+    BOOLEAN ret = hasPurePower(p, last, length, strat);
+    pNext(p) = NULL;
+    return ret;
+  }
+  else 
+  {
+    return hasPurePower(L->p, last, length, strat);
+  }
 }
 
@@ -788 +670 @@
 * in the case of looking for the pure powers
 */
-int posInL10 (LSet const set, int length, const LObject &p,kStrategy const strat)
+int posInL10 (LSet const set, int length, LObject* p,kStrategy const strat)
 {
   int j,dp,dL;
 
   if (length<0) return 0;
-  if (hasPurePower(p.p,strat->lastAxis,&dp,strat))
-  {
-    int op= pFDeg(p.p)+p.ecart;
+  if (hasPurePower(p,strat->lastAxis,&dp,strat))
+  {
+    int op= p->GetpFDeg() +p->ecart;
     for (j=length; j>=0; j--)
     {
-      if (!hasPurePower(set[j].p,strat->lastAxis,&dL,strat))
+      if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
         return j+1;
       if (dp < dL)
         return j+1;
       if ((dp == dL)
-      && (pFDeg(set[j].p)+set[j].ecart >= op))
+          && (set[j].GetpFDeg()+set[j].ecart >= op))
         return j+1;
     }
@@ -811 +693 @@
   {
     if (j<0) break;
-    if (!hasPurePower(set[j].p,strat->lastAxis,&dL,strat)) break;
+    if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
     j--;
   }
   return strat->posInLOld(set,j,p,strat);
 }
+
 
 /*2
@@ -828 +711 @@
   {
     if (j<0) break;
-    if (hasPurePower(strat->L[j].p,strat->lastAxis,&dL,strat))
+    if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
     {
       p=strat->L[strat->Ll];
@@ -846 +729 @@
       {
         pLmFree(strat->L[j].p);    /*deletes the short spoly and computes*/
-        strat->L[j].p=ksOldCreateSpoly(strat->L[j].p1,
-                                    strat->L[j].p2,
-                                    strat->kNoether);   /*the real one*/
+        poly m1 = NULL, m2 = NULL;
+        // check that spoly creation is ok 
+        while (strat->tailRing != currRing && 
+               !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
+        {
+          assume(m1 == NULL && m2 == NULL);
+          // if not, change to a ring where exponents are at least
+          // large enough
+          kStratChangeTailRing(strat);
+        }
+        /* create the real one */
+        ksCreateSpoly(&(strat->L[j]), strat->kNoether, FALSE, 
+                      strat->tailRing, m1, m2, strat->R);
+
         if (!strat->honey)
           strat->initEcart(&strat->L[j]);
         else
-          strat->L[j].length = pLength(strat->L[j].p);
-        if (hasPurePower(strat->L[j].p,strat->lastAxis,&dL,strat))
+          strat->L[j].SetLength(strat->length_pLength);
+        
+        BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
+        
+        if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
+        
+        if (pp)
         {
           p=strat->L[strat->Ll];
@@ -873 +772 @@
 {
   int i = 0;
+  kTest_TS(strat);
   while (i <= strat->Ll)
   {
@@ -886 +786 @@
       {
         pLmFree(strat->L[i].p);
-        strat->L[i].p = ksOldCreateSpoly(strat->L[i].p1,
-                                         strat->L[i].p2,
-                                         strat->kNoether);
+        poly m1 = NULL, m2 = NULL;
+        // check that spoly creation is ok 
+        while (strat->tailRing != currRing && 
+               !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
+        {
+          assume(m1 == NULL && m2 == NULL);
+          // if not, change to a ring where exponents are at least
+          // large enough
+          kStratChangeTailRing(strat);
+        }
+        /* create the real one */
+        ksCreateSpoly(&(strat->L[i]), strat->kNoether, FALSE, 
+                      strat->tailRing, m1, m2, strat->R);
         strat->L[i].SetpFDeg();
-        strat->L[i].ecart = pLDeg(strat->L[i].p,&strat->L[i].length)
-                           -strat->L[i].GetpFDeg();
+        strat->L[i].ecart 
+          = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
+        if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
       }
     }
     else
-      deleteHC(&strat->L[i].p,&strat->L[i].ecart,&strat->L[i].length,strat);
-   if (strat->L[i].p == NULL)
+      deleteHC(&(strat->L[i]), strat);
+   if (strat->L[i].IsNull())
       deleteInL(strat->L,&strat->Ll,i,strat);
     else
+    {
+#ifdef KDEBUG
+      kTest_L(&(strat->L[i]), strat->tailRing, TRUE, i, strat->T, strat->tl);
+#endif
       i++;
-  }
+    }
+  }
+  kTest_TS(strat);
 }
 
@@ -914 +831 @@
   {
     p = strat->T[i];
-    deleteHCs(&p,strat);
+    deleteHC(&p,strat, TRUE);
     /*- tries to cancel a unit: -*/
     cancelunit(&p);
@@ -934 +851 @@
   if (strat->update)
   {
+    kTest_TS(strat);
     strat->update = (strat->tl == -1);
     if (TEST_OPT_WEIGHTM)
@@ -951 +869 @@
       }
       pLDeg=pLDegOld;
+      kOptimizeLDeg(pFDeg, pLDeg, strat);
       if (ecartWeights)
       {
@@ -965 +884 @@
       return;
     if (!BTEST1(20))        /*- take the first possible -*/
+    {
       strat->red = redFirst;
+      strat->use_buckets = kMoraUseBucket(strat);
+    }
     updateT(strat);
     strat->posInT = posInT2;
     reorderT(strat);
   }
+  kTest_TS(strat);
 }
 
@@ -1022 +945 @@
         strat->posInLOldFlag = FALSE;
         strat->posInL = posInL10;
+        strat->posInLDependsOnLength = TRUE;
         updateL(strat);
         reorderL(strat);
@@ -1104 +1028 @@
     mflush();
   }
-}
+  kOptimizeLDeg(pFDeg, pLDeg, strat);
+}
+
+#ifdef HAVE_ASSUME
+static int mora_count = 0;
+static int mora_loop_count;
+#endif
 
 ideal mora (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
 {
+#ifdef HAVE_ASSUME
+  mora_count++;
+  mora_loop_count = 0;
+#endif
+#ifdef KDEBUG
+  om_Opts.MinTrack = 5;
+#endif
   int srmax;
   int lrmax = 0;
@@ -1143 +1080 @@
   }
   srmax = strat->sl;
+  kTest_TS(strat);
+  strat->use_buckets = kMoraUseBucket(strat);
   /*- compute-------------------------------------------*/
   while (strat->Ll >= 0)
   {
-    kTest_TS(strat);
+#ifdef HAVE_ASSUME
+    mora_loop_count++;
+#endif
     if (lrmax< strat->Ll) lrmax=strat->Ll; /*stat*/
     //test_int_std(strat->kIdeal);
     if (TEST_OPT_DEBUG) messageSets(strat);
     if (TEST_OPT_DEGBOUND
-    && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p)> Kstd1_deg))
+    && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
     {
       /*
@@ -1159 +1100 @@
       */
       while ((strat->Ll >= 0)
-        && (strat->L[strat->Ll].ecart+pFDeg(strat->L[strat->Ll].p)> Kstd1_deg)
+        && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
         && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL))
       {
@@ -1173 +1114 @@
     if (strat->Ll==0) strat->interpt=TRUE;
     strat->Ll--;
+
+    // create the real Spoly
     if (pNext(strat->P.p) == strat->tail)
     {
-      pLmFree(strat->P.p);/*- deletes the short spoly and computes -*/
-      strat->P.p = ksOldCreateSpoly(strat->P.p1,
-                                    strat->P.p2,
-                                    strat->kNoether);/*- the real one -*/
-      if (!strat->honey)
+      /*- deletes the short spoly and computes -*/
+      pLmFree(strat->P.p);
+      strat->P.p = NULL;
+      poly m1 = NULL, m2 = NULL;
+      // check that spoly creation is ok 
+      while (strat->tailRing != currRing && 
+             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
+      {
+        assume(m1 == NULL && m2 == NULL);
+        // if not, change to a ring where exponents are large enough
+        kStratChangeTailRing(strat);
+      }
+      /* create the real one */
+      ksCreateSpoly(&(strat->P), strat->kNoether, strat->use_buckets, 
+                    strat->tailRing, m1, m2, strat->R);
+      if (!strat->use_buckets)
+        strat->P.SetLength(strat->length_pLength);
+    }
+    else if (strat->P.p1 == NULL)
+    {
+      // for input polys, prepare reduction
+      strat->P.SetLength(strat->length_pLength);
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+    
+
+    if (TEST_OPT_PROT) 
+      message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat);
+
+    strat->red(&strat->P,strat);/*- reduction of the element choosen from L -*/
+
+    if (strat->P.p != NULL)
+    {
+      strat->P.GetP();
+      assume(strat->P.sev == 0 || strat->P.sev == pGetShortExpVector(strat->P.p));
+      if (TEST_OPT_PROT) PrintS("s");/*- statistic -*/
+      /*- enter P.p into s and b: -*/
+      if (!TEST_OPT_INTSTRATEGY)
+        strat->P.pNorm();
+
+      strat->P.p = redtail(strat->P.p,strat->sl,strat);
+      if (strat->redTailChange) 
+      {
+        strat->P.pLength = 0;
+        strat->P.last = NULL;
+      }
+      
+      if ((!strat->noTailReduction) && (!strat->honey))
+      {
         strat->initEcart(&strat->P);
-      else
-        strat->P.length = pLength(strat->P.p);
-    }
-    {
-      if (TEST_OPT_PROT) message(strat->P.ecart+(strat->P.p == NULL ? 0 : pFDeg(strat->P.p)),&olddeg,&reduc,strat);
-      strat->red(&strat->P,strat);/*- reduction of the element choosen from L -*/
-    }
-    if (strat->P.p != NULL)
-    {
-      assume(strat->P.sev == 0 || strat->P.sev == pGetShortExpVector(strat->P.p));
-          if (TEST_OPT_PROT) PrintS("s");/*- statistic -*/
-          /*- enter P.p into s and b: -*/
-          if (!TEST_OPT_INTSTRATEGY)
-          {
-            pNorm(strat->P.p);
-          }
-          strat->P.p = redtail(strat->P.p,strat->sl,strat);
-          if ((!strat->noTailReduction) && (!strat->honey))
-          {
-            strat->initEcart(&strat->P);
-          }
-          if (TEST_OPT_INTSTRATEGY)
-          {
-            //pContent(strat->P.p);
-            pCleardenom(strat->P.p);// also does a pContent
-          }
-          cancelunit(&strat->P);/*- tries to cancel a unit -*/
-          enterT(strat->P,strat);
-          {
-            int pos;
-            {
-              enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat);
-              if (strat->sl==-1)
-              {
-                pos=0;
-              }
-              else
-              {
-                pos = posInS(strat->S,strat->sl,strat->P.p);
-              }
-              strat->enterS(strat->P,pos,strat, strat->tl);
-            }
-            if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
-          }
-          kTest_TS(strat);
-          if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
-          strat->P.lcm=NULL;
+      }
+      if (TEST_OPT_INTSTRATEGY)
+        strat->P.pCleardenom();
+      cancelunit(&strat->P);/*- tries to cancel a unit -*/
+      enterT(strat->P,strat);
+      int pos;
+      {
+        enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
+        if (strat->sl==-1)
+        {
+          pos=0;
+        }
+        else
+        {
+          pos = posInS(strat->S,strat->sl,strat->P.p);
+        }
+        strat->enterS(strat->P,pos,strat, strat->tl);
+      }
+      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
+      if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
+      strat->P.lcm=NULL;
 #ifdef KDEBUG
       memset(&strat->P,0,sizeof(strat->P));
@@ -1250 +1211 @@
       }
     }
+    kTest_TS(strat);
   }
   /*- complete reduction of the standard basis------------------------ -*/
@@ -1356 +1318 @@
     h.length = pLength(h.p);
     h.sev = strat->sevS[i];
+    h.SetpFDeg();
     enterT(h,strat);
   }
@@ -1480 +1443 @@
           h.p = strat->S[j];
           h.ecart = strat->ecartS[j];
-          h.length = pLength(h.p);
+          h.pLength = h.length = pLength(h.p);
           if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
           else assume(strat->sevS[j] == pGetShortExpVector(h.p));
           h.sev = strat->sevS[j];
-          h.length = pLength(h.p);
+          h.SetpFDeg();
           enterT(h,strat);
         }
@@ -1873 +1836 @@
   return shdl;
 }
+
+// returns TRUE if mora should use buckets, false otherwise
+static BOOLEAN kMoraUseBucket(kStrategy strat)
+{
+  if (TEST_OPT_NOT_BUCKETS) 
+    return FALSE;
+  if (strat->red == redFirst)
+  {
+    if (strat->homog && !strat->syzComp) 
+      return TRUE;
+    else
+      return FALSE;
+  }
+  else
+  {
+    assume(strat->red == redEcart);
+    if (strat->honey && !strat->syzComp)
+      return TRUE;
+    else
+      return FALSE;
+  }
+}

Singular/kstd2.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kstd2.cc,v 1.61 2000-11-16 09:54:50 obachman Exp $ */
+/* $Id: kstd2.cc,v 1.62 2000-11-23 17:34:09 obachman Exp $ */
 /*
 *  ABSTRACT -  Kernel: alg. of Buchberger
@@ -31 +31 @@
 //        number of first divisor, otherwise
 int kFindDivisibleByInT(const TSet &T, const unsigned long* sevT,
-                        const int tl, const LObject* L)
+                        const int tl, const LObject* L, int start)
 {
   unsigned long not_sev = ~L->sev;
-  int j = 0;
+  int j = start;
   poly p;
   ring r;
@@ -75 +75 @@
     }
   }
-  return -1;
 }
 
@@ -108 +107 @@
 static int redHomog (LObject* h,kStrategy strat)
 {
-  if (strat->tl<0) return 1;
+//  if (strat->tl<0) return 1;
 #ifdef KDEBUG
   if (TEST_OPT_DEBUG)
@@ -123 +122 @@
     h->SetShortExpVector();
     j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, h);
-    if (j < 0) return 1;
+    if (j < 0) 
+    {
+      h->SetpFDeg();
+      return 1;
+    }
     
     // now we found one which is divisible -- reduce it
@@ -131 +134 @@
     if (TEST_OPT_DEBUG)
     {
-      Print("\n%pto ", h->t_p);
+      Print("\nto ", h->t_p);
       h->wrp();
       PrintLn();
@@ -159 +162 @@
   int pass = 0;
   assume(h->pFDeg() == h->FDeg);
-  int reddeg = h->FDeg;
+  long reddeg = h->GetpFDeg();
 
   h->SetShortExpVector();
@@ -203 +206 @@
     {
       h->SetLmCurrRing();
-      at = posInL11(strat->L,strat->Ll,*h,strat);
+      at = posInL11(strat->L,strat->Ll,h,strat);
       if (at <= strat->Ll)
       {
@@ -236 +239 @@
 
   poly h_p;
-  int i,j,at,reddeg,d,pass,ei, ii, h_d;
+  int i,j,at,pass,ei, ii, h_d;
   unsigned long not_sev;
-
+  long reddeg,d;
+  
   pass = j = 0;
-  d = reddeg = h->FDeg + h->ecart;
+  d = reddeg = h->GetpFDeg() + h->ecart;
   h->SetShortExpVector();
   h_p = h->GetLmTailRing();
@@ -289 +293 @@
       if (strat->Ll >= 0) /* L is not empty */
       {
-        at = strat->posInL(strat->L,strat->Ll,*h,strat);
+        at = strat->posInL(strat->L,strat->Ll,h,strat);
 
         if(at <= strat->Ll)
@@ -354 +358 @@
     {
       h->SetLmCurrRing();
-      at = strat->posInL(strat->L,strat->Ll,*h,strat);
+      at = strat->posInL(strat->L,strat->Ll,h,strat);
       if (at <= strat->Ll)
       {
@@ -483 +487 @@
 }
 
+#ifdef KDEBUG
+static int bba_count = 0;
+#endif
+
 ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
 {
+#ifdef KDEBUG
+  bba_count++;
+  int loop_count = 0;
+#endif
   om_Opts.MinTrack = 5;
   int   srmax,lrmax, red_result;
@@ -500 +512 @@
   reduc = olddeg = lrmax = 0;
 
-  if (!TEST_OPT_NOT_BUCKETS && 
-      (strat->red == redHomog || strat->red == redHoney))
+  if (!TEST_OPT_NOT_BUCKETS)
     strat->use_buckets = 1;
 
@@ -515 +526 @@
     if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
 #ifdef KDEBUG
+    loop_count++;
     if (TEST_OPT_DEBUG) messageSets(strat);
 #endif
@@ -536 +548 @@
     if (pNext(strat->P.p) == strat->tail)
     {
+      // deletes the short spoly 
+      pLmFree(strat->P.p);
+      strat->P.p = NULL;
       poly m1 = NULL, m2 = NULL;
-      /* check that spoly creation is ok */
+
+      // check that spoly creation is ok
       while (strat->tailRing != currRing && 
-             !kCheckSpolyCreation(strat, m1, m2))
+             !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
       {
         assume(m1 == NULL && m2 == NULL);
@@ -546 +562 @@
         kStratChangeTailRing(strat);
       }
-      /* deletes the short spoly and computes */
-      pLmFree(strat->P.p);
-      strat->P.p=NULL;
-      /* create the real one */
+      // create the real one
       ksCreateSpoly(&(strat->P), strat->kNoether, strat->use_buckets, 
                     strat->tailRing, m1, m2, strat->R);
     }
-
-    if  ((strat->P.p1==NULL) && (strat->minim>0)) 
-      strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
-
+    else if (strat->P.p1 == NULL)
+    {
+      if (strat->minim > 0)
+        strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
+      // for input polys, prepare reduction
+      strat->P.PrepareRed(strat->use_buckets);
+    }
+    
     if (TEST_OPT_PROT)
       message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
@@ -569 +586 @@
       /* statistic */
       if (TEST_OPT_PROT) PrintS("s");
+
+      // get the polynomial (canonicalize bucket, make sure P.p is set)
       strat->P.GetP(strat->lmBin);
-      /* enter P.p into s and L */
-      {
-        int pos=posInS(strat->S,strat->sl,strat->P.p);
-        if (TEST_OPT_INTSTRATEGY)
+
+      int pos=posInS(strat->S,strat->sl,strat->P.p);
+
+      // reduce the tail and normailze poly
+      if (TEST_OPT_INTSTRATEGY)
+      {
+        strat->P.pCleardenom();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
         {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat);
+          if (strat->redTailChange)  strat->P.pLength = 0;
           strat->P.pCleardenom();
-          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
-          {
-            strat->P.p = redtailBba(&(strat->P),pos-1,strat);
-            if (strat->redTailChange)  strat->P.pLength = 0;
-            strat->P.pCleardenom();
-          }
+        }
+      }
+      else
+      {
+        strat->P.pNorm();
+        if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
+        {
+          strat->P.p = redtailBba(&(strat->P),pos-1,strat);
+          if (strat->redTailChange)  strat->P.pLength = 0;
+        }
+      }
+
+#ifdef KDEBUG
+      if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
+#endif
+
+      // min_std stuff
+      if ((strat->P.p1==NULL) && (strat->minim>0))
+      {
+        if (strat->minim==1)
+        {
+          strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
+          p_Delete(&strat->P.p2, currRing, strat->tailRing);
         }
         else
         {
-          strat->P.pNorm();
-          if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
-          {
-            strat->P.p = redtailBba(&(strat->P),pos-1,strat);
-            if (strat->redTailChange)  strat->P.pLength = 0;
-          }
+          strat->M->m[minimcnt]=strat->P.p2;
+          strat->P.p2=NULL;
         }
-#ifdef KDEBUG
-        if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
-#endif
-        if ((strat->P.p1==NULL) && (strat->minim>0))
-        {
-          if (strat->minim==1)
-          {
-            strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
-            p_Delete(&strat->P.p2, currRing, strat->tailRing);
-          }
-          else
-          {
-            strat->M->m[minimcnt]=strat->P.p2;
-            strat->P.p2=NULL;
-          }
-          if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
-            pNext(strat->M->m[minimcnt]) 
-              = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
-                                             strat->tailRing, currRing,
-                                             currRing->PolyBin);
-          minimcnt++;
-        }
-
-        // put stuff into T-Set
-        enterT(strat->P, strat);
-        enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
-        // posInS only depends on the leading term
-        strat->enterS(strat->P, pos, strat, strat->tl);
-        if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
-      }
+        if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
+          pNext(strat->M->m[minimcnt]) 
+            = strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
+                                           strat->tailRing, currRing,
+                                           currRing->PolyBin);
+        minimcnt++;
+      }
+
+      // enter into S, L, and T
+      enterT(strat->P, strat);
+      enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
+      // posInS only depends on the leading term
+      strat->enterS(strat->P, pos, strat, strat->tl);
+      if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
       if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
       if (strat->sl>srmax) srmax = strat->sl;

Singular/kutil.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kutil.cc,v 1.78 2000-11-16 09:54:51 obachman Exp $ */
+/* $Id: kutil.cc,v 1.79 2000-11-23 17:34:09 obachman Exp $ */
 /*
 * ABSTRACT: kernel: utils for kStd
@@ -12 +12 @@
 // #define PDEBUG 2
 // #define PDIV_DEBUG
-
+#include <limits.h>
 #include <stdlib.h>
 #include <string.h>
@@ -20 +20 @@
 #define KDEBUG 2
 #endif
+// define if enterL, enterT should use memmove instead of doing it manually
+// on topgun, this is slightly faster (see monodromy_l.tst)
+#define ENTER_USE_MEMMOVE
+
 #include "tok.h"
 #include "kutil.h"
@@ -90 +94 @@
 *works only for orderings with ecart =pFDeg(end)-pFDeg(start)
 */
+void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
+{
+  if (strat->kHEdgeFound)
+  {
+    kTest_L(L);
+    poly p1;
+    poly p = L->GetLmTailRing();
+    int l = 1;
+    if (L->bucket != NULL)
+    {
+      kBucketClear(L->bucket, &pNext(p), &L->pLength);
+      L->pLength++;
+    }
+
+    if (!fromNext && p_Cmp(p,strat->kNoether, L->tailRing) == -1)
+    {
+      L->Delete();
+      L->Clear();
+      L->ecart = -1;
+      return;
+    }
+    p1 = p;
+    while (pNext(p1)!=NULL)
+    { 
+      if (p_LmCmp(pNext(p1), strat->kNoether, L->tailRing) == -1)
+      {
+        if (L->last != NULL)
+          L->last = p1;
+        p_Delete(&pNext(p1), L->tailRing);
+        if (p1 == p)
+        {
+          if (L->t_p != NULL)
+          {
+            assume(L->p != NULL && p == L->t_p);
+            pNext(L->p) = NULL;
+          }
+        }
+        if (L->pLength != 0) L->pLength = l;
+        // Hmmm when called from updateT, then only
+        // reset ecart when cut
+        if (fromNext)
+          L->ecart = L->pLDeg() - L->GetpFDeg();
+        break;
+      }
+      l++;
+      pIter(p1);
+    }
+    if (L->bucket != NULL)
+    {
+      if (L->pLength > 1) 
+      {
+        kBucketInit(L->bucket, pNext(p), L->pLength - 1);
+        pNext(p) = NULL;
+        if (L->t_p != NULL) pNext(L->t_p) = NULL;
+        L->pLength = 0;
+      }
+      else
+        kBucketDestroy(&L->bucket);
+    }
+    if (! fromNext)
+    {
+      L->SetpFDeg();
+      L->ecart = L->pLDeg() - L->GetpFDeg();
+    }
+    kTest_L(L);
+  }
+}
+
 void deleteHC(poly* p, int* e, int* l,kStrategy strat)
 {
-  poly p1;
-
-  if (strat->kHEdgeFound)
-  {
-    if (pCmp(*p,strat->kNoether) == -1)
-    {
-      pDelete(p);
-      *l = 0;
-      *e = -1;
-      return;
-    }
-    p1 = *p;
-    while (pNext(p1)!=NULL)
-    {
-      if (pLmCmp(pNext(p1), strat->kNoether) == -1)
-        pDelete(&pNext(p1));
-      else
-        pIter(p1);
-    }
-    *e = pLDeg(*p,l)-pFDeg(*p);
-  }
+  LObject L(*p, currRing, strat->tailRing);
+
+  deleteHC(&L, strat);
+  *p = L.p;
+  *e = L.ecart;
+  *l = L.length;
+  if (L.t_p != NULL) p_LmFree(L.t_p, strat->tailRing);
 }
 
@@ -141 +199 @@
         L->ecart = 0;
         L->length = 1;
-        L->pLength = 1; // let pLength be determined dynamically
+        if (L->pLength > 0) L->pLength = 1;
+        if (L->last != NULL) L->last = p;
+
         if (L->t_p != NULL && pNext(L->t_p) != NULL)
           pNext(L->t_p) = NULL;
@@ -460 +520 @@
   }
 
-  if (T->pLength != 0 &&
-      T->pLength != pLength(p))
+  if (i >= 0 && T->pLength != 0 && T->pLength != pLength(p))
   {
     return dReportError("%c[%d] pLength error: has %d, specified to have %d",
@@ -491 +550 @@
   if (testp)
   {
+    poly pn = NULL;
     if (L->bucket != NULL)
     {
       kFalseReturn(kbTest(L->bucket));
       r_assume(L->bucket->bucket_ring == L->tailRing);
+      if (L->p != NULL && pNext(L->p) != NULL)
+      {
+        pn = pNext(L->p);
+        pNext(L->p) = NULL;
+      }
     }
     kFalseReturn(kTest_T(L, strat_tailRing, lpos, 'L'));
+    if (pn != NULL)
+      pNext(L->p) = pn;
+
     ring r;
     poly p;
@@ -504 +572 @@
       return dReportError("L[%d] wrong sev: has %o, specified to have %o",
                           lpos, p_GetShortExpVector(p, r), L->sev);
+    }
+    if (lpos > 0 && L->last != NULL && pLast(p) != L->last)
+    {
+      return dReportError("L[%d] last wrong: has %p specified to have %p",
+                          lpos, pLast(p), L->last);
     }
   }
@@ -618 +691 @@
   for (i=0; i<=strat->Ll; i++)
   {
-    if (strat->L[i].i_r1 >= 0 && 
-        (strat->L[i].i_r1 > strat->tl ||
-         strat->L[i].T_1(strat)->p != strat->L[i].p1))
-      return dReportError("L[%d].i_r1 out of sync", i);
-    if (strat->L[i].i_r2 >= 0 && 
-        (strat->L[i].i_r2 > strat->tl ||
-         strat->L[i].T_2(strat)->p != strat->L[i].p2))
-      return dReportError("L[%d].i_r2 out of sync", i);
+    if (strat->L[i].p1 != NULL && strat->L[i].p2)
+    {
+      if (strat->L[i].i_r1 < 0 ||
+          strat->L[i].i_r1 > strat->tl ||
+          strat->L[i].T_1(strat)->p != strat->L[i].p1)
+        return dReportError("L[%d].i_r1 out of sync", i);
+      if (strat->L[i].i_r2 < 0 ||
+          strat->L[i].i_r2 > strat->tl ||
+          strat->L[i].T_2(strat)->p != strat->L[i].p2);
+    }
+    else
+    {
+      if (strat->L[i].i_r1 != -1)
+        return dReportError("L[%d].i_r1 out of sync", i);
+      if (strat->L[i].i_r2 != -1)
+        return dReportError("L[%d].i_r2 out of sync", i);
+    }
   }
   return TRUE;
@@ -691 +773 @@
           {
             /* not found : */
+            if (set[j].bucket != NULL)
+            {
+              kBucketDeleteAndDestroy(&set[j].bucket);
+              pNext(p) = NULL;
+              if (set[j].t_p != NULL) pNext(set[j].t_p) = NULL;
+            }
             if (set[j].t_p != NULL)
             {
@@ -700 +788 @@
               pDelete(&p);
             }
-            if (set[j].bucket != NULL)
-              kBucketDeleteAndDestroy(&set[j].bucket);
             break;
           }
@@ -751 +837 @@
   int i;
   // this should be corrected
-  p.FDeg = p.pFDeg();
+  assume(p.FDeg == p.pFDeg());
   if ((*length)>=0)
   {
     if ((*length) == (*LSetmax)-1) enlargeL(set,LSetmax,setmax);
+    if (at <= (*length))
+#ifdef ENTER_USE_MEMMOVE
+      memmove(&((*set)[at+1]), &((*set)[at]), ((*length)-at+1)*sizeof(LObject));
+#else
     for (i=(*length)+1; i>=at+1; i--) (*set)[i] = (*set)[i-1];
+#endif
   }
   else at = 0;
@@ -990 +1081 @@
       nDelete(&(Lp.p->coef));
     }
-    l = strat->posInL(strat->B,strat->Bl,Lp,strat);
+    l = strat->posInL(strat->B,strat->Bl,&Lp,strat);
     enterL(&strat->B,&strat->Bl,&strat->Bmax,Lp,l);
   }
@@ -1052 +1143 @@
       nDelete(&(Lp.p->coef));
     }
-    l = strat->posInL(strat->L,strat->Ll,Lp,strat);
+    l = strat->posInL(strat->L,strat->Ll,&Lp,strat);
     enterL(&strat->L,&strat->Ll,&strat->Lmax,Lp,l);
   }
@@ -1194 +1285 @@
     for (i=strat->Bl; i>=0; i--)
     {
-      j = strat->posInL(strat->L,j-1,strat->B[i],strat);
+      j = strat->posInL(strat->L,j-1,&(strat->B[i]),strat);
       enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
     }
@@ -1228 +1319 @@
     for (i=strat->Bl; i>=0; i--)
     {
-      j = strat->posInL(strat->L,j,strat->B[i],strat);
+      j = strat->posInL(strat->L,j,&(strat->B[i]),strat);
       enterL(&strat->L,&strat->Ll,&strat->Lmax,strat->B[i],j);
     }
@@ -1635 +1726 @@
  * int o;
  *
- * o = pFDeg(p.p);
+ * o = p.GetpFDeg();
  * loop
  * {
@@ -1651 +1742 @@
   if (length==-1) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p.GetpFDeg();
   int op = set[length].GetpFDeg();
 
@@ -1691 +1782 @@
   if (length==-1) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p.GetpFDeg();
   int op = set[length].GetpFDeg();
 
@@ -1736 +1827 @@
   if (length==-1) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p.GetpFDeg();
 
   if (set[length].GetpFDeg() <= o)
@@ -1770 +1861 @@
  * int o;
  *
- * o = pFDeg(p.p)+p.ecart;
+ * o = p.GetpFDeg()+p.ecart;
  * loop
  * {
@@ -1787 +1878 @@
   if (length==-1) return 0;
 
-  int o = pFDeg(p.p) + p.ecart;
+  int o = p.GetpFDeg() + p.ecart;
   int op = set[length].GetpFDeg()+set[length].ecart;
 
@@ -1829 +1920 @@
 * int  o;
 *
-*  o = pFDeg(p.p)+p.ecart;
+*  o = p.GetpFDeg()+p.ecart;
 *  loop
 *  {
@@ -1847 +1938 @@
   if (length==-1) return 0;
 
-  int o = pFDeg(p.p) + p.ecart;
+  int o = p.GetpFDeg() + p.ecart;
   int op = set[length].GetpFDeg()+set[length].ecart;
 
@@ -1893 +1984 @@
   int cc = (-1+2*currRing->order[0]==ringorder_c);
   /* cc==1 for (c,..), cc==-1 for (C,..) */
-  int o = pFDeg(p.p) + p.ecart;
+  int o = p.GetpFDeg() + p.ecart;
   int c = pGetComp(p.p)*cc;
 
@@ -1957 +2048 @@
 
   int o = p.ecart;
-  int op=pFDeg(p.p);
+  int op=p.GetpFDeg();
 
   if (set[length].ecart < o)
@@ -2009 +2100 @@
 */
 int posInLSpecial (const LSet set, const int length,
-                   const LObject &p,const kStrategy strat)
+                   LObject *p,const kStrategy strat)
 {
   if (length<0) return 0;
 
-  int d=pFDeg(p.p);
+  int d=p->GetpFDeg();
   int op=set[length].GetpFDeg();
 
   if ((op > d)
-  || ((op == d) && (p.p1!=NULL)&&(set[length].p1==NULL))
-  || (pLmCmp(set[length].p,p.p)== pOrdSgn))
+  || ((op == d) && (p->p1!=NULL)&&(set[length].p1==NULL))
+  || (pLmCmp(set[length].p,p->p)== pOrdSgn))
      return length+1;
 
@@ -2030 +2121 @@
       op=set[an].GetpFDeg();
       if ((op > d)
-      || ((op == d) && (p.p1!=NULL) && (set[an].p1==NULL))
-      || (pLmCmp(set[an].p,p.p)== pOrdSgn))
+      || ((op == d) && (p->p1!=NULL) && (set[an].p1==NULL))
+      || (pLmCmp(set[an].p,p->p)== pOrdSgn))
          return en;
       return an;
@@ -2038 +2129 @@
     op=set[i].GetpFDeg();
     if ((op>d)
-    || ((op==d) && (p.p1!=NULL) && (set[i].p1==NULL))
-    || (pLmCmp(set[i].p,p.p) == pOrdSgn))
+    || ((op==d) && (p->p1!=NULL) && (set[i].p1==NULL))
+    || (pLmCmp(set[i].p,p->p) == pOrdSgn))
       an=i;
     else
@@ -2052 +2143 @@
 */
 int posInL0 (const LSet set, const int length,
-             const LObject &p,const kStrategy strat)
+             LObject* p,const kStrategy strat)
 {
   if (length<0) return 0;
 
-  if (pLmCmp(set[length].p,p.p)== pOrdSgn)
+  if (pLmCmp(set[length].p,p->p)== pOrdSgn)
     return length+1;
 
@@ -2066 +2157 @@
     if (an >= en-1)
     {
-      if (pLmCmp(set[an].p,p.p) == pOrdSgn) return en;
+      if (pLmCmp(set[an].p,p->p) == pOrdSgn) return en;
       return an;
     }
     i=(an+en) / 2;
-    if (pLmCmp(set[i].p,p.p) == pOrdSgn) an=i;
+    if (pLmCmp(set[i].p,p->p) == pOrdSgn) an=i;
     else                                 en=i;
     /*aend. fuer lazy == in !=- machen */
@@ -2083 +2174 @@
 */
 int posInL11 (const LSet set, const int length,
-              const LObject &p,const kStrategy strat)
+              LObject* p,const kStrategy strat)
 /*{
  * int j=0;
  * int o;
  *
- * o = pFDeg(p.p);
+ * o = p->GetpFDeg();
  * loop
  * {
  *   if (j > length)            return j;
  *   if ((set[j].GetpFDeg() < o)) return j;
- *   if ((set[j].GetpFDeg() == o) && (pLmCmp(set[j].p,p.p) == -pOrdSgn))
+ *   if ((set[j].GetpFDeg() == o) && (pLmCmp(set[j].p,p->p) == -pOrdSgn))
  *   {
  *     return j;
@@ -2104 +2195 @@
   if (length<0) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p->GetpFDeg();
   int op = set[length].GetpFDeg();
 
   if ((op > o)
-  || ((op == o) && (pLmCmp(set[length].p,p.p) != -pOrdSgn)))
+  || ((op == o) && (pLmCmp(set[length].p,p->p) != -pOrdSgn)))
     return length+1;
   int i;
@@ -2119 +2210 @@
       op = set[an].GetpFDeg();
       if ((op > o)
-      || ((op == o) && (pLmCmp(set[an].p,p.p) != -pOrdSgn)))
+      || ((op == o) && (pLmCmp(set[an].p,p->p) != -pOrdSgn)))
         return en;
       return an;
@@ -2126 +2217 @@
     op = set[i].GetpFDeg();
     if ((op > o)
-    || ((op == o) && (pLmCmp(set[i].p,p.p) != -pOrdSgn)))
+    || ((op == o) && (pLmCmp(set[i].p,p->p) != -pOrdSgn)))
       an=i;
     else
@@ -2139 +2230 @@
 */
 int posInL110 (const LSet set, const int length,
-               const LObject &p,const kStrategy strat)
+               LObject* p,const kStrategy strat)
 {
   if (length<0) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p->GetpFDeg();
   int op = set[length].GetpFDeg();
 
   if ((op > o)
-  || ((op == o) && (set[length].length >2*p.length))
-  || ((op == o) && (set[length].length <= 2*p.length)
-     && (pLmCmp(set[length].p,p.p) != -pOrdSgn)))
+  || ((op == o) && (set[length].length >2*p->length))
+  || ((op == o) && (set[length].length <= 2*p->length)
+     && (pLmCmp(set[length].p,p->p) != -pOrdSgn)))
     return length+1;
   int i;
@@ -2160 +2251 @@
       op = set[an].GetpFDeg();
       if ((op > o)
-      || ((op == o) && (set[an].length >2*p.length))
-      || ((op == o) && (set[an].length <=2*p.length)
-         && (pLmCmp(set[an].p,p.p) != -pOrdSgn)))
+      || ((op == o) && (set[an].length >2*p->length))
+      || ((op == o) && (set[an].length <=2*p->length)
+         && (pLmCmp(set[an].p,p->p) != -pOrdSgn)))
         return en;
       return an;
@@ -2169 +2260 @@
     op = set[i].GetpFDeg();
     if ((op > o)
-    || ((op == o) && (set[i].length > 2*p.length))
-    || ((op == o) && (set[i].length <= 2*p.length)
-       && (pLmCmp(set[i].p,p.p) != -pOrdSgn)))
+    || ((op == o) && (set[i].length > 2*p->length))
+    || ((op == o) && (set[i].length <= 2*p->length)
+       && (pLmCmp(set[i].p,p->p) != -pOrdSgn)))
       an=i;
     else
@@ -2185 +2276 @@
 */
 int posInL13 (const LSet set, const int length,
-              const LObject &p,const kStrategy strat)
+              LObject* p,const kStrategy strat)
 {
   if (length<0) return 0;
 
-  int o = pFDeg(p.p);
+  int o = p->GetpFDeg();
 
   if (set[length].GetpFDeg() > o)
@@ -2220 +2311 @@
 */
 int posInL15 (const LSet set, const int length,
-              const LObject &p,const kStrategy strat)
+              LObject* p,const kStrategy strat)
 /*{
  * int j=0;
  * int o;
  *
- * o = p.ecart+pFDeg(p.p);
+ * o = p->ecart+p->GetpFDeg();
  * loop
  * {
@@ -2231 +2322 @@
  *   if (set[j].GetpFDeg()+set[j].ecart < o) return j;
  *   if ((set[j].GetpFDeg()+set[j].ecart == o)
- *   && (pLmCmp(set[j].p,p.p) == -pOrdSgn))
+ *   && (pLmCmp(set[j].p,p->p) == -pOrdSgn))
  *   {
  *     return j;
@@ -2242 +2333 @@
   if (length<0) return 0;
 
-  int o = pFDeg(p.p) + p.ecart;
+  int o = p->GetpFDeg() + p->ecart;
   int op = set[length].GetpFDeg() + set[length].ecart;
 
   if ((op > o)
-  || ((op == o) && (pLmCmp(set[length].p,p.p) != -pOrdSgn)))
+  || ((op == o) && (pLmCmp(set[length].p,p->p) != -pOrdSgn)))
     return length+1;
   int i;
@@ -2257 +2348 @@
       op = set[an].GetpFDeg() + set[an].ecart;
       if ((op > o)
-      || ((op == o) && (pLmCmp(set[an].p,p.p) != -pOrdSgn)))
+      || ((op == o) && (pLmCmp(set[an].p,p->p) != -pOrdSgn)))
         return en;
       return an;
@@ -2264 +2355 @@
     op = set[i].GetpFDeg() + set[i].ecart;
     if ((op > o)
-    || ((op == o) && (pLmCmp(set[i].p,p.p) != -pOrdSgn)))
+    || ((op == o) && (pLmCmp(set[i].p,p->p) != -pOrdSgn)))
       an=i;
     else
@@ -2279 +2370 @@
 */
 int posInL17 (const LSet set, const int length,
-              const LObject &p,const kStrategy strat)
+              LObject* p,const kStrategy strat)
 {
   if (length<0) return 0;
 
-  int o = pFDeg(p.p) + p.ecart;
+  int o = p->GetpFDeg() + p->ecart;
 
   if ((set[length].GetpFDeg() + set[length].ecart > o)
   || ((set[length].GetpFDeg() + set[length].ecart == o)
-     && (set[length].ecart > p.ecart))
+     && (set[length].ecart > p->ecart))
   || ((set[length].GetpFDeg() + set[length].ecart == o)
-     && (set[length].ecart == p.ecart)
-     && (pLmCmp(set[length].p,p.p) != -pOrdSgn)))
+     && (set[length].ecart == p->ecart)
+     && (pLmCmp(set[length].p,p->p) != -pOrdSgn)))
     return length+1;
   int i;
@@ -2301 +2392 @@
       if ((set[an].GetpFDeg() + set[an].ecart > o)
       || ((set[an].GetpFDeg() + set[an].ecart == o)
-         && (set[an].ecart > p.ecart))
+         && (set[an].ecart > p->ecart))
       || ((set[an].GetpFDeg() + set[an].ecart == o)
-         && (set[an].ecart == p.ecart)
-         && (pLmCmp(set[an].p,p.p) != -pOrdSgn)))
+         && (set[an].ecart == p->ecart)
+         && (pLmCmp(set[an].p,p->p) != -pOrdSgn)))
         return en;
       return an;
@@ -2311 +2402 @@
     if ((set[i].GetpFDeg() + set[i].ecart > o)
     || ((set[i].GetpFDeg() + set[i].ecart == o)
-       && (set[i].ecart > p.ecart))
+       && (set[i].ecart > p->ecart))
     || ((set[i].GetpFDeg() +set[i].ecart == o)
-       && (set[i].ecart == p.ecart)
-       && (pLmCmp(set[i].p,p.p) != -pOrdSgn)))
+       && (set[i].ecart == p->ecart)
+       && (pLmCmp(set[i].p,p->p) != -pOrdSgn)))
       an=i;
     else
@@ -2327 +2418 @@
 */
 int posInL17_c (const LSet set, const int length,
-                const LObject &p,const kStrategy strat)
+                LObject* p,const kStrategy strat)
 {
   if (length<0) return 0;
@@ -2333 +2424 @@
   int cc = (-1+2*currRing->order[0]==ringorder_c);
   /* cc==1 for (c,..), cc==-1 for (C,..) */
-  int c = pGetComp(p.p)*cc;
-  int o = pFDeg(p.p) + p.ecart;
+  int c = pGetComp(p->p)*cc;
+  int o = p->GetpFDeg() + p->ecart;
 
   if (pGetComp(set[length].p)*cc > c)
@@ -2342 +2433 @@
     if ((set[length].GetpFDeg() + set[length].ecart > o)
     || ((set[length].GetpFDeg() + set[length].ecart == o)
-       && (set[length].ecart > p.ecart))
+       && (set[length].ecart > p->ecart))
     || ((set[length].GetpFDeg() + set[length].ecart == o)
-       && (set[length].ecart == p.ecart)
-       && (pLmCmp(set[length].p,p.p) != -pOrdSgn)))
+       && (set[length].ecart == p->ecart)
+       && (pLmCmp(set[length].p,p->p) != -pOrdSgn)))
       return length+1;
   }
@@ -2361 +2452 @@
         if ((set[an].GetpFDeg() + set[an].ecart > o)
         || ((set[an].GetpFDeg() + set[an].ecart == o)
-           && (set[an].ecart > p.ecart))
+           && (set[an].ecart > p->ecart))
         || ((set[an].GetpFDeg() + set[an].ecart == o)
-           && (set[an].ecart == p.ecart)
-           && (pLmCmp(set[an].p,p.p) != -pOrdSgn)))
+           && (set[an].ecart == p->ecart)
+           && (pLmCmp(set[an].p,p->p) != -pOrdSgn)))
           return en;
       }
@@ -2376 +2467 @@
       if ((set[i].GetpFDeg() + set[i].ecart > o)
       || ((set[i].GetpFDeg() + set[i].ecart == o)
-         && (set[i].ecart > p.ecart))
+         && (set[i].ecart > p->ecart))
       || ((set[i].GetpFDeg() +set[i].ecart == o)
-         && (set[i].ecart == p.ecart)
-         && (pLmCmp(set[i].p,p.p) != -pOrdSgn)))
+         && (set[i].ecart == p->ecart)
+         && (pLmCmp(set[i].p,p->p) != -pOrdSgn)))
         an=i;
       else
@@ -2388 +2479 @@
   }
 }
+
+/***************************************************************
+ *
+ * Tail reductions
+ * 
+ ***************************************************************/
+static TObject* 
+kFindDivisibleByInS(kStrategy strat, int pos, LObject* L, TObject *T, 
+                    long ecart = LONG_MAX)
+{
+  int j = 0;
+  const unsigned long not_sev = ~L->sev;
+  const unsigned long* sev = strat->sevS;
+  poly p;
+  ring r;
+  L->GetLm(p, r);
+  
+  assume(~not_sev == p_GetShortExpVector(p, r));
+
+  if (r == currRing)
+  {
+    while (1)
+    {
+      if (j > pos) return NULL;
+#if defined(PDEBUG) || defined(PDIV_DEBUG)
+      if (p_LmShortDivisibleBy(strat->S[j], sev[j], p, not_sev, r) &&
+          (ecart== LONG_MAX || ecart>= strat->ecartS[j]))
+        break;
+#else
+      if (!(sev[j] & not_sev) &&
+          (ecart== LONG_MAX || ecart>= strat->ecartS[j]) &&
+          p_LmDivisibleBy(strat->S[j], p, r))
+        break;
+      
+#endif
+      j++;
+    }
+    // if called from NF, T objects do not exist:
+    if (strat->tl < 0) 
+    {
+      T->Set(strat->S[j], r);
+      return T;
+    }
+    else
+    {
+      assume (j >= 0 && j <= strat->tl && strat->S_2_T(j) != NULL);
+      return strat->S_2_T(j);
+    }
+  }
+  else
+  {
+    TObject* t;
+    while (1)
+    {
+      if (j > pos) return NULL;
+#if defined(PDEBUG) || defined(PDIV_DEBUG)
+      t = strat->S_2_T(j);
+      assume(t != NULL && t->t_p != NULL && t->tailRing == r);
+      if (p_LmShortDivisibleBy(t->t_p, sev[j], p, not_sev, r) && 
+          (ecart== LONG_MAX || ecart>= strat->ecartS[j]))
+        return t;
+#else      
+      if (! (sev[j] & not_sev) && (ecart== LONG_MAX || ecart>= strat->ecartS[j]))
+      {
+        t = strat->S_2_T(j);
+        assume(t != NULL && t->t_p != NULL && t->tailRing == r);
+        if (p_LmDivisibleBy(t->t_p, p, r)) return t;
+      }
+#endif
+      j++;
+    }
+  }
+}
+
+
+poly redtail (LObject* L, int pos, kStrategy strat)
+{
+  poly h, hn;
+  int j;
+  unsigned long not_sev;
+  strat->redTailChange=FALSE;
+  poly p = L->p;
+  if (strat->noTailReduction || pNext(p) == NULL)
+    return p;
+
+  LObject Ln(strat->tailRing);
+  TObject* With;
+  // placeholder in case strat->tl < 0
+  TObject  With_s(strat->tailRing);
+  h = p;
+  hn = pNext(h);
+  long op = pFDeg(hn, strat->tailRing);
+  long e;
+  int l;
+  BOOLEAN save_HE=strat->kHEdgeFound;
+  strat->kHEdgeFound |= 
+    ((Kstd1_deg>0) && (op<=Kstd1_deg)) || TEST_OPT_INFREDTAIL;
+
+  while(hn != NULL)
+  {
+    e = pLDeg(hn, &l, strat->tailRing) - op;
+    while (1)
+    {
+      kTest_TS(strat);
+      Ln.Set(hn, strat->tailRing);
+      Ln.sev = p_GetShortExpVector(hn, strat->tailRing);
+      if (strat->kHEdgeFound)
+        With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
+      else
+        With = kFindDivisibleByInS(strat, pos, &Ln, &With_s, e);
+      if (With == NULL) break;
+      strat->redTailChange=TRUE;
+      if (ksReducePolyTail(L, With, h, strat->kNoether))
+      {
+        // reducing the tail would violate the exp bound
+        if (kStratChangeTailRing(strat, L))
+        {
+          strat->kHEdgeFound = save_HE;
+          return redtail(L, pos, strat);
+        }
+        else
+          return NULL;
+      }
+      hn = pNext(h);
+      if (hn == NULL) goto all_done;
+      op = pFDeg(hn, strat->tailRing);
+      e = pLDeg(hn, &l) - op;
+      kTest_TS(strat);
+    }
+    h = hn;
+    hn = pNext(h);
+  }
+
+  all_done:
+  strat->kHEdgeFound = save_HE;
+  return p;
+}
+
+#define OLD_RED_TAIL
+#ifdef OLD_RED_TAIL
 /*2
 * reduces h using the set S
@@ -2398 +2629 @@
 poly redtail (poly p, int pos, kStrategy strat)
 {
-  if ((!strat->noTailReduction)
-  && (pNext(p)!=NULL))
+  if ((!strat->noTailReduction) && (pNext(p)!=NULL))
   {
     int j, e, l;
@@ -2418 +2648 @@
       {
         if (pLmShortDivisibleBy(strat->S[j], strat->sevS[j], hn, not_sev)
-        && ((e >= strat->ecartS[j])
-          || strat->kHEdgeFound)
-        )
+            && 
+            ((e >= strat->ecartS[j]) || strat->kHEdgeFound))
         {
           strat->redTailChange=TRUE;
@@ -2448 +2677 @@
   return p;
 }
-
-/*2
-*compute the normalform of the tail p->next of p
-*with respect to S
-*/
-TObject* kFindDivisibleByInS(kStrategy strat, int pos, LObject* L, TObject *T)
-{
-  int j = 0;
-  const unsigned long not_sev = ~L->sev;
-  const unsigned long* sev = strat->sevS;
-  poly p;
-  ring r;
-  L->GetLm(p, r);
-  
-  assume(~not_sev == p_GetShortExpVector(p, r));
-
-  if (r == currRing)
-  {
-    while (1)
-    {
-      if (j > pos) return NULL;
-#if defined(PDEBUG) || defined(PDIV_DEBUG)
-      if (p_LmShortDivisibleBy(strat->S[j], sev[j], p, not_sev, r))
-        break;
 #else
-      if (!(sev[j] & not_sev) &&
-          p_LmDivisibleBy(strat->S[j], p, r))
-        break;
-      
+poly redtail (poly p, int pos, kStrategy strat)
+{
+  LObject L(p, currRing);
+  return redtail(&L, pos, strat);
+}
 #endif
-      j++;
-    }
-    // if called from NF, T objects do not exist:
-    if (strat->tl < 0) 
-    {
-      T->Set(strat->S[j], r);
-      return T;
-    }
-    else
-    {
-      assume (j >= 0 && j <= strat->tl && strat->S_2_T(j) != NULL);
-      return strat->S_2_T(j);
-    }
-  }
-  else
-  {
-    TObject* t;
-    while (1)
-    {
-      if (j > pos) return NULL;
-#if defined(PDEBUG) || defined(PDIV_DEBUG)
-      t = strat->S_2_T(j);
-      assume(t != NULL && t->t_p != NULL && t->tailRing == r);
-      if (p_LmShortDivisibleBy(t->t_p, sev[j], p, not_sev, r))
-        return t;
-#else      
-      if (! (sev[j] & not_sev))
-      {
-        t = strat->S_2_T(j);
-        assume(t != NULL && t->t_p != NULL && t->tailRing == r);
-        if (p_LmDivisibleBy(t->t_p, p, r)) return t;
-      }
-#endif
-      j++;
-    }
-  }
-}
 
 poly redtailBba (LObject* L, int pos, kStrategy strat)
@@ -2641 +2810 @@
 
 #endif
+
 
 /*2
@@ -2672 +2842 @@
         {
           //pContent(h.p);
-          pCleardenom(h.p); // also does a pContent
+          h.pCleardenom(); // also does a pContent
         }
         else
         {
-          pNorm(h.p);
+          h.pNorm();
         }
         strat->initEcart(&h);
         if (pOrdSgn==-1)
         {
-          deleteHC(&h.p, &h.ecart, &h.length,strat);
+          deleteHC(&h, strat);
         }
         if (h.p!=NULL)
@@ -2707 +2877 @@
       {
         //pContent(h.p);
-        pCleardenom(h.p); // also does a pContent
+        h.pCleardenom(); // also does a pContent
       }
       else
       {
-        pNorm(h.p);
+        h.pNorm();
       }
       strat->initEcart(&h);
@@ -2717 +2887 @@
       {
         cancelunit(&h);  /*- tries to cancel a unit -*/
-        deleteHC(&h.p, &h.ecart, &h.length,strat);
+        deleteHC(&h, strat);
       }
       if (TEST_OPT_DEGBOUND
@@ -2771 +2941 @@
         {
           //pContent(h.p);
-          pCleardenom(h.p); // also does a pContent
+          h.pCleardenom(); // also does a pContent
         }
         else
         {
-          pNorm(h.p);
+          h.pNorm();
         }
         strat->initEcart(&h);
         if (pOrdSgn==-1)
         {
-          deleteHC(&h.p, &h.ecart, &h.length,strat);
+          deleteHC(&h,strat);
         }
         if (h.p!=NULL)
@@ -2806 +2976 @@
       {
         //pContent(h.p);
-        pCleardenom(h.p); // also does a pContent
+        h.pCleardenom(); // also does a pContent
       }
       else
       {
-        pNorm(h.p);
+        h.pNorm();
       }
       strat->initEcart(&h);
@@ -2816 +2986 @@
       {
         cancelunit(&h);  /*- tries to cancel a unit -*/
-        deleteHC(&h.p, &h.ecart, &h.length,strat);
+        deleteHC(&h, strat);
       }
       if (TEST_OPT_DEGBOUND
@@ -2829 +2999 @@
           else
           {
-            pos = strat->posInL(strat->L,strat->Ll,h,strat);
+            pos = strat->posInL(strat->L,strat->Ll,&h,strat);
           }
           h.sev = pGetShortExpVector(h.p);
@@ -2875 +3045 @@
         //{
         //  //pContent(h.p);
-        //  pCleardenom(h.p); // also does a pContent
+        //  h.pCleardenom(); // also does a pContent
         //}
         //else
         //{
-        //  pNorm(h.p);
+        //  h.pNorm();
         //}
         strat->initEcart(&h);
         if (pOrdSgn==-1)
         {
-          deleteHC(&h.p, &h.ecart, &h.length,strat);
+          deleteHC(&h,strat);
         }
         if (h.p!=NULL)
@@ -2895 +3065 @@
           }
           h.sev = pGetShortExpVector(h.p);
+          h.SetpFDeg();
           strat->enterS(h,pos,strat, strat->tl+1);
           enterT(h, strat);
@@ -2916 +3087 @@
       if (pOrdSgn==-1)
       {
-          deleteHC(&h.p, &h.ecart, &h.length,strat);
+        deleteHC(&h,strat);
       }
       if (TEST_OPT_DEGBOUND
@@ -2934 +3105 @@
         strat->enterS(h,pos,strat, strat->tl+1);
         h.length = pLength(h.p);
+        h.SetpFDeg();
         enterT(h,strat);
       }
@@ -2948 +3120 @@
       if (TEST_OPT_INTSTRATEGY)
       {
-        pCleardenom(h.p);
+        h.pCleardenom();
       }
       else
       {
-        pNorm(h.p);
+        h.pNorm();
       }
       if(strat->sl>=0)
@@ -2971 +3143 @@
           if (TEST_OPT_INTSTRATEGY)
           {
-            pCleardenom(h.p);
+            h.pCleardenom();
           }
           else
           {
-            pNorm(h.p);
+            h.is_normalized = 0;
+            h.pNorm();
           }
           h.sev = pGetShortExpVector(h.p);
+          h.SetpFDeg();
           pos = posInS(strat->S,strat->sl,h.p);
           enterpairsSpecial(h.p,strat->sl,h.ecart,pos,strat,strat->tl+1);
@@ -2987 +3161 @@
       {
         h.sev = pGetShortExpVector(h.p);
+        h.SetpFDeg();
         strat->enterS(h,0,strat, strat->tl+1);
         enterT(h,strat);
@@ -3119 +3294 @@
   int  j=0;
   int  e,l;
-  poly h1;
   unsigned long not_sev = ~ pGetShortExpVector(h);
 
@@ -3130 +3304 @@
       && ((e >= strat->ecartS[j]) || strat->kHEdgeFound))
       {
-        h1 = ksOldSpolyRedNew(strat->S[j],h,strat->kNoether);
+#ifdef KDEBUG
+        if (TEST_OPT_DEBUG)
+          PrintS("reduce "); wrp(h); Print(" with S[%d] (",j);wrp(strat->S[j]);
+#endif          
+        h = ksOldSpolyRed(strat->S[j],h,strat->kNoether);
+#ifdef KDEBUG
         if(TEST_OPT_DEBUG)
-        {
-          PrintS("reduce "); wrp(h); Print(" with S[%d] (",j);wrp(strat->S[j]);
-          PrintS(")\nto "); wrp(h1); PrintLn();
-        }
-        pDelete(&h);
-        if (h1 == NULL) return NULL;
-        h = h1;
+          PrintS(")\nto "); wrp(h); PrintLn();
+#endif
+        // pDelete(&h);
+        if (h == NULL) return NULL;
         e = pLDeg(h,&l)-pFDeg(h);
         j = 0;
@@ -3239 +3415 @@
         else assume(strat->sevS[i] == pGetShortExpVector(h.p));
         h.sev = strat->sevS[i];
+        h.SetpFDeg();
         /*puts the elements of S also to T*/
         enterT(h,strat);
@@ -3322 +3499 @@
         cancelunit1(&h,strat->sl,strat);
       h.length = pLength(h.p);
+      h.SetpFDeg();
       /*puts the elements of S also to T*/
       enterT(h,strat);
@@ -3366 +3544 @@
     strat->Shdl->m=strat->S;
   }
-  for (i=strat->sl+1; i>=atS+1; i--)
-  {
-    strat->S[i] = strat->S[i-1];
-    strat->ecartS[i] = strat->ecartS[i-1];
-    strat->sevS[i] = strat->sevS[i-1];
-    strat->S_2_R[i] = strat->S_2_R[i-1];
+  if (atS <= strat->sl)
+  {
+#ifdef ENTER_USE_MEMMOVE
+// #if 0
+    memmove(&(strat->S[atS+1]), &(strat->S[atS]), 
+            (strat->sl - atS + 1)*sizeof(poly));
+    memmove(&(strat->ecartS[atS+1]), &(strat->ecartS[atS]), 
+            (strat->sl - atS + 1)*sizeof(int));
+    memmove(&(strat->sevS[atS+1]), &(strat->sevS[atS]), 
+            (strat->sl - atS + 1)*sizeof(unsigned long));
+    memmove(&(strat->S_2_R[atS+1]), &(strat->S_2_R[atS]), 
+            (strat->sl - atS + 1)*sizeof(int));
+#else    
+    for (i=strat->sl+1; i>=atS+1; i--)
+    {
+      strat->S[i] = strat->S[i-1];
+      strat->ecartS[i] = strat->ecartS[i-1];
+      strat->sevS[i] = strat->sevS[i-1];
+      strat->S_2_R[i] = strat->S_2_R[i-1];
+    }
+#endif
   }
   if (strat->fromQ!=NULL)
@@ -3405 +3598 @@
   assume(strat->tailRing == p.tailRing);
   assume(p.pLength == 0 || pLength(p.p) == p.pLength);
+  assume(p.FDeg == p.pFDeg());
+  assume(!p.is_normalized || nIsOne(pGetCoeff(p.p)));
 
   strat->newt = TRUE;
@@ -3411 +3606 @@
   if (strat->tl == strat->tmax-1) 
     enlargeT(strat->T,strat->R,strat->sevT,strat->tmax,setmax);
-  for (i=strat->tl+1; i>=atT+1; i--)
-  {
-    strat->T[i] = strat->T[i-1];
-    strat->sevT[i] = strat->sevT[i-1];
-    strat->R[strat->T[i].i_r] = &(strat->T[i]);
+  if (atT <= strat->tl)
+  {
+#ifdef ENTER_USE_MEMMOVE
+    memmove(&(strat->T[atT+1]), &(strat->T[atT]), 
+            (strat->tl-atT+1)*sizeof(TObject));
+    memmove(&(strat->sevT[atT+1]), &(strat->sevT[atT]), 
+            (strat->tl-atT+1)*sizeof(unsigned long));
+#endif
+    for (i=strat->tl+1; i>=atT+1; i--)
+    {
+#ifndef ENTER_USE_MEMMOVE
+      strat->T[i] = strat->T[i-1];
+      strat->sevT[i] = strat->sevT[i-1];
+#endif
+      strat->R[strat->T[i].i_r] = &(strat->T[i]);
+    }
   }
 
@@ -3433 +3639 @@
     strat->T[atT].max = NULL;
 
-  strat->T[atT].FDeg = p.pFDeg();
   strat->tl++;
   strat->R[strat->tl] = &(strat->T[atT]);
@@ -3467 +3672 @@
     else              PrintS("ideal/module is not homogeneous\n");
   }
+}
+
+BOOLEAN kPosInLDependsOnLength(int (*pos_in_l)
+                               (const LSet set, const int length,
+                                LObject* L,const kStrategy strat))
+{
+  if (pos_in_l == posInL110 ||
+      pos_in_l == posInL10) 
+    return TRUE;
+
+  return FALSE;
 }
 
@@ -3539 +3755 @@
   else if (BTEST1(12) || BTEST1(14) || BTEST1(16) || BTEST1(18))
     strat->posInT = posInT1;
+  strat->posInLDependsOnLength = kPosInLDependsOnLength(strat->posInL);
 }
 
@@ -3780 +3997 @@
  *
  ***************************************************************/
-BOOLEAN kCheckSpolyCreation(kStrategy strat, 
-                            poly &m1, poly &m2)
-{
-  assume(pNext(strat->P.p) == strat->tail);
-  assume(strat->P.p1 != NULL && strat->P.p2 != NULL);
-  assume(strat->P.i_r1 >= 0 && strat->P.i_r1 <= strat->tl);
-  assume(strat->P.i_r2 >= 0 && strat->P.i_r2 <= strat->tl);
+BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
+{
+  assume(L->p1 != NULL && L->p2 != NULL);
+  assume(L->i_r1 >= 0 && L->i_r1 <= strat->tl);
+  assume(L->i_r2 >= 0 && L->i_r2 <= strat->tl);
   assume(strat->tailRing != currRing);
   
-  if (! k_GetLeadTerms(strat->P.p1, strat->P.p2, currRing,
-                       m1, m2, strat->tailRing))
+  if (! k_GetLeadTerms(L->p1, L->p2, currRing, m1, m2, strat->tailRing))
     return FALSE;
-  poly p1_max = (strat->R[strat->P.i_r1])->max;
-  poly p2_max = (strat->R[strat->P.i_r2])->max;
+  poly p1_max = (strat->R[L->i_r1])->max;
+  poly p2_max = (strat->R[L->i_r2])->max;
   
   if ((p1_max != NULL && !p_LmExpVectorAddIsOk(m1, p1_max, strat->tailRing)) ||

Singular/kutil.h

@@ -4 +4 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: kutil.h,v 1.44 2000-11-16 09:54:52 obachman Exp $ */
+/* $Id: kutil.h,v 1.45 2000-11-23 17:34:10 obachman Exp $ */
 /*
 * ABSTRACT: kernel: utils for kStd
@@ -119 +119 @@
   
   poly  lcm;   /*- the lcm of p1,p2 -*/
+  poly last;   // pLast(p) during reductions
   kBucket_pt bucket;
   int   i_r1, i_r2;
@@ -134 +135 @@
 
   // spoly related things
+  // preparation for reduction if not spoly
+  KINLINE void PrepareRed(BOOLEAN use_bucket);
   KINLINE void SetLmTail(poly lm, poly new_p, int length, 
-                         int use_bucket, ring r);
+                         int use_bucket, ring r, poly last);
   KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
   KINLINE void Tail_Mult_nn(number n);
+  // deletes bucket, makes sure that p and t_p exists
   KINLINE poly GetP(omBin lmBin = NULL);
-  KINLINE void CanonicalizeP();
-  
+  // does not delete bucket, just canonicalizes it
+  // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
+  KINLINE poly CanonicalizeP();
+  
+  // makes a copy of the poly of L
+  KINLINE void Copy();
+  // gets the poly and makes a copy of it
+  KINLINE poly CopyGetP();
+
+  KINLINE int GetpLength();
+  KINLINE long pLDeg(BOOLEAN use_last);
   KINLINE long pLDeg();
-  KINLINE long SetLength();
+  KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
   KINLINE long SetDegStuffReturnLDeg();
+  KINLINE long SetDegStuffReturnLDeg(BOOLEAN use_last);
 
   KINLINE long MinComp();
@@ -176 +190 @@
   int (*posInT)(const TSet T,const int tl,const LObject &h);
   int (*posInL)(const LSet set, const int length,
-                const LObject &L,const kStrategy strat);
+                LObject* L,const kStrategy strat);
   void (*enterS)(LObject h, int pos,kStrategy strat, int atR = -1);
   void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
   int (*posInLOld)(const LSet Ls,const int Ll,
-                   const LObject &Lo,const kStrategy strat);
+                   LObject* Lo,const kStrategy strat);
+  pFDegProc pOrigFDeg;
+  pLDegProc pOrigLDeg;
   pFDegProc pOldFDeg;
   ideal Shdl;
@@ -204 +220 @@
   pShallowCopyDeleteProc p_shallow_copy_delete;
   BOOLEAN *pairtest;/*used for enterOnePair*/
+  // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
+  BOOLEAN LDegLast;
+  // if set, then L.length == L.pLength
+  BOOLEAN length_pLength;
+  // if set, then posInL does not depend on L.length
+  BOOLEAN posInLDependsOnLength;
   int cp,c3;
   int sl,mu;
@@ -246 +268 @@
 
 void deleteHC(poly *p, int *e, int *l, kStrategy strat);
+void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
 void deleteInS (int i,kStrategy strat);
 void cleanT (kStrategy strat);
@@ -265 +288 @@
 void reorderS (int* suc,kStrategy strat);
 int posInL0 (const LSet set, const int length,
-             const LObject &L,const kStrategy strat);
+             LObject* L,const kStrategy strat);
 int posInL11 (const LSet set, const int length,
-             const LObject &L,const kStrategy strat);
+             LObject* L,const kStrategy strat);
 int posInL13 (const LSet set, const int length,
-             const LObject &L,const kStrategy strat);
+             LObject* L,const kStrategy strat);
 int posInL15 (const LSet set, const int length,
-             const LObject &L,const kStrategy strat);
+             LObject* L,const kStrategy strat);
 int posInL17 (const LSet set, const int length,
-             const LObject &L,const kStrategy strat);
+             LObject* L,const kStrategy strat);
+int posInL10 (const LSet set, const int length,
+             LObject* L,const kStrategy strat);
 KINLINE poly redtailBba (poly p,int pos,kStrategy strat);
 poly redtailBba (LObject *L, int pos,kStrategy strat);
 poly redtail (poly p,int pos,kStrategy strat);
+poly redtail (LObject *L,int pos,kStrategy strat);
 void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
 void entersets (LObject h);
@@ -296 +322 @@
 void cancelunit (LObject* p);
 void HEckeTest (poly pp,kStrategy strat);
-void redtailS (poly* h,int maxIndex);
-void redtailMora (poly* h,int maxIndex);
 void initBuchMoraCrit(kStrategy strat);
 void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
@@ -314 +338 @@
 //        number of first divisor, otherwise
 int kFindDivisibleByInT(const TSet &T, const unsigned long* sevT, 
-                        const int tl, const LObject* L);
+                        const int tl, const LObject* L, const int start=0);
 // same with S
 int kFindDivisibleByInS(const polyset &S, const unsigned long* sev, 
@@ -460 +484 @@
 //             exponent bound of strat->tailRing
 //      FALSE, otherwise
-BOOLEAN kCheckSpolyCreation(kStrategy strat, poly &m1, poly &m2);
+BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
 // change strat->tailRing and adjust all data in strat, L, and T: 
 // new tailRing has larger exponent bound 

Singular/pInline0.h

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: pInline0.h,v 1.4 2000-11-08 15:34:59 obachman Exp $
+ *  Version: $Id: pInline0.h,v 1.5 2000-11-23 17:34:11 obachman Exp $
  *******************************************************************/
 #ifndef PINLINE0_H
@@ -41 +41 @@
 }
 
-
 // returns minimal column number in the modul element a (or 0)
-PINLINE0 int p_MinComp(poly p, ring r)
+PINLINE0 long p_MinComp(poly p, ring lmRing, ring tailRing)
 {
-  int result,i;
+  long result,i;
 
   if(p==NULL) return 0;
-  result = p_GetComp(p,r);
-  while (pNext(p)!=NULL)
+  result = p_GetComp(p,lmRing);
+  if (result != 0)
   {
-    pIter(p);
-    i = p_GetComp(p,r);
-    if (i<result) result = i;
+    while (pNext(p)!=NULL)
+    {
+      pIter(p);
+      i = p_GetComp(p,tailRing);
+      if (i<result) result = i;
+    }
   }
   return result;
@@ -61 +63 @@
 PINLINE0 long p_MaxComp(poly p, ring lmRing, ring tailRing)
 {
-  int result,i;
+  long result,i;
 
   if(p==NULL) return 0;
   result = p_GetComp(p, lmRing);
-  while (pNext(p)!=NULL)
+  if (result != 0) 
   {
-    pIter(p);
-    i = p_GetComp(p, tailRing);
-    if (i>result) result = i;
+    while (pNext(p)!=NULL)
+    {
+      pIter(p);
+      i = p_GetComp(p, tailRing);
+      if (i>result) result = i;
+    }
   }
   return result;
@@ -113 +118 @@
 }
 
+/*2
+* returns the length of a (numbers of monomials)
+*/
+PINLINE0 poly pLast(poly a, int &l)
+{
+  if (a == NULL) 
+  {
+    l = 0;
+    return NULL;
+  }
+  l = 1;
+  while (pNext(a)!=NULL)
+  {
+    pIter(a);
+    l++;
+  }
+  return a;
+}
+
 #endif // PINLINE_CC
 

Singular/pInline2.h

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: pInline2.h,v 1.17 2000-11-13 14:50:24 levandov Exp $
+ *  Version: $Id: pInline2.h,v 1.18 2000-11-23 17:34:11 obachman Exp $
  *******************************************************************/
 #ifndef PINLINE2_H
@@ -465 +465 @@
 PINLINE2 poly pp_Mult_mm(poly p, poly m, const ring r)
 {
-  return r->p_Procs->pp_Mult_mm(p, m, NULL, r);
+  poly last;
+  int shorter;
+  return r->p_Procs->pp_Mult_mm(p, m, shorter, NULL, r, last);
 }
 
@@ -478 +480 @@
 {
   int shorter;
-  return r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r);
+  poly last;
+  return r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r, last);
 }
 PINLINE2 poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, int &lp, int lq,
@@ -484 +487 @@
 {
   int shorter;
-  poly res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, spNoether, r);
+  poly last;
+  poly res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, spNoether, r, last);
   lp = (lp + lq) - shorter;
   return res;
@@ -538 +542 @@
 PINLINE2 poly pp_Mult_qq(poly p, poly q, const ring r)
 {
+  poly last;
+  int shorter;
   if (p == NULL || q == NULL) return NULL;
 
   if (pNext(p) == NULL)
-    return r->p_Procs->pp_Mult_mm(q, p, NULL, r);
+    return r->p_Procs->pp_Mult_mm(q, p, shorter, NULL, r, last);
 
   if (pNext(q) == NULL)
-    return r->p_Procs->pp_Mult_mm(p, q, NULL, r);
+    return r->p_Procs->pp_Mult_mm(p, q, shorter, NULL, r, last);
 
   poly qq = q;
@@ -560 +566 @@
 PINLINE2 poly p_Plus_mm_Mult_qq(poly p, poly m, poly q, const ring r)
 {
-  poly res;
+  poly res, last;
   int shorter;
   number n_old = pGetCoeff(m);
@@ -567 +573 @@
   pSetCoeff0(m, n_neg);
 
-  res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r);
+  res = r->p_Procs->p_Minus_mm_Mult_qq(p, m, q, shorter, NULL, r, last);
   pSetCoeff0(m, n_old);
   n_Delete(&n_neg, r);

Singular/p_Minus_mm_Mult_qq__Template.cc

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: p_Minus_mm_Mult_qq__Template.cc,v 1.6 2000-11-03 14:50:21 obachman Exp $
+ *  Version: $Id: p_Minus_mm_Mult_qq__Template.cc,v 1.7 2000-11-23 17:34:11 obachman Exp $
  *******************************************************************/
 
@@ -18 +18 @@
  * 
  ***************************************************************/
-poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, int& Shorter, const poly spNoether, const ring r)
+poly p_Minus_mm_Mult_qq(poly p, poly m, poly q, int& Shorter, const poly spNoether, const ring r, poly &last)
 {
   p_Test(p, r);
@@ -105 +105 @@
   a = pNext(a) = p;// append p to result and advance p
   pIter(p);
-  if (p == NULL) goto Finish;;
+  if (p == NULL) goto Finish;
   goto CmpTop;
  
@@ -111 +111 @@
   Finish: // q or p is NULL: Clean-up time
   if (q == NULL) // append rest of p to result
+  {
     pNext(a) = p;
+    if (p == NULL) last = a;
+  }
   else  // append (- m*q) to result
   {
     pSetCoeff0(m, tneg);
-    pNext(a) = r->p_Procs->pp_Mult_mm(q, m, spNoether, r);
+    last = a;
+    pNext(a) = r->p_Procs->pp_Mult_mm(q, m, shorter, spNoether, r, last);
     pSetCoeff0(m, tm);
   }

Singular/p_Mult_q.cc

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: p_Mult_q.cc,v 1.5 2000-09-18 09:19:26 obachman Exp $
+ *  Version: $Id: p_Mult_q.cc,v 1.6 2000-11-23 17:34:11 obachman Exp $
  *******************************************************************/
 #include "mod2.h"
@@ -95 +95 @@
 }
 
-#if 0
-poly _p_Mult_q(poly p, poly q, const int copy, const ring r)
-{
-  pAssume (p != NULL && pNext(p) != NULL && q != NULL && pNext(q) != NULL);
-  
-  // to minimize the number of polynomial comparisons
-  // we reverse p and should arrange p and q such that
-  // pLast(p)*pHead(q) > pHead(p)*pLast(q)
-  // as a first approximation, we just compare the head terms
-#if 0  
-  if (p_LmCmp(p, q, r) == -1)
-  {
-    poly tmp = q;
-    q = p;
-    p = tmp;
-  }
-  p = r->p_Procs->p_ReverseNeg(p, r);
-#endif
-
-  poly pp = p;
-  int shorter;
-  p_Minus_mm_Mult_qq_Proc_Ptr p_minus_mm_mult_qq 
-    =  r->p_Procs->p_Minus_mm_Mult_qq;
-  poly pr = NULL;
-
-  while (pp != NULL)
-  {
-    pr = p_minus_mm_mult_qq(pr, pp, q, shorter, NULL, r);
-    pIter(pp);
-  }
-  
-  if (copy)
-  {
-    r->p_Procs->p_ReverseNeg(p, r);
-  }
-  else
-  {
-    r->p_Procs->p_Delete(&q, r);
-    r->p_Procs->p_Delete(&p, r);
-  }
-  return pr;
-}
-
-  
-  
-#endif

Singular/p_Procs.h

@@ -8 +8 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: p_Procs.h,v 1.7 2000-11-03 14:50:22 obachman Exp $
+ *  Version: $Id: p_Procs.h,v 1.8 2000-11-23 17:34:12 obachman Exp $
  *******************************************************************/
 #ifndef P_PROCS_H
@@ -22 +22 @@
 typedef poly (*p_Mult_mm_Proc_Ptr)(poly p, poly m, const ring r);
 typedef poly (*pp_Mult_mm_Proc_Ptr)(poly p, poly m, 
-                                   poly spNoether, const ring r);
+                                    int &shorter, poly spNoether, 
+                                    const ring r, 
+                                    poly &last);
 typedef poly (*p_Add_q_Proc_Ptr)(poly p, poly q, int & shorter, const ring r);
 typedef poly (*p_Minus_mm_Mult_qq_Proc_Ptr)(poly p, poly m, poly q, 
-                                                int &shorter, poly spNoether, 
-                                                const ring r);
+                                            int &shorter, poly spNoether, 
+                                            const ring r, poly &last);
 typedef poly (*p_Neg_Proc_Ptr)(poly p, const ring r);
 typedef poly (*pp_Mult_Coeff_mm_DivSelect_Proc_Ptr)(poly p, const poly m, const ring r);

Singular/p_polys.cc

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: p_polys.cc,v 1.9 2000-11-14 16:04:59 obachman Exp $
+ *  Version: $Id: p_polys.cc,v 1.10 2000-11-23 17:34:12 obachman Exp $
  *******************************************************************/
 
@@ -169 +169 @@
 * the ordering is compatible with degree, use a->order
 */
-long pDeg(poly a, ring r)
+inline long _pDeg(poly a, ring r)
 {
   p_LmCheckPolyRing(a, r);
   assume(p_GetOrder(a, r) == pWTotaldegree(a, r));
   return p_GetOrder(a, r);
+}
+
+long pDeg(poly a, ring r)
+{
+  return _pDeg(a, r);
 }
 
@@ -182 +187 @@
 * the ordering is not compatible with degree so do not use p->Order
 */
-long pTotaldegree(poly p, ring r)
+inline long _pTotaldegree(poly p, ring r)
 {
   p_LmCheckPolyRing(p, r);
   return (long) p_ExpVectorQuerSum(p, r);
+}
+long pTotaldegree(poly p, ring r)
+{
+  return (long) _pTotaldegree(p, r);
 }
 
@@ -295 +304 @@
   int ll=1;
 
-  while ((pNext(p)!=NULL) && (p_GetComp(pNext(p), r)==k))
-  {
-    pIter(p);
-    ll++;
+  if (k > 0)
+  {
+    while ((pNext(p)!=NULL) && (p_GetComp(pNext(p), r)==k))
+    {
+      pIter(p);
+      ll++;
+    }
+  }
+  else
+  {
+     while (pNext(p)!=NULL)
+     {
+       pIter(p);
+       ll++;
+     }
   }
   *l=ll;
@@ -354 +374 @@
   int ll=1;
 
-  while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
-  {
-    ll++;
+  if (k != 0)
+  {
+    while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
+    {
+      ll++;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p)) !=NULL)
+    {
+      ll++;
+    }
   }
   *l=ll;
@@ -374 +404 @@
   long  t,max;
 
-  max=pFDeg(p);
-  while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
-  {
-    t=pFDeg(p, r);
-    if (t>max) max=t;
-    ll++;
+  max=pFDeg(p, r);
+  if (k > 0)
+  {
+    while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
+    {
+      t=pFDeg(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      t=pFDeg(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
   }
   *l=ll;
@@ -398 +440 @@
 
   max=pFDeg(p, r);
-  while ((p=pNext(p))!=NULL)
-  {
-    if (! rIsSyzIndexRing(r) ||
-        (p_GetComp(p, r)<=rGetCurrSyzLimit(r)))
-    {
-       if ((t=pFDeg(p, r))>max) max=t;
-       ll++;
-    }
-    else break;
+  if (rIsSyzIndexRing(r))
+  {
+    long limit = rGetCurrSyzLimit(r);
+    while ((p=pNext(p))!=NULL)
+    {
+      if (p_GetComp(p, r)<=limit)
+      {
+        if ((t=pFDeg(p, r))>max) max=t;
+        ll++;
+      }
+      else break;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      if ((t=pFDeg(p, r))>max) max=t;
+      ll++;
+    }
+  }
+  *l=ll;
+  return max;
+}
+
+// like pLDeg1, only pFDeg == Deg
+long pLDeg1_Deg(poly p,int *l, ring r)
+{
+  p_CheckPolyRing(p, r);
+  Exponent_t k= p_GetComp(p, r);
+  int ll=1;
+  long  t,max;
+
+  max=_pDeg(p, r);
+  if (k > 0)
+  {
+    while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
+    {
+      t=_pDeg(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      t=_pDeg(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
+  }
+  *l=ll;
+  return max;
+}
+
+long pLDeg1c_Deg(poly p,int *l, ring r)
+{
+  p_CheckPolyRing(p, r);
+  int ll=1;
+  long  t,max;
+
+  max=_pDeg(p, r);
+  if (rIsSyzIndexRing(r))
+  {
+    long limit = rGetCurrSyzLimit(r);
+    while ((p=pNext(p))!=NULL)
+    {
+      if (p_GetComp(p, r)<=limit)
+      {
+        if ((t=_pDeg(p, r))>max) max=t;
+        ll++;
+      }
+      else break;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      if ((t=_pDeg(p, r))>max) max=t;
+      ll++;
+    }
+  }
+  *l=ll;
+  return max;
+}
+
+// like pLDeg1, only pFDeg == pTotoalDegree
+long pLDeg1_Totaldegree(poly p,int *l, ring r)
+{
+  p_CheckPolyRing(p, r);
+  Exponent_t k= p_GetComp(p, r);
+  int ll=1;
+  long  t,max;
+
+  max=_pTotaldegree(p, r);
+  if (k > 0)
+  {
+    while (((p=pNext(p))!=NULL) && (p_GetComp(p, r)==k))
+    {
+      t=_pTotaldegree(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      t=_pTotaldegree(p, r);
+      if (t>max) max=t;
+      ll++;
+    }
+  }
+  *l=ll;
+  return max;
+}
+
+long pLDeg1c_Totaldegree(poly p,int *l, ring r)
+{
+  p_CheckPolyRing(p, r);
+  int ll=1;
+  long  t,max;
+
+  max=_pTotaldegree(p, r);
+  if (rIsSyzIndexRing(r))
+  {
+    long limit = rGetCurrSyzLimit(r);
+    while ((p=pNext(p))!=NULL)
+    {
+      if (p_GetComp(p, r)<=limit)
+      {
+        if ((t=_pTotaldegree(p, r))>max) max=t;
+        ll++;
+      }
+      else break;
+    }
+  }
+  else
+  {
+    while ((p=pNext(p))!=NULL)
+    {
+      if ((t=_pTotaldegree(p, r))>max) max=t;
+      ll++;
+    }
   }
   *l=ll;
@@ -533 +712 @@
   return TRUE;
 }
+
+/*2
+*test if a monomial /head term is a pure power
+*/
+int p_IsPurePower(const poly p, const ring r)
+{
+  int i,k=0;
+
+  for (i=r->N;i;i--)
+  {
+    if (p_GetExp(p,i, r)!=0)
+    {
+      if(k!=0) return 0;
+      k=i;
+    }
+  }
+  return k;
+}

Singular/p_polys.h

@@ -8 +8 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 9/00
- *  Version: $Id: p_polys.h,v 1.14 2000-11-14 16:05:00 obachman Exp $
+ *  Version: $Id: p_polys.h,v 1.15 2000-11-23 17:34:12 obachman Exp $
  *******************************************************************/
 #ifndef P_POLYS_H
@@ -214 +214 @@
 // return TRUE if all monoms have the same component
 BOOLEAN   p_OneComp(poly p, ring r);
+int       p_IsPurePower(const poly p, const ring r);
+
 /***************************************************************
  *
@@ -299 +301 @@
 PINLINE0   long p_MaxComp(poly p, ring lmRing, ring tailRing);
 inline long p_MaxComp(poly p,ring lmRing) {return p_MaxComp(p,lmRing,lmRing);}
-PINLINE0   int  p_MinComp(poly p, ring r);
+PINLINE0   long p_MinComp(poly p, ring lmRing, ring tailRing);
+inline long p_MinComp(poly p,ring lmRing) {return p_MinComp(p,lmRing,lmRing);}
 
 /***************************************************************
@@ -307 +310 @@
  ***************************************************************/
 PINLINE0 int       pLength(poly a);
+PINLINE0 poly      pLast(poly a, int &length);
+inline   poly      pLast(poly a) { int l; return pLast(a, l);}
 PINLINE0 poly pReverse(poly p);
 
@@ -346 +351 @@
 long pLDeg1(poly p,int *l, ring r);
 long pLDeg1c(poly p,int *l, ring r);
+long pLDeg1_Deg(poly p,int *l, ring r);
+long pLDeg1c_Deg(poly p,int *l, ring r);
+long pLDeg1_Totaldegree(poly p,int *l, ring r);
+long pLDeg1c_Totaldegree(poly p,int *l, ring r);
 
 /***************************************************************

Singular/polys.h

@@ -4 +4 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: polys.h,v 1.45 2000-11-14 16:05:00 obachman Exp $ */
+/* $Id: polys.h,v 1.46 2000-11-23 17:34:12 obachman Exp $ */
 /*
 * ABSTRACT - all basic methods to manipulate polynomials of the
@@ -237 +237 @@
 BOOLEAN   pIsConstant(const poly p);
 BOOLEAN   pIsConstantPoly(poly p);
-int       pIsPurePower(const poly p);
+#define   pIsPurePower(p)   p_IsPurePower(p, currRing)
 #define   pIsVector(p)     (pGetComp(p)!=0)
 BOOLEAN   pHasNotCF(poly p1, poly p2);   /*has no common factor ?*/
@@ -270 +270 @@
 long pLDeg1(poly p,int *l, ring r = currRing);
 long pLDeg1c(poly p,int *l, ring r = currRing);
+long pLDeg1_Deg(poly p,int *l, ring r = currRing);
+long pLDeg1c_Deg(poly p,int *l, ring r = currRing);
+long pLDeg1_Totaldegree(poly p,int *l, ring r = currRing);
+long pLDeg1c_Totaldegree(poly p,int *l, ring r = currRing);
 
 /*-------------pComp for syzygies:-------------------*/

Singular/polys1.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: polys1.cc,v 1.53 2000-11-14 16:05:00 obachman Exp $ */
+/* $Id: polys1.cc,v 1.54 2000-11-23 17:34:13 obachman Exp $ */
 
 /*
@@ -62 +62 @@
 }
 
-/*2
-*test if a monomial /head term is a pure power
-*/
-int pIsPurePower(const poly p)
-{
-  int i,k=0;
-
-  for (i=pVariables;i;i--)
-  {
-    if (pGetExp(p,i)!=0)
-    {
-      if(k!=0) return 0;
-      k=i;
-    }
-  }
-  return k;
-}
 
 

Singular/pp_Mult_mm__Template.cc

@@ -7 +7 @@
  *  Author:  obachman (Olaf Bachmann)
  *  Created: 8/00
- *  Version: $Id: pp_Mult_mm__Template.cc,v 1.6 2000-10-30 16:54:56 obachman Exp $
+ *  Version: $Id: pp_Mult_mm__Template.cc,v 1.7 2000-11-23 17:34:13 obachman Exp $
  *******************************************************************/
 
@@ -18 +18 @@
  *
  ***************************************************************/
-poly pp_Mult_mm(poly p, const poly m, const poly spNoether, const ring ri)
+poly pp_Mult_mm(poly p, const poly m, int& Shorter, const poly spNoether, const ring ri, poly &last)
 {
   p_Test(p, ri);
   p_LmTest(m, ri);
-  if (p == NULL) return NULL;
+  if (p == NULL) 
+  {
+    last = NULL;
+    return NULL;
+  }
   spolyrec rp;
   poly q = &rp, r;
@@ -45 +49 @@
     }
     while (p != NULL);
+    last = q;
   }
   else
@@ -56 +61 @@
       if (p_LmCmp(r, spNoether, ri) == -1)
       {
+        Shorter += pLength(p);
         p_FreeBinAddr(r, ri);
         break;
@@ -63 +69 @@
       pIter(p);
     }
+    if (q  != &rp) last = q;
   }
   pNext(q) = NULL;
-  
+
   p_Test(pNext(&rp), ri);
   return pNext(&rp);

Singular/ring.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: ring.cc,v 1.144 2000-11-23 14:06:50 Singular Exp $ */
+/* $Id: ring.cc,v 1.145 2000-11-23 17:34:13 obachman Exp $ */
 
 /*
@@ -2631 +2631 @@
     {
       // Hmm... sometimes (e.g., from maGetPreimage) new variables
-      // are intorduced, but their name is never set
-      // hence, do the following awkward trick
+      // are intorduced, but their names are never set
+      // hence, we do the following awkward trick
       int N = omSizeWOfAddr(r->names);
       if (r->N < N) N = r->N;
@@ -2707 +2707 @@
   r->ComponentOrder = 1;
   r->pFDeg = pTotaldegree;
-  r->pLDeg = (r->OrdSgn == 1 ? r->pLDeg = pLDegb : pLDeg0);
+  r->pLDeg = (r->OrdSgn == 1 ? pLDegb : pLDeg0);
 
   /*======== ordering type is (_,c) =========================*/
@@ -2743 +2743 @@
   &&  (order[2]==0))
   {
-    /* pLDeg = ldeg0; is standard*/
     if ((order[0]==ringorder_C)||(order[0]==ringorder_S)||
         order[0]==ringorder_s)