Changeset cc4d094 in git


Ignore:
Timestamp:
Feb 8, 2007, 11:40:35 AM (16 years ago)
Author:
Michael Brickenstein <bricken@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
f14cbcb38f34d4058c037ba2a746bd9ef43ea15a
Parents:
508937797961aad4ba379a8c5136675e42495d8a
Message:
-map


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

Legend:

Unmodified
Added
Removed
  • Singular/claptmpl.cc

    r508937 rcc4d094  
    33*  Computer Algebra System SINGULAR     *
    44****************************************/
    5 // $Id: claptmpl.cc,v 1.35 2007-02-07 12:40:06 bricken Exp $
     5// $Id: claptmpl.cc,v 1.36 2007-02-08 10:40:35 bricken Exp $
    66/*
    77* ABSTRACT - instantiation of all templates
     
    220220template int pos_helper(kStrategy strat, poly p, wlen_type len, wlen_set setL, polyset set);
    221221#ifdef NORO_CACHE
    222 template class std::map<PolySimple,std::pair<PolySimple,int> >;
     222//template class std::map<PolySimple,std::pair<PolySimple,int> >;
    223223template class std::vector<PolySimple>;
    224224#endif
  • kernel/tgb.cc

    r508937 rcc4d094  
    55*  Computer Algebra System SINGULAR     *
    66****************************************/
    7 /* $Id: tgb.cc,v 1.124 2007-02-07 12:39:55 bricken Exp $ */
     7/* $Id: tgb.cc,v 1.125 2007-02-08 10:40:18 bricken Exp $ */
    88/*
    99* ABSTRACT: slimgb and F4 implementation
     
    2929#include <stdlib.h>
    3030#include <stdio.h>
    31 #include <map>
     31
     32#define BUCKETS_FOR_NORO_RED 1
    3233#define SR_HDL(A) ((long)(A))
    3334static const int bundle_size=1000;
     
    21852186
    21862187#ifdef NORO_CACHE
     2188class NoroCacheNode{
     2189public:
     2190  NoroCacheNode** branches;
     2191  int branches_len;
     2192
     2193 
     2194  NoroCacheNode(){
     2195    branches=NULL;
     2196    branches_len=0;
     2197  }
     2198  NoroCacheNode* setNode(int branch, NoroCacheNode* node){
     2199    if (branch>=branches_len){
     2200      if (branches==NULL){
     2201        branches_len=branch+1;
     2202        branches=(NoroCacheNode**) omalloc(branches_len*sizeof(NoroCacheNode*));
     2203        int i;
     2204        for(i=0;i<branches_len;i++){
     2205          branches[i]=NULL;
     2206        }
     2207      }else{
     2208        int branches_len_old=branches_len;
     2209        branches_len=branch+1;
     2210        branches=(NoroCacheNode**) omrealloc(branches,branches_len*sizeof(NoroCacheNode*));
     2211        int i;
     2212        for(i=branches_len_old;i<branches_len;i++){
     2213          branches[i]=NULL;
     2214        }
     2215      }
     2216    }
     2217    assume(branches[branch]==NULL);
     2218    branches[branch]=node;
     2219    return node;
     2220  }
     2221  NoroCacheNode* getBranch(int branch){
     2222    if (branch<branches_len) return branches[branch];
     2223    return NULL;
     2224  }
     2225  virtual ~NoroCacheNode(){
     2226    int i;
     2227    for(i=0;i<branches_len;i++){
     2228      delete branches[i];
     2229    }
     2230    omfree(branches);
     2231  }
     2232  NoroCacheNode* getOrInsertBranch(int branch){
     2233    if ((branch<branches_len)&&(branches[branch]))
     2234      return branches[branch];
     2235    else{
     2236      return setNode(branch,new NoroCacheNode());
     2237    }
     2238  }
     2239};
     2240class DataNoroCacheNode:public NoroCacheNode{
     2241public:
     2242 
     2243  int value_len;
     2244  poly value_poly;
     2245  DataNoroCacheNode(poly p, int len){
     2246    value_len=len;
     2247    value_poly=p;
     2248  }
     2249};
    21872250class NoroCache{
    21882251public:
     2252  poly temp_term;
     2253#ifndef BUCKETS_FOR_NORO_RED
     2254  int reserved;
     2255  poly* recursionPolyBuffer;
     2256#endif
     2257  static const int backLinkCode=-222;
    21892258  void insert(poly term, poly nf, int len){
    2190     assume(impl.find(p_Copy(term,currRing))==impl.end());
    2191     assume(len==pLength(nf));
     2259    //assume(impl.find(p_Copy(term,currRing))==impl.end());
     2260    //assume(len==pLength(nf));
    21922261    if (term==nf){
    2193       poly copied=p_Copy(term, currRing);
    2194       term=copied;
    2195       nf=copied;
    2196       ressources.push_back(copied);
     2262
     2263      treeInsertBackLink(term);
     2264      return;
    21972265    } else{
    2198       term=p_Copy(term,currRing);
    2199 
    2200       ressources.push_back(term);
     2266      //term=p_Copy(term,currRing);
     2267
     2268      //ressources.push_back(term);
    22012269      if (nf){
    22022270        nf=p_Copy(nf,currRing);
    22032271        ressources.push_back(nf);
    22042272      }
    2205     }
    2206     impl[term]=std::pair<PolySimple,int> (nf,len);
    2207   }
    2208   poly lookup(poly term, BOOLEAN& succ, int& len){
    2209     cache_map::iterator it=impl.find(term);
    2210     if (it!=impl.end()){
    2211       succ=TRUE;
    2212       //PrintS("Hit");
    2213       len=it->second.second;
    2214       return it->second.first.impl;
    2215     } else {
    2216       //PrintS("Miss");
    2217       succ=FALSE;
    2218       return NULL;
    2219     }
    2220   }
     2273      treeInsert(term,nf,len);
     2274      return;
     2275    }
     2276   
     2277    //impl[term]=std::pair<PolySimple,int> (nf,len);
     2278  }
     2279
     2280  poly lookup(poly term, BOOLEAN& succ, int & len);
     2281  NoroCache(){
     2282#ifndef BUCKETS_FOR_NORO_RED
     2283    reserved=0;
     2284    recursionPolyBuffer=(poly*)omalloc(1000000*sizeof(poly));
     2285#endif
     2286    temp_term=pOne();
     2287  }
     2288#ifndef BUCKETS_FOR_NORO_RED
     2289  poly* reserve(int n){
     2290    poly* res=recursionPolyBuffer+reserved;
     2291    reserved+=n;
     2292    return res;
     2293  }
     2294  void free(int n){
     2295    reserved-=n;
     2296  }
     2297#endif
    22212298  ~NoroCache(){
    22222299    int s=ressources.size();
     
    22252302      p_Delete(&ressources[i].impl,currRing);
    22262303    }
     2304    p_Delete(&temp_term,currRing);
     2305#ifndef BUCKETS_FOR_NORO_RED
     2306    omfree(recursionPolyBuffer);
     2307#endif
    22272308  }
    22282309protected:
     2310  void treeInsert(poly term,poly nf,int len){
     2311    int i;
     2312    int nvars=pVariables;
     2313    NoroCacheNode* parent=&root;
     2314    for(i=1;i<nvars;i++){
     2315      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
     2316    }
     2317    parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(nf,len));
     2318  }
     2319  void treeInsertBackLink(poly term){
     2320    int i;
     2321    int nvars=pVariables;
     2322    NoroCacheNode* parent=&root;
     2323    for(i=1;i<nvars;i++){
     2324      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
     2325    }
     2326    parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(NULL,backLinkCode));
     2327  }
     2328 
     2329  //@TODO descruct nodes;
    22292330  typedef std::vector<PolySimple> poly_vec;
    22302331  poly_vec ressources;
    2231   typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map;
    2232   cache_map impl;
     2332  //typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map;
     2333  //cache_map impl;
     2334  NoroCacheNode root;
    22332335};
    2234 
    2235 static poly noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c);
    2236 
    2237 static poly noro_red_mon(poly t, int &len, BOOLEAN& changed, NoroCache* cache,slimgb_alg* c){
     2336poly NoroCache::lookup(poly term, BOOLEAN& succ, int & len){
     2337  int i;
     2338  NoroCacheNode* parent=&root;
     2339  for(i=1;i<pVariables;i++){
     2340    parent=parent->getBranch(p_GetExp(term,i,currRing));
     2341    if (!(parent)){
     2342      succ=FALSE;
     2343      return NULL;
     2344    }
     2345  }
     2346  DataNoroCacheNode* res_holder=(DataNoroCacheNode*) parent->getBranch(p_GetExp(term,i,currRing));
     2347  if (res_holder){
     2348    succ=TRUE;
     2349    if ((res_holder->value_poly==0) &&(res_holder->value_len==backLinkCode)){
     2350      len=1;
     2351      return term;
     2352    }
     2353    len=res_holder->value_len;
     2354    return res_holder->value_poly;
     2355  } else {
     2356    succ=FALSE;
     2357    return NULL;
     2358  }
     2359}
     2360poly noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c);
     2361
     2362poly noro_red_mon(poly t, int &len, BOOLEAN& changed, NoroCache* cache,slimgb_alg* c){
    22382363  BOOLEAN succ;
    22392364  //wrp(t);
     
    22412366  poly cache_lookup=cache->lookup(t,succ, len);//don't own this yet
    22422367  if (succ){
    2243     if (p_LmEqual(cache_lookup,t,c->r)){
     2368    if (cache_lookup==t){
    22442369      //know they are equal
    22452370      len=1;
     
    22482373    }
    22492374    poly t_new=ppMult_nn(cache_lookup,pGetCoeff(t));
    2250     pDelete(&t);
     2375    p_Delete(&t,c->r);
    22512376    return t_new;
    22522377  } else {
     
    22552380    if (i>=0){
    22562381      number coef_bak=pGetCoeff(t);
    2257       if (!(npIsOne(coef_bak))){
    2258         number coef_inverse=npInvers(coef_bak);
    2259         t=pMult_nn(t,coef_inverse);
    2260 
    2261       }
     2382
     2383      p_SetCoeff(t,npInit(1),c->r);
    22622384      assume(npIsOne(p_GetCoeff(c->strat->S[i],c->r)));
    22632385      number coefstrat=p_GetCoeff(c->strat->S[i],c->r);
    2264     //assume(nIsOne(coef));
    22652386     
    2266       poly t_copy_mon=p_Copy(t,c->r);
    2267 
     2387      //poly t_copy_mon=p_Copy(t,c->r);
     2388      poly exp_diff=cache->temp_term;
     2389      p_ExpVectorDiff(exp_diff,t,c->strat->S[i],c->r);
     2390      p_SetCoeff(exp_diff,npNeg(npInvers(coefstrat)),c->r);
     2391      p_Setm(exp_diff,c->r);
     2392      assume(c->strat->S[i]!=NULL);
     2393      //poly t_to_del=t;
     2394      poly res;
     2395      res=pp_Mult_mm(pNext(c->strat->S[i]),exp_diff,c->r);
     2396
     2397      len=c->strat->lenS[i]-1;
     2398      res=noro_red(res,len,cache,c);
    22682399     
    2269       //TODO: t=spoly(t,..)
    2270       p_ExpVectorSub(t,c->strat->S[i],c->r);
    2271       p_SetCoeff(t,npNeg(npInvers(coefstrat)),c->r);
    2272       p_Setm(t,c->r);
    2273       assume(c->strat->S[i]!=NULL);
    2274       poly t_to_del=t;
    2275       t=pp_Mult_mm(pNext(c->strat->S[i]),t,c->r);
    2276       p_Delete(&t_to_del,c->r);
    2277       len=c->strat->lenS[i]-1;
    2278       t=noro_red(t,len,cache,c);
    2279      
    2280      
    2281       cache->insert(t_copy_mon,t,pLength(t));
    2282       p_Delete(&t_copy_mon,c->r);
    2283       t=pMult_nn(t,coef_bak);
    2284       return t;
     2400      cache->insert(t,res,pLength(res));
     2401      p_Delete(&t,c->r);
     2402      //p_Delete(&t_copy_mon,c->r);
     2403      res=pMult_nn(res,coef_bak);
     2404      return res;
    22852405    } else {
    22862406      number coef_bak=p_GetCoeff(t,c->r);
     
    22942414  }
    22952415}
     2416poly tree_add(poly* a,int begin, int end,ring r){
     2417  int d=end-begin;
     2418  switch(d){
     2419    case 0:
     2420      return NULL;
     2421    case 1:
     2422      return a[begin];
     2423    case 2:
     2424      return p_Add_q(a[begin],a[begin+1],r);
     2425    default:
     2426      int s=d/2;
     2427      return p_Add_q(tree_add(a,begin,begin+s,r),tree_add(a,begin+s,end,r),r);
     2428  }
     2429}
     2430
    22962431//len input and out: Idea: reverse addition
    2297 static poly noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c){
     2432poly noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c){
    22982433  assume(len==pLength(p));
    22992434  poly orig_p=p;
     
    23052440    return NULL;
    23062441  }
     2442  if (len==1){
     2443    BOOLEAN changed;
     2444    return noro_red_mon(p,len,changed,cache,c);
     2445  }
     2446  #ifdef BUCKETS_FOR_NORO_RED
    23072447  kBucket_pt bucket=kBucketCreate(currRing);
    23082448  kBucketInit(bucket,NULL,0);
    2309   int pos=0;
     2449  #endif
     2450  //int pos=0;
    23102451  poly unchanged_head=NULL;
    23112452  poly unchanged_tail=NULL;
    23122453  int unchanged_size=0;
     2454  #ifndef BUCKETS_FOR_NORO_RED
     2455  poly * pre_buckets=cache->reserve(len);
     2456  #endif
     2457  int reserved=len;//(poly*) omalloc(len*sizeof(poly));
     2458  int pos=0;
    23132459  while(p){
    23142460    poly t=p;
     
    23302476    } else{
    23312477      assume(l==pLength(t));
    2332 
     2478#ifdef BUCKETS_FOR_NORO_RED
    23332479      kBucket_Add_q(bucket,t,&l);
     2480#else
     2481     pre_buckets[pos++]=t;
     2482#endif
    23342483    }
    23352484    //pre_buckets[pos]=t;
     
    23382487    //todo catch in general the length from cache
    23392488
    2340   assume(pos==len);
     2489  //assume(pos==len);
    23412490  int i;
    23422491  //for(i=pos-1;i>=0;i--){
     
    23452494  poly res;
    23462495  len=0;
     2496 
     2497  #ifdef BUCKETS_FOR_NORO_RED
    23472498  kBucket_Add_q(bucket,unchanged_head,&unchanged_size);
    23482499  kBucketClear(bucket,&res,&len);
    23492500  kBucketDestroy(&bucket);
     2501  #else
     2502  res=tree_add(pre_buckets,0,pos,c->r);
     2503  res=p_Add_q(unchanged_head,res,c->r);
     2504  len=pLength(res);
     2505  cache->free(reserved);
     2506  //omfree(pre_buckets);
     2507  #endif
    23502508  //omfree(pre_buckets);
    23512509  //omfree(pre_buckets_len);
     
    23542512#endif
    23552513
    2356 static void noro_step(poly*p,int &pn,slimgb_alg* c){
     2514void noro_step(poly*p,int &pn,slimgb_alg* c){
    23572515  poly* reduced=(poly*) omalloc(pn*sizeof(poly));
    23582516  int j;
  • kernel/tgb_internal.h

    r508937 rcc4d094  
    55*  Computer Algebra System SINGULAR     *
    66****************************************/
    7 /* $Id: tgb_internal.h,v 1.50 2007-02-07 12:39:56 bricken Exp $ */
     7/* $Id: tgb_internal.h,v 1.51 2007-02-08 10:40:19 bricken Exp $ */
    88/*
    99 * ABSTRACT: tgb internal .h file
     
    1818#include "polys.h"
    1919#include "stdlib.h"
    20 #define USE_NORO 1
    21 //#define NORO_CACHE 1
     20//#define USE_NORO 1
     21#define NORO_CACHE 1
    2222#ifdef NORO_CACHE
    23 #include <map>
     23//#include <map>
    2424#include <vector>
    2525#endif
Note: See TracChangeset for help on using the changeset viewer.