Changeset 7724a3 in git


Ignore:
Timestamp:
Oct 24, 2002, 9:52:39 AM (21 years ago)
Author:
Michael Brickenstein <bricken@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
ec989caa0706a8f53442d9f6380c1d7cbd076081
Parents:
cae0b6dbd933345aaf77e7ea69081a445c804819
Message:
*bricken: algorithmic changes


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

Legend:

Unmodified
Added
Removed

  • Singular/tgb.cc

    rcae0b6 r7724a3  
    1717
    1818#define FULLREDUCTIONS
     19#define HALFREDUCTIONS
    1920#define HEAD_BIN
    2021//#define HOMOGENEOUS_EXAMPLE
    … …  
    3839#endif
    3940enum calc_state
    40 {
    41   UNCALCULATED,
    42   HASTREP,
    43   UNIMPORTANT
    44 };
     41  {
     42    UNCALCULATED,
     43    HASTREP,
     44    UNIMPORTANT
     45  };
    4546struct calc_dat
    4647{
    … …  
    5657  int* misses;
    5758  int_pair_node* soon_free;
    58   #ifdef HEAD_BIN
     59#ifdef HEAD_BIN
    5960  struct omBin_s*   HeadBin;
    60   #endif
     61#endif
    6162  int max_misses;
    6263  int found_i;
    … …  
    9293  start_j=-1;
    9394#ifndef HOMOGENEOUS_EXAMPLE
    94    if (c->misses_series>80){
    95      c->current_degree++;
    96      c->misses_series=0;
    97    }
     95  if (c->misses_series>80){
     96    c->current_degree++;
     97    c->misses_series=0;
     98  }
    9899#endif
    99100  start_i=c->continue_i;
    … …  
    102103  for (int i=start_i;i<c->n;i++){
    103104    if (c->T_deg[i]>c->current_degree)
    104     {
    105       c->skipped_pairs++;
    106       continue;
    107     }
     105      {
     106        c->skipped_pairs++;
     107        continue;
     108      }
    108109    for(int j=(i==start_i)?start_j+1:0;j<i;j++){
    109110      // printf("searching at %d,%d",i,j);
    … …  
    111112        c->skipped_pairs++;
    112113        break;
    113         }
     114      }
    114115      if (c->states[i][j]==UNCALCULATED){
    115116        if(c->deg[i][j]<=c->current_degree)
    116         {
    117           c->continue_i=c->found_i=i;
    118           c->continue_j=c->found_j=j;
    119           return true;
    120         }
    121           else
     117          {
     118            c->continue_i=c->found_i=i;
     119            c->continue_j=c->found_j=j;
     120            return true;
     121          }
     122        else
    122123          {
    123124            ++(c->skipped_pairs);
    … …  
    125126      }
    126127    }
    127       c->misses_counter=0;
     128    c->misses_counter=0;
    128129  }
    129130
    … …  
    148149        if(c->states[i][j]==UNCALCULATED){
    149150          if (c->deg[i][j]<=c->current_degree)
    150           {
    151             c->continue_i=c->found_i=i;
    152             c->continue_j=c->found_j=j;
    153             return true;
    154           }
     151            {
     152              c->continue_i=c->found_i=i;
     153              c->continue_j=c->found_j=j;
     154              return true;
     155            }
    155156          else
    156           {
    157             ++(c->skipped_pairs);
    158           }
     157            {
     158              ++(c->skipped_pairs);
     159            }
    159160        }
    160161      }
    … …  
    195196      strat->lenS[i] = strat->lenS[i-1];
    196197
    197     strat->S[new_pos]=p;
     198  strat->S[new_pos]=p;
    198199  strat->ecartS[new_pos]=ecart;
    199200  strat->sevS[new_pos]=sev;
    … …  
    215216  for (int n=0;((n<c->n) && (i_con[n]>=0));n++){
    216217    if (i_con[n]==j){
    217 //       curr_deg=pFDeg(lm);
    218 //       for(int z1=0;((z1<c->n) && (i_con[z1]>=0));z1++)
    219 //         for (int z2=z1+1;((z2<c->n)&&(i_con[z2]>=0));z2++)
    220 //         {
    221 //           pLcm(c->S->m[i_con[z1]], c->S->m[i_con[z2]], lm);
    222 //           pSetm(lm);
    223 //           if (pFDeg(lm)==curr_deg)
    224 //             now_t_rep(i_con[z1],i_con[z2],c);
    225 //         }
     218      //       curr_deg=pFDeg(lm);
     219      //       for(int z1=0;((z1<c->n) && (i_con[z1]>=0));z1++)
     220      //         for (int z2=z1+1;((z2<c->n)&&(i_con[z2]>=0));z2++)
     221      //         {
     222      //           pLcm(c->S->m[i_con[z1]], c->S->m[i_con[z2]], lm);
     223      //           pSetm(lm);
     224      //           if (pFDeg(lm)==curr_deg)
     225      //             now_t_rep(i_con[z1],i_con[z2],c);
     226      //         }
    226227      now_t_rep(i,j,c);
    227228      omfree(i_con);
    … …  
    253254      pSetm(lm);
    254255      if (pFDeg(lm)>=deciding_deg)
    255       {
    256         int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node));
    257         if (last!=NULL)
    258           last->next=h;
    259         else
    260           c->soon_free=h;
    261         h->next=NULL;
    262         h->a=i_con[m];
    263         h->b=j_con[n];
    264         last=h;
    265       }
     256        {
     257          int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node));
     258          if (last!=NULL)
     259            last->next=h;
     260          else
     261            c->soon_free=h;
     262          h->next=NULL;
     263          h->a=i_con[m];
     264          h->b=j_con[n];
     265          last=h;
     266        }
    266267      //      if ((comp_deg<curr_deg)
    267268      //  ||
    … …  
    304305            <=
    305306            c->misses[i_con[m]]+c->misses[j_con[n]])))
    306 //       if ((comp_deg<curr_deg)
    307 //           ||
    308 //           ((comp_deg==curr_deg) &&
    309 //            (c->lengths[i]+c->lengths[j]
    310 //             <=
    311 //             c->lengths[i_con[m]]+c->lengths[j_con[n]])))
    312 
    313       {
    314         curr_deg=comp_deg;
    315         i=i_con[m];
    316         j=j_con[n];
    317       }
     307        //       if ((comp_deg<curr_deg)
     308        //           ||
     309        //           ((comp_deg==curr_deg) &&
     310        //            (c->lengths[i]+c->lengths[j]
     311        //             <=
     312        //             c->lengths[i_con[m]]+c->lengths[j_con[n]])))
     313
     314        {
     315          curr_deg=comp_deg;
     316          i=i_con[m];
     317          j=j_con[n];
     318        }
    318319    }
    319320  }
    … …  
    379380  long neg_bounds_short= ~p_GetShortExpVector(bound,c->r);
    380381  // for (int i=0;i<c->n;i++){
    381 //     if (c->T_deg[i]>s) continue;
    382 //     if (i!=from){
    383 //       if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){
    384 //         cans[cans_length]=i;
    385 //         cans_length++;
    386 //       }
    387 //     }
    388 //   }
     382  //     if (c->T_deg[i]>s) continue;
     383  //     if (i!=from){
     384  //       if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){
     385  //         cans[cans_length]=i;
     386  //         cans_length++;
     387  //       }
     388  //     }
     389  //   }
    389390  int not_yet_found=cans_length;
    390391  int con_checked=0;
    … …  
    488489  c->continue_j=0;
    489490  c->skipped_i=-1;
    490   #ifdef HEAD_BIN
     491#ifdef HEAD_BIN
    491492  c->HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long));
    492   #endif
     493#endif
    493494  /* omUnGetSpecBin(&(c->HeadBin)); */
    494495  h=omalloc(n*sizeof(char*));
    … …  
    512513  c->short_Exps=(long*) omalloc(n*sizeof(long));
    513514  for (i=0;i<n;i++)
    514   {
    515   #ifdef HEAD_BIN
    516     c->S->m[i]=p_MoveHead(c->S->m[i],c->HeadBin);
    517   #endif
    518     c->T_deg[i]=pFDeg(c->S->m[i]);
    519     c->lengths[i]=pLength(c->S->m[i]);
    520     c->misses[i]=0;
    521     c->states[i]=(char *)omAlloc((i+1)*sizeof(char));
    522     c->deg[i]=(int*) omAlloc((i+1)*sizeof(int));
    523     for (j=0;j<i;j++){
    524       //check product criterion
    525       if (pHasNotCF(c->S->m[i],c->S->m[j])){
    526         c->states[i][j]=HASTREP;
    527       } else {
    528         c->states[i][j]=UNCALCULATED;
    529       }
    530       c->deg[i][j]=pLcmDeg(c->S->m[i],c->S->m[j]);
    531     }
    532     if ((c->lengths[i]==1) && (c->lengths[j]==1))
    533       c->states[i][j]=HASTREP;
    534     c->rep[i]=i;
    535     c->short_Exps[i]=p_GetShortExpVector(c->S->m[i],c->r);
    536 
    537   }
     515    {
     516#ifdef HEAD_BIN
     517      c->S->m[i]=p_MoveHead(c->S->m[i],c->HeadBin);
     518#endif
     519      c->T_deg[i]=pFDeg(c->S->m[i]);
     520      c->lengths[i]=pLength(c->S->m[i]);
     521      c->misses[i]=0;
     522      c->states[i]=(char *)omAlloc((i+1)*sizeof(char));
     523      c->deg[i]=(int*) omAlloc((i+1)*sizeof(int));
     524      for (j=0;j<i;j++){
     525        //check product criterion
     526        if (pHasNotCF(c->S->m[i],c->S->m[j])){
     527          c->states[i][j]=HASTREP;
     528        } else {
     529          c->states[i][j]=UNCALCULATED;
     530        }
     531        c->deg[i][j]=pLcmDeg(c->S->m[i],c->S->m[j]);
     532      }
     533      if ((c->lengths[i]==1) && (c->lengths[j]==1))
     534        c->states[i][j]=HASTREP;
     535      c->rep[i]=i;
     536      c->short_Exps[i]=p_GetShortExpVector(c->S->m[i],c->r);
     537
     538    }
    538539
    539540
    … …  
    546547  c->strat->sl = -1;
    547548  /* initS(c->S,NULL,c->strat); */
    548   /* intS start: */
    549   i=((i+IDELEMS(c->S)+15)/16)*16;
    550   c->strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/
    551   c->strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long));
    552                     /*initsevS(i);*/
    553   c->strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/
    554   c->strat->fromQ=NULL;
    555   c->strat->Shdl=idInit(i,1);
    556   c->strat->S=c->strat->Shdl->m;
    557   c->strat->lenS=(int*)omAlloc0(i*sizeof(int));
    558   for (i=0; i<IDELEMS(c->S); i++)
    559   {
    560     int pos;
    561     assume (c->S->m[i]!=NULL);
    562     LObject h;
    563     h.p = c->S->m[i];
    564     h.pNorm();
    565     c->strat->initEcart(&h);
    566     assume(c->lengths[i]==pLength(h.p));
    567     if (c->strat->sl==-1) pos=0;
    568     else pos = simple_posInS(c->strat,h.p,c->lengths[i]);
    569     h.sev = pGetShortExpVector(h.p);
    570     c->strat->enterS(h,pos,c->strat);
    571     c->strat->lenS[pos]=c->lengths[i];
    572   }
    573   //c->strat->lenS=(int*)omAlloc0(IDELEMS(c->strat->Shdl)*sizeof(int));
    574   //for (i=c->strat->sl;i>=0;i--)
    575   //{
    576   //  pNorm(c->strat->S[i]);
    577   //  c->strat->lenS[i]=pLength(c->strat->S[i]);
    578   //}
    579   /* initS end */
     549/* intS start: */
     550 i=((i+IDELEMS(c->S)+15)/16)*16;
     551 c->strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/
     552 c->strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long));
     553 /*initsevS(i);*/
     554 c->strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/
     555 c->strat->fromQ=NULL;
     556 c->strat->Shdl=idInit(i,1);
     557 c->strat->S=c->strat->Shdl->m;
     558 c->strat->lenS=(int*)omAlloc0(i*sizeof(int));
     559 for (i=0; i<IDELEMS(c->S); i++)
     560   {
     561     int pos;
     562     assume (c->S->m[i]!=NULL);
     563     LObject h;
     564     h.p = c->S->m[i];
     565     h.pNorm();
     566     c->strat->initEcart(&h);
     567     assume(c->lengths[i]==pLength(h.p));
     568     if (c->strat->sl==-1) pos=0;
     569     else pos = simple_posInS(c->strat,h.p,c->lengths[i]);
     570     h.sev = pGetShortExpVector(h.p);
     571     c->strat->enterS(h,pos,c->strat);
     572     c->strat->lenS[pos]=c->lengths[i];
     573   }
     574 //c->strat->lenS=(int*)omAlloc0(IDELEMS(c->strat->Shdl)*sizeof(int));
     575 //for (i=c->strat->sl;i>=0;i--)
     576 //{
     577 //  pNorm(c->strat->S[i]);
     578 //  c->strat->lenS[i]=pLength(c->strat->S[i]);
     579 //}
     580 /* initS end */
    580581}
    581582int simple_posInS (kStrategy strat, poly p,int len)
    … …  
    590591
    591592  if ((len>setL[length])
    592   || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
     593      || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
    593594    return length+1;
    594595
    595596  loop
    596   {
    597     if (an >= en-1)
    598     {
    599       if ((len<setL[an])
    600       || ((len==setL[length]) && (pLmCmp(set[an],p) == 1))) return an;
    601       return en;
    602     }
    603     i=(an+en) / 2;
    604     if ((len<setL[i])
    605     || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
    606     //else if ((len>setL[i])
    607     //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
    608     else an=i;
    609   }
     597    {
     598      if (an >= en-1)
     599        {
     600          if ((len<setL[an])
     601              || ((len==setL[length]) && (pLmCmp(set[an],p) == 1))) return an;
     602          return en;
     603        }
     604      i=(an+en) / 2;
     605      if ((len<setL[i])
     606          || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
     607      //else if ((len>setL[i])
     608      //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
     609      else an=i;
     610    }
    610611}
    611612/*2
    612 *if the leading term of p
    613 *divides the leading term of some S[i] it will be canceled
    614 */
     613 *if the leading term of p
     614 *divides the leading term of some S[i] it will be canceled
     615 */
    615616static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k,
    616                     kStrategy strat)
     617                           kStrategy strat)
    617618{
    618619  assume(p_sev == pGetShortExpVector(p));
    … …  
    678679  for (j=0;j<i;j++){
    679680    c->deg[i][j]=pLcmDeg(c->S->m[i],c->S->m[j]);
    680        if (c->rep[j]==j){
     681    if (c->rep[j]==j){
    681682      //check product criterion
    682683
    683          c->states[i][j]=UNCALCULATED;
     684      c->states[i][j]=UNCALCULATED;
    684685
    685686
    686687      //lies I[i] under I[j] ?
    687          if(p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)){
    688            c->rep[j]=i;
    689            PrintS("R"); R_found=TRUE;
    690 
    691            c->misses[i_pos]--;
    692            c->misses[j_pos]--;
    693            for(int z=0;z<j;z++){
    694              if (c->states[j][z]==UNCALCULATED){
    695                c->states[j][z]=UNIMPORTANT;
    696              }
    697            }
    698            for(int z=j+1;z<i;z++){
    699              if (c->states[z][j]==UNCALCULATED){
    700                c->states[z][j]=UNIMPORTANT;
    701              }
    702            }
    703          }
    704        }
     688      if(p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)){
     689        c->rep[j]=i;
     690        PrintS("R"); R_found=TRUE;
     691
     692        c->misses[i_pos]--;
     693        c->misses[j_pos]--;
     694        for(int z=0;z<j;z++){
     695          if (c->states[j][z]==UNCALCULATED){
     696            c->states[j][z]=UNIMPORTANT;
     697          }
     698        }
     699        for(int z=j+1;z<i;z++){
     700          if (c->states[z][j]==UNCALCULATED){
     701            c->states[z][j]=UNIMPORTANT;
     702          }
     703        }
     704      }
     705    }
    705706    else {
    706            c->states[i][j]=UNIMPORTANT;
    707          }
     707      c->states[i][j]=UNIMPORTANT;
     708    }
    708709    if ((c->lengths[i]==1) && (c->lengths[j]==1))
    709710      c->states[i][j]=HASTREP;
    … …  
    719720
    720721  //i=posInS(c->strat,c->strat->sl,h,0 /*ecart*/);
    721   i=simple_posInS(c->strat,h,c->lengths[c->n-1]);
    722 
    723   LObject P; memset(&P,0,sizeof(P));
    724   P.tailRing=c->r;
    725   P.p=h; /*p_Copy(h,c->r);*/
    726   P.FDeg=pFDeg(P.p,c->r);
    727   if (!rField_is_Zp(c->r)) pCleardenom(P.p);
    728   //enterT(P,c->strat,-1);
    729   c->strat->enterS(P,i,c->strat);
    730   c->strat->lenS[i]=/*pLength(c->strat->S[i]);*/ c->lengths[c->n-1];
    731   pNorm(c->strat->S[i]);
    732   if (0 /*R_found && (i<c->strat->sl)*/)
    733   {
    734     i++;
    735     unsigned long h_sev = pGetShortExpVector(h);
    736     loop
    737     {
    738       if (i>c->strat->sl) break;
    739       clearS(h,h_sev,c->lengths[c->n-1], &i,&(c->strat->sl),c->strat);
    740       i++;
    741     }
    742   }
    743   if (c->lengths[c->n-1]==1)
    744     shorten_tails(c,c->S->m[c->n-1]);
     722    i=simple_posInS(c->strat,h,c->lengths[c->n-1]);
     723
     724    LObject P; memset(&P,0,sizeof(P));
     725    P.tailRing=c->r;
     726    P.p=h; /*p_Copy(h,c->r);*/
     727    P.FDeg=pFDeg(P.p,c->r);
     728    if (!rField_is_Zp(c->r)) pCleardenom(P.p);
     729    //enterT(P,c->strat,-1);
     730    c->strat->enterS(P,i,c->strat);
     731    c->strat->lenS[i]=/*pLength(c->strat->S[i]);*/ c->lengths[c->n-1];
     732    pNorm(c->strat->S[i]);
     733    if (0 /*R_found && (i<c->strat->sl)*/)
     734      {
     735        i++;
     736        unsigned long h_sev = pGetShortExpVector(h);
     737        loop
     738          {
     739            if (i>c->strat->sl) break;
     740            clearS(h,h_sev,c->lengths[c->n-1], &i,&(c->strat->sl),c->strat);
     741            i++;
     742          }
     743      }
     744    if (c->lengths[c->n-1]==1)
     745      shorten_tails(c,c->S->m[c->n-1]);
    745746    //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
    746747
    747   //for(i=c->strat->sl; i>0;i--)
    748   //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
     748    //for(i=c->strat->sl; i>0;i--)
     749    //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
    749750}
    750751#if 0
    … …  
    756757
    757758  if (0 > strat->sl)
    758   {
    759     return h;
    760   }
     759    {
     760      return h;
     761    }
    761762  not_sev = ~ pGetShortExpVector(h);
    762763  loop
    763   {
    764     if (pLmShortDivisibleBy(strat->S[j], strat->sevS[j], h, not_sev))
    765     {
    766       //if (strat->interpt) test_int_std(strat->kIdeal);
    767       /*- compute the s-polynomial -*/
     764    {
     765      if (pLmShortDivisibleBy(strat->S[j], strat->sevS[j], h, not_sev))
     766        {
     767          //if (strat->interpt) test_int_std(strat->kIdeal);
     768          /*- compute the s-polynomial -*/
    768769#ifdef KDEBUG
    769       if (TEST_OPT_DEBUG)
    770       {
    771         PrintS("red:");
    772         wrp(h);
    773         PrintS(" with ");
    774         wrp(strat->S[j]);
    775       }
    776 #endif
    777       h = ksOldSpolyRed(strat->S[j],h,strat->kNoether);
     770          if (TEST_OPT_DEBUG)
     771            {
     772              PrintS("red:");
     773              wrp(h);
     774              PrintS(" with ");
     775              wrp(strat->S[j]);
     776            }
     777#endif
     778          h = ksOldSpolyRed(strat->S[j],h,strat->kNoether);
    778779#ifdef KDEBUG
    779       if (TEST_OPT_DEBUG)
    780       {
    781         PrintS("\nto:");
    782         wrp(h);
    783         PrintLn();
    784       }
    785 #endif
    786       if (h == NULL) return NULL;
    787       z++;
    788       if (z>=10)
    789       {
    790         z=0;
    791         pNormalize(h);
    792       }
    793       /*- try to reduce the s-polynomial -*/
    794       j = 0;
    795       not_sev = ~ pGetShortExpVector(h);
    796     }
    797     else
    798     {
    799       if (j >= strat->sl) return h;
    800       j++;
    801     }
    802   }
     780          if (TEST_OPT_DEBUG)
     781            {
     782              PrintS("\nto:");
     783              wrp(h);
     784              PrintLn();
     785            }
     786#endif
     787          if (h == NULL) return NULL;
     788          z++;
     789          if (z>=10)
     790            {
     791              z=0;
     792              pNormalize(h);
     793            }
     794          /*- try to reduce the s-polynomial -*/
     795          j = 0;
     796          not_sev = ~ pGetShortExpVector(h);
     797        }
     798      else
     799        {
     800          if (j >= strat->sl) return h;
     801          j++;
     802        }
     803    }
    803804}
    804805#else
    805 static poly redNF (poly h,kStrategy strat, int &len)
     806static poly redNF2 (poly h,calc_dat* c , int &len)
    806807{
    807808  len=0;
    … …  
    809810  int j;
    810811
     812  kStrategy strat=c->strat;
    811813  len=pLength(h);
     814  int len_upper_bound=len;
    812815  if (0 > strat->sl)
    813   {
    814     return h;
    815   }
     816    {
     817      return h;
     818    }
    816819  LObject P(h);
    817820  P.SetShortExpVector();
    … …  
    820823  //int max_pos=simple_posInS(strat,P.p);
    821824  loop
    822   {
    823     j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
    824     if (j>=0)
    825     {
    826       nNormalize(pGetCoeff(P.p));
     825    {
     826      j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
     827      if (j>=0)
     828        {
     829          poly sec_copy=NULL;
     830          //pseudo code
     831          bool must_replace_in_basis=(len_upper_bound<=strat->lenS[j]);//first test
     832          if (must_replace_in_basis)
     833            {
     834              //second test
     835              if (pLmEqual(P.p,strat->S[j]))
     836                {
     837                  PrintS("b");
     838                  sec_copy=kBucketClear(P.bucket);
     839                  kBucketInit(P.bucket,pCopy(sec_copy),pLength(sec_copy));
     840                }
     841              else
     842                {
     843                  must_replace_in_basis=false;
     844                }
     845            }
     846          nNormalize(pGetCoeff(P.p));
    827847#ifdef KDEBUG
    828       if (TEST_OPT_DEBUG)
     848          if (TEST_OPT_DEBUG)
     849            {
     850              PrintS("red:");
     851              wrp(h);
     852              PrintS(" with ");
     853              wrp(strat->S[j]);
     854            }
     855#endif
     856          len_upper_bound=len_upper_bound+strat->lenS[j]-2;
     857          number coef=kBucketPolyRed(P.bucket,strat->S[j],
     858                                     strat->lenS[j]/*pLength(strat->S[j])*/,
     859  strat->kNoether);
     860 nDelete(&coef);
     861 h = kBucketGetLm(P.bucket);
     862 //pseudo code
     863 if (must_replace_in_basis){
     864   int old_pos_in_c=-1;
     865   poly p=strat->S[j];
     866   int z;
     867   
     868   int new_length=pLength(sec_copy);
     869   Print("%i",strat->lenS[j]-new_length);
     870   len_upper_bound=new_length +strat->lenS[j]-2;//old entries length
     871   int new_pos=simple_posInS(c->strat,strat->S[j],new_length);
     872   strat->S[j]=sec_copy;
     873   c->strat->lenS[j]=new_length;
     874   
     875   for (z=c->n;z;z--)
     876     {
     877       if(p==c->S->m[z-1])
     878         {
     879           c->S->m[z-1]=sec_copy;
     880           old_pos_in_c=z-1;
     881           c->lengths[z-1]=new_length;
     882           if (new_length==1)
     883             {
     884               int i;
     885               for ( i=0;i<z-1;i++)
     886                 {
     887                   if (c->lengths[i]==1)
     888                     c->states[z-1][i]=HASTREP;
     889                 }
     890               for ( i=z;i<c->n;i++){
     891                 if (c->lengths[i]==1)
     892                   c->states[i][z-1]=HASTREP;
     893               }
     894               shorten_tails(c,sec_copy);
     895             }
     896           break;
     897         }
     898     }
     899   pDelete(&p);
     900
     901   //   replace_quietly(c,j,sec_copy);
     902   // have to do many additional things for consistency
     903   {
     904     
     905     
     906     
     907
     908     int old_pos=j;
     909     assume(new_pos<=old_pos);
     910 
     911
     912     c->strat->lenS[old_pos]=new_length;
     913     int i=0;
     914     for(i=new_pos;i<old_pos;i++){
     915       if (strat->lenS[i]<=new_length)
     916         new_pos++;
     917       else
     918         break;
     919     }
     920     if (new_pos<old_pos)
     921       move_forward_in_S(old_pos,new_pos,c->strat);
     922   
     923
     924   }
     925 }
     926 if (h==NULL) return NULL;
     927 P.p=h;
     928 P.t_p=NULL;
     929 P.SetShortExpVector();
     930#ifdef KDEBUG
     931 if (TEST_OPT_DEBUG)
     932   {
     933     PrintS("\nto:");
     934     wrp(h);
     935     PrintLn();
     936   }
     937#endif
     938        }
     939    else
    829940      {
    830         PrintS("red:");
    831         wrp(h);
    832         PrintS(" with ");
    833         wrp(strat->S[j]);
    834       }
    835 #endif
    836       number coef=kBucketPolyRed(P.bucket,strat->S[j],
    837                           strat->lenS[j]/*pLength(strat->S[j])*/,
    838                           strat->kNoether);
    839       nDelete(&coef);
    840       h = kBucketGetLm(P.bucket);
    841       if (h==NULL) return NULL;
    842       P.p=h;
    843       P.t_p=NULL;
    844       P.SetShortExpVector();
     941        kBucketClear(P.bucket,&(P.p),&len);
     942        kBucketDestroy(&P.bucket);
     943        pNormalize(P.p);
     944        return P.p;
     945      }
     946    }
     947}
     948static poly redNF (poly h,kStrategy strat, int &len)
     949{
     950  len=0;
     951  if (h==NULL) return NULL;
     952  int j;
     953
     954  len=pLength(h);
     955  if (0 > strat->sl)
     956    {
     957      return h;
     958    }
     959  LObject P(h);
     960  P.SetShortExpVector();
     961  P.bucket = kBucketCreate(currRing);
     962  kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/);
     963  //int max_pos=simple_posInS(strat,P.p);
     964  loop
     965    {
     966      j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
     967      if (j>=0)
     968        {
     969          nNormalize(pGetCoeff(P.p));
    845970#ifdef KDEBUG
    846       if (TEST_OPT_DEBUG)
     971          if (TEST_OPT_DEBUG)
     972            {
     973              PrintS("red:");
     974              wrp(h);
     975              PrintS(" with ");
     976              wrp(strat->S[j]);
     977            }
     978#endif
     979          number coef=kBucketPolyRed(P.bucket,strat->S[j],
     980                                     strat->lenS[j]/*pLength(strat->S[j])*/,
     981  strat->kNoether);
     982 nDelete(&coef);
     983 h = kBucketGetLm(P.bucket);
     984 if (h==NULL) return NULL;
     985 P.p=h;
     986 P.t_p=NULL;
     987 P.SetShortExpVector();
     988#ifdef KDEBUG
     989 if (TEST_OPT_DEBUG)
     990   {
     991     PrintS("\nto:");
     992     wrp(h);
     993     PrintLn();
     994   }
     995#endif
     996        }
     997    else
    847998      {
    848         PrintS("\nto:");
    849         wrp(h);
    850         PrintLn();
    851       }
    852 #endif
    853     }
    854     else
    855     {
    856       kBucketClear(P.bucket,&(P.p),&len);
    857       kBucketDestroy(&P.bucket);
    858       pNormalize(P.p);
    859       return P.p;
    860     }
    861   }
     999        kBucketClear(P.bucket,&(P.p),&len);
     1000        kBucketDestroy(&P.bucket);
     1001        pNormalize(P.p);
     1002        return P.p;
     1003      }
     1004    }
    8621005}
    8631006#endif
    … …  
    8831026  pTest(h);
    8841027  loop
    885   {
    886     P.p=h;
    887     P.t_p=NULL;
    888     P.SetShortExpVector();
    889     loop
    890     {
    891       j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P);
    892       if (j>=0)
    893       {
    894       #ifdef REDTAIL_PROT
    895         PrintS("r");
    896       #endif
    897         nNormalize(pGetCoeff(P.p));
     1028    {
     1029      P.p=h;
     1030      P.t_p=NULL;
     1031      P.SetShortExpVector();
     1032      loop
     1033        {
     1034          j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P);
     1035          if (j>=0)
     1036            {
     1037#ifdef REDTAIL_PROT
     1038              PrintS("r");
     1039#endif
     1040              nNormalize(pGetCoeff(P.p));
    8981041#ifdef KDEBUG
    899         if (TEST_OPT_DEBUG)
    900         {
    901           PrintS("red tail:");
    902           wrp(h);
    903           PrintS(" with ");
    904           wrp(strat->S[j]);
    905         }
    906 #endif
    907         number coef;
    908         pTest(strat->S[j]);
    909         coef=kBucketPolyRed(P.bucket,strat->S[j],
    910                strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether);
    911         pMult_nn(res,coef);
    912         nDelete(&coef);
    913         h = kBucketGetLm(P.bucket);
    914         pTest(h);
    915         if (h==NULL)
    916         {
    917           #ifdef REDTAIL_PROT
    918             PrintS(" ");
    919           #endif
    920           return res;
    921         }
    922   pTest(h);
    923         P.p=h;
    924         P.t_p=NULL;
    925         P.SetShortExpVector();
     1042              if (TEST_OPT_DEBUG)
     1043                {
     1044                  PrintS("red tail:");
     1045                  wrp(h);
     1046                  PrintS(" with ");
     1047                  wrp(strat->S[j]);
     1048                }
     1049#endif
     1050              number coef;
     1051              pTest(strat->S[j]);
     1052              coef=kBucketPolyRed(P.bucket,strat->S[j],
     1053                                  strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether);
     1054              pMult_nn(res,coef);
     1055              nDelete(&coef);
     1056              h = kBucketGetLm(P.bucket);
     1057              pTest(h);
     1058              if (h==NULL)
     1059                {
     1060#ifdef REDTAIL_PROT
     1061                  PrintS(" ");
     1062#endif
     1063                  return res;
     1064                }
     1065              pTest(h);
     1066              P.p=h;
     1067              P.t_p=NULL;
     1068              P.SetShortExpVector();
    9261069#ifdef KDEBUG
    927         if (TEST_OPT_DEBUG)
    928         {
    929           PrintS("\nto tail:");
    930           wrp(h);
    931           PrintLn();
    932         }
    933 #endif
    934       }
    935       else
    936       {
    937         #ifdef REDTAIL_PROT
    938           PrintS("n");
    939         #endif
    940         break;
    941       }
    942     } /* end loop current mon */
    943     poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
    944     act->next=tmp;pIter(act);
    945     poly tmp2=pHead(h);
    946     pNeg(tmp2);
    947     int ltmp2=1;
    948     pTest(tmp2);
    949     kBucket_Add_q(P.bucket, tmp2, &ltmp2);
    950 
    951     h = kBucketGetLm(P.bucket);
    952     if (h==NULL)
    953     {
    954       #ifdef REDTAIL_PROT
    955         PrintS(" ");
    956       #endif
    957       return res;
    958     }
    959   pTest(h);
    960   }
     1070              if (TEST_OPT_DEBUG)
     1071                {
     1072                  PrintS("\nto tail:");
     1073                  wrp(h);
     1074                  PrintLn();
     1075                }
     1076#endif
     1077            }
     1078          else
     1079            {
     1080#ifdef REDTAIL_PROT
     1081              PrintS("n");
     1082#endif
     1083              break;
     1084            }
     1085        } /* end loop current mon */
     1086      poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
     1087      act->next=tmp;pIter(act);
     1088      poly tmp2=pHead(h);
     1089      pNeg(tmp2);
     1090      int ltmp2=1;
     1091      pTest(tmp2);
     1092      kBucket_Add_q(P.bucket, tmp2, &ltmp2);
     1093
     1094      h = kBucketGetLm(P.bucket);
     1095      if (h==NULL)
     1096        {
     1097#ifdef REDTAIL_PROT
     1098          PrintS(" ");
     1099#endif
     1100          return res;
     1101        }
     1102      pTest(h);
     1103    }
    9611104}
    9621105#endif
    … …  
    9691112#ifdef FULLREDUCTIONS
    9701113  if (h!=NULL)
    971   {
    972     int len;
    973     hr=redNF(h,c->strat,len);
    974     if (hr!=NULL)
    975     #ifdef REDTAIL_S
    976       hr = redNFTail(hr,c->strat->sl,c->strat,len);
    977     #else
     1114    {
     1115      int len;
     1116
     1117      hr=redNF2(h,c,len);
     1118#ifdef HALFREDUCTIONS
     1119      int real_sl=c->strat->sl;
     1120      int l;
     1121      for(l=0;l<c->n;l++){
     1122        if (c->strat->lenS[l]>4)
     1123          break;
     1124      }
     1125      c->strat->sl=l;
     1126#endif
     1127      if (hr!=NULL)
     1128#ifdef REDTAIL_S
     1129        hr = redNFTail(hr,c->strat->sl,c->strat,len);
     1130#else
    9781131      hr = redtailBba(hr,c->strat->sl,c->strat);
    979     #endif
    980   }
     1132#endif
     1133#ifdef HALFREDUCTIONS
     1134      c->strat->sl=real_sl;
     1135#endif
     1136    }
    9811137#else
    9821138  if (h!=NULL)
    983   {
    984     int len;
    985     hr=redNF(h,c->strat,&len);
    986   }
     1139    {
     1140      int len;
     1141      hr=redNF2(h,c,len);
     1142    }
    9871143#endif
    9881144  c->normal_forms++;
    9891145  if (hr==NULL)
    990   {
    991     PrintS("-");
    992     c->misses_counter++;
    993     c->misses[i]++;
    994     c->misses[j]++;
    995     c->misses_series++;
    996   }
     1146    {
     1147      PrintS("-");
     1148      c->misses_counter++;
     1149      c->misses[i]++;
     1150      c->misses[j]++;
     1151      c->misses_series++;
     1152    }
    9971153  else
    998   {
    999     c->misses_series=0;
    1000   #ifdef HEAD_BIN
    1001     hr=p_MoveHead(hr,c->HeadBin);
    1002   #endif
    1003     add_to_basis(hr, i,j,c);
    1004   }
     1154    {
     1155      c->misses_series=0;
     1156#ifdef HEAD_BIN
     1157      hr=p_MoveHead(hr,c->HeadBin);
     1158#endif
     1159      add_to_basis(hr, i,j,c);
     1160    }
    10051161}
    10061162
    10071163ideal t_rep_gb(ring r,ideal arg_I){
    1008   ideal I_temp=kInterRed(arg_I);
     1164  ideal I_temp=idCopy(arg_I); //kInterRed(arg_I);
    10091165  ideal I=idCompactify(I_temp);
    10101166  idDelete(&I_temp);
    … …  
    10331189    int_pair_node* h=c->soon_free;
    10341190    while(h!=NULL)
    1035     {
    1036       int_pair_node* s=h;
    1037       now_t_rep(h->a,h->b,c);
    1038 
    1039       h=h->next;
    1040       omfree(s);
    1041     }
     1191      {
     1192        int_pair_node* s=h;
     1193        now_t_rep(h->a,h->b,c);
     1194
     1195        h=h->next;
     1196        omfree(s);
     1197      }
    10421198
    10431199
    … …  
    10701226
    10711227  if (arg_i==arg_j)
    1072   {
    1073     return (true);
    1074   }
     1228    {
     1229      return (true);
     1230    }
    10751231  if (arg_i>arg_j)
    1076   {
    1077     return (state->states[arg_i][arg_j]==HASTREP);
    1078   } else
    1079   {
    1080     return (state->states[arg_j][arg_i]==HASTREP);
    1081   }
     1232    {
     1233      return (state->states[arg_i][arg_j]==HASTREP);
     1234    } else
     1235      {
     1236        return (state->states[arg_j][arg_i]==HASTREP);
     1237      }
    10821238}
    10831239int pLcmDeg(poly a, poly b)
    … …  
    10861242  int n=0;
    10871243  for (i=pVariables; i; i--)
    1088   {
    1089     n+=max( pGetExp(a,i), pGetExp(b,i));
    1090   }
     1244    {
     1245      n+=max( pGetExp(a,i), pGetExp(b,i));
     1246    }
    10911247  return n;
    10921248
    … …  
    11191275
    11201276  for(int i=0;i<c->n;i++)
    1121   {
    1122     //enter tail
    1123     if (c->rep[i]!=i) continue;
    1124     if (c->S->m[i]==NULL) continue;
    1125     poly tail=c->S->m[i]->next;
    1126     poly prev=c->S->m[i];
    1127     bool did_something=false;
    1128     while((tail!=NULL)&& (pLmCmp(tail, monom)>=0))
    1129     {
    1130       if (p_LmDivisibleBy(monom,tail,c->r))
    1131       {
    1132         did_something=true;
    1133         prev->next=tail->next;
    1134         tail->next=NULL;
    1135         p_Delete(& tail,c->r);
    1136         tail=prev;
    1137         //PrintS("Shortened");
    1138         c->lengths[i]--;
    1139       }
    1140       prev=tail;
    1141       tail=tail->next;
    1142     }
    1143     if (did_something)
    1144     {
    1145       int new_pos=simple_posInS(c->strat,c->S->m[i],c->lengths[i]);
    1146       int old_pos=-1;
    1147       //assume new_pos<old_pos
    1148       for (int z=new_pos;z<=c->strat->sl;z++)
    1149       {
    1150         if (c->strat->S[z]==c->S->m[i])
    1151         {
    1152           old_pos=z;
    1153           break;
    1154         }
    1155       }
    1156       if (old_pos== -1)
    1157       for (int z=new_pos-1;z>=0l;z--)
    1158       {
    1159         if (c->strat->S[z]==c->S->m[i])
    1160         {
    1161           old_pos=z;
    1162           break;
    1163         }
    1164       }
    1165       assume(old_pos>=0);
    1166       assume(pLength(c->strat->S[old_pos])==c->lengths[i]);
    1167       c->strat->lenS[old_pos]=c->lengths[i];
    1168       if (new_pos<old_pos)
    1169         move_forward_in_S(old_pos,new_pos,c->strat);
    1170       if (c->lengths[i]==1)
    1171       {
    1172         int j;
    1173         for ( j=0;j<i;j++)
    1174         {
    1175           if (c->lengths[j]==1)
    1176             c->states[i][j]=HASTREP;
    1177         }
    1178         for ( j=i+1;j<c->n;j++){
    1179           if (c->lengths[j]==1)
    1180             c->states[j][i]=HASTREP;
    1181         }
    1182       }
    1183     }
    1184   }
    1185 }
     1277    {
     1278      //enter tail
     1279      if (c->rep[i]!=i) continue;
     1280      if (c->S->m[i]==NULL) continue;
     1281      poly tail=c->S->m[i]->next;
     1282      poly prev=c->S->m[i];
     1283      bool did_something=false;
     1284      while((tail!=NULL)&& (pLmCmp(tail, monom)>=0))
     1285        {
     1286          if (p_LmDivisibleBy(monom,tail,c->r))
     1287            {
     1288              did_something=true;
     1289              prev->next=tail->next;
     1290              tail->next=NULL;
     1291              p_Delete(& tail,c->r);
     1292              tail=prev;
     1293              //PrintS("Shortened");
     1294              c->lengths[i]--;
     1295            }
     1296          prev=tail;
     1297          tail=tail->next;
     1298        }
     1299      if (did_something)
     1300        {
     1301          int new_pos=simple_posInS(c->strat,c->S->m[i],c->lengths[i]);
     1302          int old_pos=-1;
     1303          //assume new_pos<old_pos
     1304          for (int z=new_pos;z<=c->strat->sl;z++)
     1305            {
     1306              if (c->strat->S[z]==c->S->m[i])
     1307                {
     1308                  old_pos=z;
     1309                  break;
     1310                }
     1311            }
     1312          if (old_pos== -1)
     1313            for (int z=new_pos-1;z>=0;z--)
     1314              {
     1315                if (c->strat->S[z]==c->S->m[i])
     1316                  {
     1317                    old_pos=z;
     1318                    break;
     1319                  }
     1320              }
     1321          assume(old_pos>=0);
     1322          assume(pLength(c->strat->S[old_pos])==c->lengths[i]);
     1323          c->strat->lenS[old_pos]=c->lengths[i];
     1324          if (new_pos<old_pos)
     1325            move_forward_in_S(old_pos,new_pos,c->strat);
     1326          if (c->lengths[i]==1)
     1327            {
     1328             
     1329              int j;
     1330              for ( j=0;j<i;j++)
     1331                {
     1332                  if (c->lengths[j]==1)
     1333                    c->states[i][j]=HASTREP;
     1334                }
     1335              for ( j=i+1;j<c->n;j++){
     1336                if (c->lengths[j]==1)
     1337                  c->states[j][i]=HASTREP;
     1338              }
     1339              shorten_tails(c,c->S->m[i]);
     1340            }
     1341        }
     1342    }
     1343}
Note: See TracChangeset for help on using the changeset viewer.