Changeset e3dc1c in git


Ignore:
Timestamp:
Dec 18, 2000, 6:26:41 PM (23 years ago)
Author:
Olaf Bachmann <obachman@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
10a0c5ef3797be1dba4c637d3391ac548ba28b46
Parents:
b39d4dc5adb2ce64a3babd5df6ac99eb7f4ed311
Message:
* new strat and option(prot) for std


git-svn-id: file:///usr/local/Singular/svn/trunk@4934 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • Singular/kstd1.cc

    rb39d4d re3dc1c  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kstd1.cc,v 1.73 2000-12-18 13:30:35 obachman Exp $ */
     4/* $Id: kstd1.cc,v 1.74 2000-12-18 17:26:39 obachman Exp $ */
    55/*
    66* ABSTRACT:
     
    438438#endif
    439439          h->Clear();
    440           return 0;
     440          return -1;
    441441        }
    442442      }
  • Singular/kutil.cc

    rb39d4d re3dc1c  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: kutil.cc,v 1.84 2000-12-18 13:30:37 obachman Exp $ */
     4/* $Id: kutil.cc,v 1.85 2000-12-18 17:26:40 obachman Exp $ */
    55/*
    66* ABSTRACT: kernel: utils for kStd
     
    2828// system memmove -- it does not seem to pay off, though
    2929// #define ENTER_USE_MYMEMMOVE
    30 
    31 // define if redtailBba should use buckets
    32 #define HAVE_REDTAIL_BUCKETS
    3330
    3431#include "tok.h"
     
    18861883}
    18871884
    1888 // determines the position based on: 1.) Ecart 2.) FDeg 3.) pLength
    1889 int posInT_EcartFDegpLength(const TSet set,const int length,const LObject &p)
    1890 {
    1891 
    1892   if (length==-1) return 0;
    1893 
    1894   int o = p.ecart;
    1895   int op=p.GetpFDeg();
    1896   int ol = p.GetpLength();
    1897 
    1898   if (set[length].ecart < o)
    1899     return length+1;
    1900   if (set[length].ecart == o)
    1901   {
    1902      int oo=set[length].GetpFDeg();
    1903      if ((oo < op) || ((oo==op) && (set[length].length < ol)))
    1904        return length+1;
    1905   }
    1906 
    1907   int i;
    1908   int an = 0;
    1909   int en= length;
    1910   loop
    1911   {
    1912     if (an >= en-1)
    1913     {
    1914       if (set[an].ecart > o)
    1915         return an;
    1916       if (set[an].ecart == o)
    1917       {
    1918          int oo=set[an].GetpFDeg();
    1919          if((oo > op)
    1920          || ((oo==op) && (set[an].pLength > ol)))
    1921            return an;
    1922       }
    1923       return en;
    1924     }
    1925     i=(an+en) / 2;
    1926     if (set[i].ecart > o)
    1927       en=i;
    1928     else if (set[i].ecart == o)
    1929     {
    1930        int oo=set[i].GetpFDeg();
    1931        if ((oo > op)
    1932        || ((oo == op) && (set[i].pLength > ol)))
    1933          en=i;
    1934        else
    1935         an=i;
    1936     }
    1937     else
    1938       an=i;
    1939   }
    1940 }
    1941 
    1942 // determines the position based on: 1.) FDeg 2.) pLength
    1943 int posInT_FDegpLength(const TSet set,const int length,const LObject &p)
    1944 {
    1945 
    1946   if (length==-1) return 0;
    1947 
    1948   int op=p.GetpFDeg();
    1949   int ol = p.GetpLength();
    1950 
    1951   int oo=set[length].GetpFDeg();
    1952   if ((oo < op) || ((oo==op) && (set[length].length < ol)))
    1953     return length+1;
    1954 
    1955   int i;
    1956   int an = 0;
    1957   int en= length;
    1958   loop
    1959     {
    1960       if (an >= en-1)
    1961       {
    1962         int oo=set[an].GetpFDeg();
    1963         if((oo > op)
    1964            || ((oo==op) && (set[an].pLength > ol)))
    1965           return an;
    1966         return en;
    1967       }
    1968       i=(an+en) / 2;
    1969       int oo=set[i].GetpFDeg();
    1970       if ((oo > op)
    1971           || ((oo == op) && (set[i].pLength > ol)))
    1972         en=i;
    1973       else
    1974         an=i;
    1975     }
    1976 }
    1977 
    19781885// determines the position based on: 1.) Ecart 2.) pLength
    19791886int posInT_EcartpLength(const TSet set,const int length,const LObject &p)
     
    20091916        an=i;
    20101917    }
    2011 }
    2012 
    2013 // determines the position based on: 1.) Ecart 2.) FDeg 3.) pLength
    2014 int posInT_pLength(const TSet set,const int length,const LObject &p)
    2015 {
    2016   if (length==-1)
    2017     return 0;
    2018   if (set[length].length<p.length)
    2019     return length+1;
    2020 
    2021   int i;
    2022   int an = 0;
    2023   int en= length;
    2024   int ol = p.GetpLength();
    2025 
    2026   loop
    2027   {
    2028     if (an >= en-1)
    2029     {
    2030       if (set[an].pLength>ol) return an;
    2031       return en;
    2032     }
    2033     i=(an+en) / 2;
    2034     if (set[i].pLength>ol) en=i;
    2035     else                        an=i;
    2036   }
    20371918}
    20381919 
     
    28182699
    28192700
    2820 #ifndef OLD_REDTAIL_BBA
    28212701poly redtailBba (LObject* L, int pos, kStrategy strat, BOOLEAN withT)
    28222702{
     
    28382718  L->pLength = 1;
    28392719
    2840 #ifdef HAVE_REDTAIL_BUCKETS 
    28412720  Ln.PrepareRed(strat->use_buckets);
    2842 #endif
    28432721
    28442722  while(!Ln.IsNull())
     
    28922770  return L->GetLmCurrRing();
    28932771}
    2894 #else
    2895 poly redtailBba (LObject* L, int pos, kStrategy strat, BOOLEAN withT)
    2896 {
    2897   poly h, hn;
    2898   int j;
    2899   unsigned long not_sev;
    2900   strat->redTailChange=FALSE;
    2901   poly p = L->p;
    2902   LObject Ln(strat->tailRing);
    2903   TObject* With;
    2904   // placeholder in case strat->tl < 0
    2905   TObject  With_s(strat->tailRing);
    2906 
    2907   if (strat->noTailReduction)
    2908     return p;
    2909   h = p;
    2910   hn = pNext(h);
    2911   while(hn != NULL)
    2912   {
    2913     while (1)
    2914     {
    2915       Ln.Set(hn, strat->tailRing);
    2916       Ln.sev = p_GetShortExpVector(hn, strat->tailRing);
    2917       if (! withT)
    2918       {
    2919         With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
    2920         if (With == NULL) break;
    2921       }
    2922       else
    2923       {
    2924         int j = kFindDivisibleByInT(strat->T, strat->sevT, strat->tl, &Ln);
    2925         if (j < 0) break;
    2926         With = &(strat->T[j]);
    2927       }
    2928       if (ksReducePolyTail(L, With, h, strat->kNoether))
    2929       {
    2930         // reducing the tail would violate the exp bound
    2931         if (kStratChangeTailRing(strat, L))
    2932         {
    2933           p = redtailBba(L, pos, strat);
    2934           goto all_done;
    2935         }
    2936         else
    2937         {
    2938           assume(0);
    2939           return NULL;
    2940         }
    2941       }
    2942       strat->redTailChange=TRUE;
    2943       hn = pNext(h);
    2944       if (hn == NULL) goto all_done;
    2945     }
    2946     h = hn;
    2947     hn = pNext(h);
    2948   }
    2949 
    2950   all_done:
    2951   if (strat->redTailChange)
    2952   {
    2953     L->last = NULL;
    2954     L->pLength = 0;
    2955     L->length = 0;
    2956   }
    2957   return p;
    2958 }
    2959 #endif
     2772
    29602773/*2
    29612774*checks the change degree and write progress report
     
    29902803    else
    29912804    {
    2992       if (strat->Ll != *reduc)
     2805      if (strat->Ll != *reduc && strat->Ll > 0)
    29932806      {
    29942807        Print("(%d)",strat->Ll+1);
     
    39453758    {
    39463759      strat->posInL = posInL15;
    3947       strat->posInT = posInT15;
     3760      // ok -- here is the deal: from my experiments for Singular-2-0
     3761      // I conclude that that posInT_EcartpLength is the best of
     3762      // posInT15, posInT_EcartFDegpLength, posInT_FDegLength, posInT_pLength
     3763      // see the table at the end of this file
     3764      if (K_TEST_OPT_OLDSTD)
     3765        strat->posInT = posInT15;
     3766      else
     3767        strat->posInT = posInT_EcartpLength;
    39483768    }
    39493769    else if (pLexOrder && !TEST_OPT_INTSTRATEGY)
     
    43534173
    43544174#endif // KUTIL_CC
     4175
     4176#if 0
     4177Timings for the different possibilities of posInT:
     4178            T15     EDL     DL      EL      L       1-2-3
     4179Gonnet          43.26   42.30   38.34   41.98   38.40   100.04
     4180Hairer_2_1      1.11    1.15    1.04    1.22    1.08    4.7
     4181Twomat3         1.62    1.69    1.70    1.65    1.54    11.32
     4182ahml            4.48    4.03    4.03    4.38    4.96    26.50
     4183c7                  15.02       13.98   15.16   13.24   17.31   47.89
     4184c8                  505.09      407.46  852.76  413.21  499.19  n/a
     4185f855            12.65   9.27    14.97   8.78    14.23   33.12
     4186gametwo6        11.47   11.35   14.57   11.20   12.02   35.07
     4187gerhard_3       2.73    2.83    2.93    2.64    3.12    6.24
     4188ilias13         22.89   22.46   24.62   20.60   23.34   53.86
     4189noon8           40.68   37.02   37.99   36.82   35.59   877.16
     4190rcyclic_19      48.22   42.29   43.99   45.35   51.51   204.29
     4191rkat9           82.37   79.46   77.20   77.63   82.54   267.92
     4192schwarz_11      16.46   16.81   16.76   16.81   16.72   35.56
     4193test016         16.39   14.17   14.40   13.50   14.26   34.07
     4194test017         34.70   36.01   33.16   35.48   32.75   71.45
     4195test042         10.76   10.99   10.27   11.57   10.45   23.04
     4196test058         6.78    6.75    6.51    6.95    6.22    9.47
     4197test066         10.71   10.94   10.76   10.61   10.56   19.06
     4198test073         10.75   11.11   10.17   10.79   8.63    58.10
     4199test086         12.23   11.81   12.88   12.24   13.37   66.68
     4200test103         5.05    4.80    5.47    4.64    4.89    11.90
     4201test154         12.96   11.64   13.51   12.46   14.61   36.35
     4202test162         65.27   64.01   67.35   59.79   67.54   196.46
     4203test164         7.50    6.50    7.68    6.70    7.96    17.13
     4204virasoro        3.39    3.50    3.35    3.47    3.70    7.66
     4205#endif
     4206
     4207
     4208#ifdef HAVE_MORE_POS_IN_T
     4209// determines the position based on: 1.) Ecart 2.) FDeg 3.) pLength
     4210int posInT_EcartFDegpLength(const TSet set,const int length,const LObject &p)
     4211{
     4212
     4213  if (length==-1) return 0;
     4214
     4215  int o = p.ecart;
     4216  int op=p.GetpFDeg();
     4217  int ol = p.GetpLength();
     4218
     4219  if (set[length].ecart < o)
     4220    return length+1;
     4221  if (set[length].ecart == o)
     4222  {
     4223     int oo=set[length].GetpFDeg();
     4224     if ((oo < op) || ((oo==op) && (set[length].length < ol)))
     4225       return length+1;
     4226  }
     4227
     4228  int i;
     4229  int an = 0;
     4230  int en= length;
     4231  loop
     4232  {
     4233    if (an >= en-1)
     4234    {
     4235      if (set[an].ecart > o)
     4236        return an;
     4237      if (set[an].ecart == o)
     4238      {
     4239         int oo=set[an].GetpFDeg();
     4240         if((oo > op)
     4241         || ((oo==op) && (set[an].pLength > ol)))
     4242           return an;
     4243      }
     4244      return en;
     4245    }
     4246    i=(an+en) / 2;
     4247    if (set[i].ecart > o)
     4248      en=i;
     4249    else if (set[i].ecart == o)
     4250    {
     4251       int oo=set[i].GetpFDeg();
     4252       if ((oo > op)
     4253       || ((oo == op) && (set[i].pLength > ol)))
     4254         en=i;
     4255       else
     4256        an=i;
     4257    }
     4258    else
     4259      an=i;
     4260  }
     4261}
     4262
     4263// determines the position based on: 1.) FDeg 2.) pLength
     4264int posInT_FDegpLength(const TSet set,const int length,const LObject &p)
     4265{
     4266
     4267  if (length==-1) return 0;
     4268
     4269  int op=p.GetpFDeg();
     4270  int ol = p.GetpLength();
     4271
     4272  int oo=set[length].GetpFDeg();
     4273  if ((oo < op) || ((oo==op) && (set[length].length < ol)))
     4274    return length+1;
     4275
     4276  int i;
     4277  int an = 0;
     4278  int en= length;
     4279  loop
     4280    {
     4281      if (an >= en-1)
     4282      {
     4283        int oo=set[an].GetpFDeg();
     4284        if((oo > op)
     4285           || ((oo==op) && (set[an].pLength > ol)))
     4286          return an;
     4287        return en;
     4288      }
     4289      i=(an+en) / 2;
     4290      int oo=set[i].GetpFDeg();
     4291      if ((oo > op)
     4292          || ((oo == op) && (set[i].pLength > ol)))
     4293        en=i;
     4294      else
     4295        an=i;
     4296    }
     4297}
     4298
     4299
     4300// determines the position based on: 1.) Ecart 2.) FDeg 3.) pLength
     4301int posInT_pLength(const TSet set,const int length,const LObject &p)
     4302{
     4303  if (length==-1)
     4304    return 0;
     4305  if (set[length].length<p.length)
     4306    return length+1;
     4307
     4308  int i;
     4309  int an = 0;
     4310  int en= length;
     4311  int ol = p.GetpLength();
     4312
     4313  loop
     4314  {
     4315    if (an >= en-1)
     4316    {
     4317      if (set[an].pLength>ol) return an;
     4318      return en;
     4319    }
     4320    i=(an+en) / 2;
     4321    if (set[i].pLength>ol) en=i;
     4322    else                        an=i;
     4323  }
     4324}
     4325
     4326#endif
  • Singular/kutil.h

    rb39d4d re3dc1c  
    44*  Computer Algebra System SINGULAR     *
    55****************************************/
    6 /* $Id: kutil.h,v 1.48 2000-12-18 13:30:38 obachman Exp $ */
     6/* $Id: kutil.h,v 1.49 2000-12-18 17:26:41 obachman Exp $ */
    77/*
    88* ABSTRACT: kernel: utils for kStd
     
    2424// This disbales RedThrough, tailReductions against T (bba),
    2525// sets posInT = posInT15 (bba, strat->honey), and enables redFirst with LDeg
    26 #define HAVE_OLD_STD
     26// NOTE: the same effect can be achieved with option(oldStd)
     27// #define HAVE_OLD_STD
    2728
    2829#ifdef HAVE_OLD_STD
     
    306307int posInT17 (const TSet set,const int length,const LObject &p);
    307308int posInT19 (const TSet set,const int length,const LObject &p);
     309int posInT_EcartpLength(const TSet set,const int length,const LObject &p);
     310
     311#ifdef HAVE_MORE_POS_IN_T
     312int posInT_pLength(const TSet set,const int length,const LObject &p);
    308313int posInT_EcartFDegpLength(const TSet set,const int length,const LObject &p);
    309314int posInT_FDegpLength(const TSet set,const int length,const LObject &p);
    310 int posInT_EcartpLength(const TSet set,const int length,const LObject &p);
    311 int posInT_pLength(const TSet set,const int length,const LObject &p);
     315#endif
     316
    312317
    313318void reorderS (int* suc,kStrategy strat);
Note: See TracChangeset for help on using the changeset viewer.