Changeset a7d970 in git


Ignore:
Timestamp:
Feb 22, 2007, 11:45:12 AM (16 years ago)
Author:
Michael Brickenstein <bricken@…>
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
ebe987f7339e431a23e717106ffe22dacf14a1a2
Parents:
490afd567a4f8c21b1a8b7bff89f26c3053d6a38
Message:
*bricken: beginning templating arithmetic


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

Legend:

Unmodified
Added
Removed

  • Singular/claptmpl.cc

    r490afd5 ra7d970  
    33*  Computer Algebra System SINGULAR     *
    44****************************************/
    5 // $Id: claptmpl.cc,v 1.38 2007-02-21 10:14:11 bricken Exp $
     5// $Id: claptmpl.cc,v 1.39 2007-02-22 10:45:12 bricken Exp $
    66/*
    77* ABSTRACT - instantiation of all templates
    … …  
    227227//template class std::vector<std::vector<NoroPlaceHolder> >;
    228228template class std::vector<DataNoroCacheNode*>;
     229template SparseRow* noro_red_to_non_poly_t<unsigned char>(poly p, int &len, NoroCache* cache,slimgb_alg* c);
     230template SparseRow* noro_red_to_non_poly_t<unsigned short>(poly p, int &len, NoroCache* cache,slimgb_alg* c);
     231template SparseRow* noro_red_to_non_poly_t<unsigned int>(poly p, int &len, NoroCache* cache,slimgb_alg* c);
    229232//std::priority_queue<MonRedRes>
    230233#endif

  • kernel/tgb.cc

    r490afd5 ra7d970  
    55*  Computer Algebra System SINGULAR     *
    66****************************************/
    7 /* $Id: tgb.cc,v 1.144 2007-02-21 10:02:47 bricken Exp $ */
     7/* $Id: tgb.cc,v 1.145 2007-02-22 10:44:59 bricken Exp $ */
    88/*
    99* ABSTRACT: slimgb and F4 implementation
    … …  
    22172217
    22182218#ifdef NORO_CACHE
    2219 class NoroCacheNode{
    2220 public:
    2221   NoroCacheNode** branches;
    2222   int branches_len;
    2223 
    2224  
    2225   NoroCacheNode(){
    2226     branches=NULL;
    2227     branches_len=0;
    2228    
    2229   }
    2230   NoroCacheNode* setNode(int branch, NoroCacheNode* node){
    2231     if (branch>=branches_len){
    2232       if (branches==NULL){
    2233         branches_len=branch+1;
    2234         branches_len=si_max(branches_len,3);
    2235         branches=(NoroCacheNode**) omalloc(branches_len*sizeof(NoroCacheNode*));
    2236         int i;
    2237         for(i=0;i<branches_len;i++){
    2238           branches[i]=NULL;
    2239         }
    2240       }else{
    2241         int branches_len_old=branches_len;
    2242         branches_len=branch+1;
    2243         branches=(NoroCacheNode**) omrealloc(branches,branches_len*sizeof(NoroCacheNode*));
    2244         int i;
    2245         for(i=branches_len_old;i<branches_len;i++){
    2246           branches[i]=NULL;
    2247         }
    2248       }
    2249     }
    2250     assume(branches[branch]==NULL);
    2251     branches[branch]=node;
    2252     return node;
    2253   }
    2254   NoroCacheNode* getBranch(int branch){
    2255     if (branch<branches_len) return branches[branch];
    2256     return NULL;
    2257   }
    2258   virtual ~NoroCacheNode(){
    2259     int i;
    2260     for(i=0;i<branches_len;i++){
    2261       delete branches[i];
    2262     }
    2263     omfree(branches);
    2264   }
    2265   NoroCacheNode* getOrInsertBranch(int branch){
    2266     if ((branch<branches_len)&&(branches[branch]))
    2267       return branches[branch];
    2268     else{
    2269       return setNode(branch,new NoroCacheNode());
    2270     }
    2271   }
    2272 };
    2273 class DenseRow{
    2274 public:
    2275   number* array;
    2276   int begin;
    2277   int end;
    2278   DenseRow(){
    2279     array=NULL;
    2280   }
    2281   ~DenseRow(){
    2282     omfree(array);
    2283   }
    2284 };
    2285 class SparseRow{
    2286 public:
    2287   int* idx_array;
    2288   number* coef_array;
    2289   int len;
    2290   SparseRow(){
    2291     len=0;
    2292     idx_array=NULL;
    2293     coef_array=NULL;
    2294   }
    2295   SparseRow(int n){
    2296     len=n;
    2297     idx_array=(int*) omalloc(n*sizeof(int));
    2298     coef_array=(number*) omalloc(n*sizeof(number));
    2299   }
    2300   ~SparseRow(){
    2301     omfree(idx_array);
    2302     omfree(coef_array);
    2303   }
    2304 };
    2305 
    2306 class DataNoroCacheNode:public NoroCacheNode{
    2307 public:
    2308  
    2309   int value_len;
    2310   poly value_poly;
    2311   #ifdef NORO_SPARSE_ROWS_PRE
    2312   SparseRow* row;
    2313   #else
    2314   DenseRow* row;
    2315   #endif
    2316   int term_index;
    2317   DataNoroCacheNode(poly p, int len){
    2318     value_len=len;
    2319     value_poly=p;
    2320     row=NULL;
    2321     term_index=-1;
    2322   }
    2323   #ifdef NORO_SPARSE_ROWS_PRE
    2324   DataNoroCacheNode(SparseRow* row){
    2325     if (row!=NULL)
    2326       value_len=row->len;
    2327     else
    2328       value_len=0;
    2329     value_poly=NULL;
    2330     this->row=row;
    2331     term_index=-1;
    2332   }
    2333   #endif
    2334   ~DataNoroCacheNode(
    2335   ){
    2336     //p_Delete(&value_poly,currRing);
    2337     if (row) delete row;
    2338   }
    2339 };
    2340 class NoroCache{
    2341 public:
    2342   poly temp_term;
    2343   void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
    2344   void collectIrreducibleMonomials( std::vector<DataNoroCacheNode*>& res);
    2345   void collectIrreducibleMonomials(int level,  NoroCacheNode* node, std::vector<DataNoroCacheNode*>& res);
    2346   void evaluateRows();
    2347   void evaluateRows(int level, NoroCacheNode* node);
    2348 #ifdef NORO_RED_ARRAY_RESERVER
    2349   int reserved;
    2350   poly* recursionPolyBuffer;
    2351 #endif
    2352   static const int backLinkCode=-222;
    2353   DataNoroCacheNode* insert(poly term, poly nf, int len){
    2354     //assume(impl.find(p_Copy(term,currRing))==impl.end());
    2355     //assume(len==pLength(nf));
    2356     assume(npIsOne(p_GetCoeff(term,currRing)));
    2357     if (term==nf){
    2358       term=p_Copy(term,currRing);
    2359 
    2360       ressources.push_back(term);
    2361       nIrreducibleMonomials++;
    2362       return treeInsertBackLink(term);
    2363      
    2364     } else{
    2365      
    2366       if (nf){
    2367         //nf=p_Copy(nf,currRing);
    2368         assume(p_LmCmp(nf,term,currRing)==-1);
    2369         ressources.push_back(nf);
    2370       }
    2371       return treeInsert(term,nf,len);
    2372      
    2373     }
    2374    
    2375     //impl[term]=std::pair<PolySimple,int> (nf,len);
    2376   }
    2377   #ifdef NORO_SPARSE_ROWS_PRE
    2378   DataNoroCacheNode* insert(poly term, SparseRow* srow){
    2379     //assume(impl.find(p_Copy(term,currRing))==impl.end());
    2380     //assume(len==pLength(nf));
    2381 
    2382       return treeInsert(term,srow);
    2383      
    2384  
    2385     //impl[term]=std::pair<PolySimple,int> (nf,len);
    2386   }
    2387   #endif
    2388   DataNoroCacheNode* insertAndTransferOwnerShip(poly t, ring r){
    2389    
    2390     ressources.push_back(t);
    2391     DataNoroCacheNode* res=treeInsertBackLink(t);
    2392     res->term_index=nIrreducibleMonomials;
    2393     nIrreducibleMonomials++;
    2394     return res;
    2395   }
    2396   poly lookup(poly term, BOOLEAN& succ, int & len);
    2397   DataNoroCacheNode* getCacheReference(poly term);
    2398   NoroCache(){
    2399     buffer=NULL;
    2400 #ifdef NORO_RED_ARRAY_RESERVER
    2401     reserved=0;
    2402     recursionPolyBuffer=(poly*)omalloc(1000000*sizeof(poly));
    2403 #endif
    2404     nIrreducibleMonomials=0;
    2405     nReducibleMonomials=0;
    2406     temp_term=pOne();
    2407   }
    2408 #ifdef NORO_RED_ARRAY_RESERVER
    2409   poly* reserve(int n){
    2410     poly* res=recursionPolyBuffer+reserved;
    2411     reserved+=n;
    2412     return res;
    2413   }
    2414   void free(int n){
    2415     reserved-=n;
    2416   }
    2417 #endif
    2418   ~NoroCache(){
    2419     int s=ressources.size();
    2420     int i;
    2421     for(i=0;i<s;i++){
    2422       p_Delete(&ressources[i].impl,currRing);
    2423     }
    2424     p_Delete(&temp_term,currRing);
    2425 #ifdef NORO_RED_ARRAY_RESERVER
    2426     omfree(recursionPolyBuffer);
    2427 #endif
    2428   }
    2429  
    2430   int nIrreducibleMonomials;
    2431   int nReducibleMonomials;
    2432 protected:
    2433   DataNoroCacheNode* treeInsert(poly term,poly nf,int len){
    2434     int i;
    2435     nReducibleMonomials++;
    2436     int nvars=pVariables;
    2437     NoroCacheNode* parent=&root;
    2438     for(i=1;i<nvars;i++){
    2439       parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    2440     }
    2441     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(nf,len));
    2442   }
    2443   #ifdef NORO_SPARSE_ROWS_PRE
    2444   DataNoroCacheNode* treeInsert(poly term,SparseRow* srow){
    2445     int i;
    2446     nReducibleMonomials++;
    2447     int nvars=pVariables;
    2448     NoroCacheNode* parent=&root;
    2449     for(i=1;i<nvars;i++){
    2450       parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    2451     }
    2452     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(srow));
    2453   }
    2454   #endif
    2455   DataNoroCacheNode* treeInsertBackLink(poly term){
    2456     int i;
    2457     int nvars=pVariables;
    2458     NoroCacheNode* parent=&root;
    2459     for(i=1;i<nvars;i++){
    2460       parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
    2461     }
    2462     return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(term,backLinkCode));
    2463   }
    2464  
    2465   //@TODO descruct nodes;
    2466   typedef std::vector<PolySimple> poly_vec;
    2467   poly_vec ressources;
    2468   //typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map;
    2469   //cache_map impl;
    2470   NoroCacheNode root;
    2471   number* buffer;
    2472 };
    24732219void NoroCache::evaluateRows(){
    24742220  //after that can evaluate placeholders
    … …  
    29042650#ifdef NORO_SPARSE_ROWS_PRE
    29052651//len input and out: Idea: reverse addition
     2652
    29062653SparseRow* noro_red_to_non_poly(poly p, int &len, NoroCache* cache,slimgb_alg* c){
    2907   assume(len==pLength(p));
    2908   poly orig_p=p;
    2909   if (p==NULL) {
    2910     len=0;
    2911     return NULL;
    2912   }
    2913  
    2914   number zero=npInit(0);
    2915   MonRedResNP* mon=(MonRedResNP*) omalloc(len*sizeof(MonRedResNP));
    2916   int i=0;
    2917 
    2918   while(p){
    2919 
    2920     poly t=p;
    2921     pIter(p);
    2922     pNext(t)=NULL;
    2923    
    2924 #ifndef NDEBUG
    2925     number coef_debug=p_GetCoeff(t,currRing);
    2926 #endif
    2927     MonRedResNP red=noro_red_mon_to_non_poly(t,cache,c);
    2928     mon[i]=red;
    2929     i++;
    2930   }
    2931  
    2932   assume(i==len);
    2933   len=i;
    2934   //in the loop before nIrreducibleMonomials increases, so position here is important
    2935   number* temp_array=(number*) omalloc(cache->nIrreducibleMonomials*sizeof(number));
    2936   int temp_size=cache->nIrreducibleMonomials;
    2937   memset(temp_array,0,sizeof(number)*cache->nIrreducibleMonomials);
    2938   for(i=0;i<len;i++){
    2939     MonRedResNP red=mon[i];
    2940     if ((red.ref)){
    2941       if (red.ref->row){
    2942         SparseRow* row=red.ref->row;
    2943         number coef=red.coef;
    2944         int j;
    2945         if (!(npIsOne(coef))){
    2946         for(j=0;j<row->len;j++){
    2947           int idx=row->idx_array[j];
    2948           assume(!(npIsZero(coef)));
    2949           assume(!(npIsZero(row->coef_array[j])));
    2950           temp_array[idx]=npAddM(temp_array[idx],npMultM(row->coef_array[j],coef));
    2951           assume(idx<temp_size);
    2952         }}else{
    2953           for(j=0;j<row->len;j++){
    2954             int idx=row->idx_array[j];
    2955             temp_array[idx]=npAddM(temp_array[idx],row->coef_array[j]);
    2956             assume(idx<temp_size);
    2957           }
    2958         }
    2959       }
    2960       else{
    2961         if (red.ref->value_len==NoroCache::backLinkCode){
    2962           temp_array[red.ref->term_index]=npAddM(temp_array[red.ref->term_index],red.coef);
    2963         } else {
    2964           //PrintS("third case\n");
    2965         }
    2966       }
    2967     }
    2968   }
    2969   int non_zeros=0;
    2970   for(i=0;i<cache->nIrreducibleMonomials;i++){
    2971     if (!(temp_array[i]==zero)){
    2972       non_zeros++;
    2973     }
    2974   }
    2975   SparseRow* res=new SparseRow(non_zeros);
    2976   int pos=0;
    2977   for(i=0;i<cache->nIrreducibleMonomials;i++){
    2978     if (!(zero==temp_array[i])){
    2979    
    2980       res->idx_array[pos]=i;
    2981       res->coef_array[pos]=temp_array[i];
    2982 
    2983       pos++; 
    2984     }
    2985    
    2986   }
    2987   omfree(temp_array);
    2988 
    2989   omfree(mon);
    2990   return res;
     2654  if (npPrimeM<255){
     2655    return noro_red_to_non_poly_t<unsigned char>(p,len,cache,c);
     2656  } else {
     2657    if (npPrimeM<65000){
     2658      return noro_red_to_non_poly_t<unsigned short>(p,len,cache,c);
     2659    } else{
     2660      return noro_red_to_non_poly_t<unsigned int>(p,len,cache,c);
     2661    }
     2662  }
    29912663}
    29922664#endif
    … …  
    30152687#endif
    30162688
     2689
     2690
     2691
     2692
    30172693#endif
    3018 
    3019 
    3020 
    3021 
    30222694
    30232695#ifndef NORO_CACHE

  • kernel/tgb_internal.h

    r490afd5 ra7d970  
    55*  Computer Algebra System SINGULAR     *
    66****************************************/
    7 /* $Id: tgb_internal.h,v 1.55 2007-02-20 15:11:04 bricken Exp $ */
     7/* $Id: tgb_internal.h,v 1.56 2007-02-22 10:45:00 bricken Exp $ */
    88/*
    99 * ABSTRACT: tgb internal .h file
    … …  
    1818#include "polys.h"
    1919#include "stdlib.h"
     20#include <modulop.h>
    2021//#define USE_NORO 1
    21 //#define NORO_CACHE 1
    22 //#define NORO_SPARSE_ROWS_PRE 1
    23 //#define NORO_NON_POLY 1
     22#ifdef USE_NORO
     23#define NORO_CACHE 1
     24#define NORO_SPARSE_ROWS_PRE 1
     25#define NORO_NON_POLY 1
     26#endif
    2427#ifdef NORO_CACHE
    2528//#include <map>
    … …  
    388391
    389392}
    390 
    391 
     393#ifdef NORO_CACHE
     394typedef unsigned short tgb_uint16;
     395typedef unsigned char tgb_uint8;
     396typedef unsigned int tgb_uint32;
     397class NoroCacheNode{
     398public:
     399  NoroCacheNode** branches;
     400  int branches_len;
     401
     402 
     403  NoroCacheNode(){
     404    branches=NULL;
     405    branches_len=0;
     406   
     407  }
     408  NoroCacheNode* setNode(int branch, NoroCacheNode* node){
     409    if (branch>=branches_len){
     410      if (branches==NULL){
     411        branches_len=branch+1;
     412        branches_len=si_max(branches_len,3);
     413        branches=(NoroCacheNode**) omalloc(branches_len*sizeof(NoroCacheNode*));
     414        int i;
     415        for(i=0;i<branches_len;i++){
     416          branches[i]=NULL;
     417        }
     418      }else{
     419        int branches_len_old=branches_len;
     420        branches_len=branch+1;
     421        branches=(NoroCacheNode**) omrealloc(branches,branches_len*sizeof(NoroCacheNode*));
     422        int i;
     423        for(i=branches_len_old;i<branches_len;i++){
     424          branches[i]=NULL;
     425        }
     426      }
     427    }
     428    assume(branches[branch]==NULL);
     429    branches[branch]=node;
     430    return node;
     431  }
     432  NoroCacheNode* getBranch(int branch){
     433    if (branch<branches_len) return branches[branch];
     434    return NULL;
     435  }
     436  virtual ~NoroCacheNode(){
     437    int i;
     438    for(i=0;i<branches_len;i++){
     439      delete branches[i];
     440    }
     441    omfree(branches);
     442  }
     443  NoroCacheNode* getOrInsertBranch(int branch){
     444    if ((branch<branches_len)&&(branches[branch]))
     445      return branches[branch];
     446    else{
     447      return setNode(branch,new NoroCacheNode());
     448    }
     449  }
     450};
     451class DenseRow{
     452public:
     453  number* array;
     454  int begin;
     455  int end;
     456  DenseRow(){
     457    array=NULL;
     458  }
     459  ~DenseRow(){
     460    omfree(array);
     461  }
     462};
     463class SparseRow{
     464public:
     465  int* idx_array;
     466  number* coef_array;
     467  int len;
     468  SparseRow(){
     469    len=0;
     470    idx_array=NULL;
     471    coef_array=NULL;
     472  }
     473  SparseRow(int n){
     474    len=n;
     475    idx_array=(int*) omalloc(n*sizeof(int));
     476    coef_array=(number*) omalloc(n*sizeof(number));
     477  }
     478  ~SparseRow(){
     479    omfree(idx_array);
     480    omfree(coef_array);
     481  }
     482};
     483
     484class DataNoroCacheNode:public NoroCacheNode{
     485public:
     486 
     487  int value_len;
     488  poly value_poly;
     489  #ifdef NORO_SPARSE_ROWS_PRE
     490  SparseRow* row;
     491  #else
     492  DenseRow* row;
     493  #endif
     494  int term_index;
     495  DataNoroCacheNode(poly p, int len){
     496    value_len=len;
     497    value_poly=p;
     498    row=NULL;
     499    term_index=-1;
     500  }
     501  #ifdef NORO_SPARSE_ROWS_PRE
     502  DataNoroCacheNode(SparseRow* row){
     503    if (row!=NULL)
     504      value_len=row->len;
     505    else
     506      value_len=0;
     507    value_poly=NULL;
     508    this->row=row;
     509    term_index=-1;
     510  }
     511  #endif
     512  ~DataNoroCacheNode(
     513  ){
     514    //p_Delete(&value_poly,currRing);
     515    if (row) delete row;
     516  }
     517};
     518class NoroCache{
     519public:
     520  poly temp_term;
     521  void evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders);
     522  void collectIrreducibleMonomials( std::vector<DataNoroCacheNode*>& res);
     523  void collectIrreducibleMonomials(int level,  NoroCacheNode* node, std::vector<DataNoroCacheNode*>& res);
     524  void evaluateRows();
     525  void evaluateRows(int level, NoroCacheNode* node);
     526#ifdef NORO_RED_ARRAY_RESERVER
     527  int reserved;
     528  poly* recursionPolyBuffer;
     529#endif
     530  static const int backLinkCode=-222;
     531  DataNoroCacheNode* insert(poly term, poly nf, int len){
     532    //assume(impl.find(p_Copy(term,currRing))==impl.end());
     533    //assume(len==pLength(nf));
     534    assume(npIsOne(p_GetCoeff(term,currRing)));
     535    if (term==nf){
     536      term=p_Copy(term,currRing);
     537
     538      ressources.push_back(term);
     539      nIrreducibleMonomials++;
     540      return treeInsertBackLink(term);
     541     
     542    } else{
     543     
     544      if (nf){
     545        //nf=p_Copy(nf,currRing);
     546        assume(p_LmCmp(nf,term,currRing)==-1);
     547        ressources.push_back(nf);
     548      }
     549      return treeInsert(term,nf,len);
     550     
     551    }
     552   
     553    //impl[term]=std::pair<PolySimple,int> (nf,len);
     554  }
     555  #ifdef NORO_SPARSE_ROWS_PRE
     556  DataNoroCacheNode* insert(poly term, SparseRow* srow){
     557    //assume(impl.find(p_Copy(term,currRing))==impl.end());
     558    //assume(len==pLength(nf));
     559
     560      return treeInsert(term,srow);
     561     
     562 
     563    //impl[term]=std::pair<PolySimple,int> (nf,len);
     564  }
     565  #endif
     566  DataNoroCacheNode* insertAndTransferOwnerShip(poly t, ring r){
     567   
     568    ressources.push_back(t);
     569    DataNoroCacheNode* res=treeInsertBackLink(t);
     570    res->term_index=nIrreducibleMonomials;
     571    nIrreducibleMonomials++;
     572    return res;
     573  }
     574  poly lookup(poly term, BOOLEAN& succ, int & len);
     575  DataNoroCacheNode* getCacheReference(poly term);
     576  NoroCache(){
     577    buffer=NULL;
     578#ifdef NORO_RED_ARRAY_RESERVER
     579    reserved=0;
     580    recursionPolyBuffer=(poly*)omalloc(1000000*sizeof(poly));
     581#endif
     582    nIrreducibleMonomials=0;
     583    nReducibleMonomials=0;
     584    temp_term=pOne();
     585  }
     586#ifdef NORO_RED_ARRAY_RESERVER
     587  poly* reserve(int n){
     588    poly* res=recursionPolyBuffer+reserved;
     589    reserved+=n;
     590    return res;
     591  }
     592  void free(int n){
     593    reserved-=n;
     594  }
     595#endif
     596  ~NoroCache(){
     597    int s=ressources.size();
     598    int i;
     599    for(i=0;i<s;i++){
     600      p_Delete(&ressources[i].impl,currRing);
     601    }
     602    p_Delete(&temp_term,currRing);
     603#ifdef NORO_RED_ARRAY_RESERVER
     604    omfree(recursionPolyBuffer);
     605#endif
     606  }
     607 
     608  int nIrreducibleMonomials;
     609  int nReducibleMonomials;
     610protected:
     611  DataNoroCacheNode* treeInsert(poly term,poly nf,int len){
     612    int i;
     613    nReducibleMonomials++;
     614    int nvars=pVariables;
     615    NoroCacheNode* parent=&root;
     616    for(i=1;i<nvars;i++){
     617      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
     618    }
     619    return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(nf,len));
     620  }
     621  #ifdef NORO_SPARSE_ROWS_PRE
     622  DataNoroCacheNode* treeInsert(poly term,SparseRow* srow){
     623    int i;
     624    nReducibleMonomials++;
     625    int nvars=pVariables;
     626    NoroCacheNode* parent=&root;
     627    for(i=1;i<nvars;i++){
     628      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
     629    }
     630    return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(srow));
     631  }
     632  #endif
     633  DataNoroCacheNode* treeInsertBackLink(poly term){
     634    int i;
     635    int nvars=pVariables;
     636    NoroCacheNode* parent=&root;
     637    for(i=1;i<nvars;i++){
     638      parent=parent->getOrInsertBranch(p_GetExp(term,i,currRing));
     639    }
     640    return (DataNoroCacheNode*) parent->setNode(p_GetExp(term,nvars,currRing),new DataNoroCacheNode(term,backLinkCode));
     641  }
     642 
     643  //@TODO descruct nodes;
     644  typedef std::vector<PolySimple> poly_vec;
     645  poly_vec ressources;
     646  //typedef std::map<PolySimple,std::pair<PolySimple,int> > cache_map;
     647  //cache_map impl;
     648  NoroCacheNode root;
     649  number* buffer;
     650};
     651MonRedResNP noro_red_mon_to_non_poly(poly t,  NoroCache* cache,slimgb_alg* c);
     652template<class storage_type> SparseRow* noro_red_to_non_poly_t(poly p, int &len, NoroCache* cache,slimgb_alg* c){
     653  assume(len==pLength(p));
     654  poly orig_p=p;
     655  if (p==NULL) {
     656    len=0;
     657    return NULL;
     658  }
     659 
     660  number zero=npInit(0);
     661  MonRedResNP* mon=(MonRedResNP*) omalloc(len*sizeof(MonRedResNP));
     662  int i=0;
     663
     664  while(p){
     665
     666    poly t=p;
     667    pIter(p);
     668    pNext(t)=NULL;
     669   
     670#ifndef NDEBUG
     671    number coef_debug=p_GetCoeff(t,currRing);
     672#endif
     673    MonRedResNP red=noro_red_mon_to_non_poly(t,cache,c);
     674    mon[i]=red;
     675    i++;
     676  }
     677 
     678  assume(i==len);
     679  len=i;
     680  //in the loop before nIrreducibleMonomials increases, so position here is important
     681  storage_type* temp_array=(storage_type*) omalloc(cache->nIrreducibleMonomials*sizeof(storage_type));
     682  int temp_size=cache->nIrreducibleMonomials;
     683  memset(temp_array,0,sizeof(storage_type)*cache->nIrreducibleMonomials);
     684  for(i=0;i<len;i++){
     685    MonRedResNP red=mon[i];
     686    if ((red.ref)){
     687      if (red.ref->row){
     688        SparseRow* row=red.ref->row;
     689        number coef=red.coef;
     690        int j;
     691        if (!(npIsOne(coef))){
     692        for(j=0;j<row->len;j++){
     693          int idx=row->idx_array[j];
     694          assume(!(npIsZero(coef)));
     695          assume(!(npIsZero(row->coef_array[j])));
     696          temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],npMultM(row->coef_array[j],coef));
     697          assume(idx<temp_size);
     698        }}else{
     699          for(j=0;j<row->len;j++){
     700            int idx=row->idx_array[j];
     701            temp_array[idx]=(storage_type) (unsigned int) npAddM((number) temp_array[idx],row->coef_array[j]);
     702            assume(idx<temp_size);
     703          }
     704        }
     705      }
     706      else{
     707        if (red.ref->value_len==NoroCache::backLinkCode){
     708          temp_array[red.ref->term_index]=(storage_type) (unsigned int) npAddM((number) temp_array[red.ref->term_index],red.coef);
     709        } else {
     710          //PrintS("third case\n");
     711        }
     712      }
     713    }
     714  }
     715  int non_zeros=0;
     716  for(i=0;i<cache->nIrreducibleMonomials;i++){
     717    if (!(temp_array[i]==0)){
     718      non_zeros++;
     719    }
     720  }
     721  SparseRow* res=new SparseRow(non_zeros);
     722  int pos=0;
     723  for(i=0;i<cache->nIrreducibleMonomials;i++){
     724    if (!(0==temp_array[i])){
     725   
     726      res->idx_array[pos]=i;
     727      res->coef_array[pos]=(number) temp_array[i];
     728
     729      pos++; 
     730    }
     731   
     732  }
     733  omfree(temp_array);
     734
     735  omfree(mon);
     736  return res;
     737}
     738#endif
    392739static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c);
    393740wlen_type pELength(poly p, ring r);
    394741void simplest_gauss_modp(number* a, int nrows,int ncols);
     742
    395743// a: a[0,0],a[0,1]....a[nrows-1,ncols-1]
    396744// assume: field is Zp
Note: See TracChangeset for help on using the changeset viewer.