Changeset c70e58 in git
 Timestamp:
 Feb 14, 2005, 11:03:41 AM (18 years ago)
 Branches:
 (u'jengelhdatetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '00e2e9c41af3fde1273eb3633f4c0c7c3db2579d')
 Children:
 aa07a05c3a08e7bfc7d1e1326b8bfe6f74ab6430
 Parents:
 446c2dec291872c3568905658dd37d52142edc62
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

kernel/fast_mult.cc
r446c2d rc70e58 2 2 #include "kbuckets.h" 3 3 static const int pass_option=1; 4 static void degsplit(poly p,int n,poly &p1,poly&p2 ){4 static void degsplit(poly p,int n,poly &p1,poly&p2, int vn){ 5 5 poly erg1_i, erg2_i; 6 6 erg1_i=NULL; 7 7 erg2_i=NULL; 8 8 while(p){ 9 if(pGetExp(p, 1)>=n){9 if(pGetExp(p,vn)>=n){ 10 10 if (p1==NULL){ 11 11 p1=p; … … 32 32 33 33 } 34 static void div_by_x_power_n(poly p, int n ){34 static void div_by_x_power_n(poly p, int n, int vn){ 35 35 while(p){ 36 assume(pGetExp(p, 1)>=n);37 int e=pGetExp(p, 1);38 pSetExp(p, 1,en);36 assume(pGetExp(p,vn)>=n); 37 int e=pGetExp(p,vn); 38 pSetExp(p,vn,en); 39 39 p=pNext(p); 40 40 } 41 41 } 42 42 43 poly do_unifastmult(poly f, poly g){43 poly do_unifastmult(poly f,int df,poly g,int dg, int vn){ 44 44 int n=1; 45 45 if ((f==NULL)(g==NULL)) return NULL; 46 int df=pGetExp(f,1);//pFDeg(f);47 int dg=pGetExp(g,1);//pFDeg(g);46 //int df=pGetExp(f,vn);//pFDeg(f); 47 // int dg=pGetExp(g,vn);//pFDeg(g); 48 48 49 49 int dm; … … 68 68 poly f1=NULL; 69 69 poly f0=NULL;//f(x^(pot)*F1); 70 degsplit(pCopy(f),pot,f1,f0 );71 div_by_x_power_n(f1,pot );70 degsplit(pCopy(f),pot,f1,f0,vn); 71 div_by_x_power_n(f1,pot,vn); 72 72 73 73 poly g1=NULL; 74 74 poly g0=NULL; 75 degsplit(pCopy(g),pot,g1,g0 );76 div_by_x_power_n(g1,pot );75 degsplit(pCopy(g),pot,g1,g0,vn); 76 div_by_x_power_n(g1,pot,vn); 77 77 78 78 //p00, p11 … … 84 84 poly factor=pOne(); 85 85 86 pSetExp(factor, 1,n);86 pSetExp(factor,vn,n); 87 87 erg=ppMult_mm(p11,factor); 88 88 erg=pAdd(erg,pCopy(p00)); … … 101 101 //eat up pbig 102 102 poly sum=pbig; 103 pSetExp(factor, 1,pot);103 pSetExp(factor,vn,pot); 104 104 105 105 //eat up p00 … … 119 119 poly s1=unifastmult(f0,g1); 120 120 poly s2=unifastmult(g0,f1); 121 pSetExp(factor, 1,pot);121 pSetExp(factor,vn,pot); 122 122 poly h=pMult_mm(((s1!=NULL)?s1:s2),factor); 123 123 pDelete(&f1); … … 136 136 } 137 137 138 poly do_unifastmult_buckets(poly f,poly g){138 // poly do_unifastmult_buckets(poly f,poly g){ 139 139 140 140 141 141 142 142 143 int n=1;144 if ((f==NULL)(g==NULL)) return NULL;145 int df=pGetExp(f,1);//pFDeg(f);146 int dg=pGetExp(g,1);//pFDeg(g);143 // int n=1; 144 // if ((f==NULL)(g==NULL)) return NULL; 145 // int df=pGetExp(f,1);//pFDeg(f); 146 // int dg=pGetExp(g,1);//pFDeg(g); 147 147 148 int dm;149 if(df>dg){150 dm=df;151 }else{152 dm=dg;153 }154 while(n<=dm)155 {156 n*=2;157 }158 int pseudo_len=0;159 if(n==1){160 return ppMult_qq(f,g);161 162 }163 kBucket_pt erg_bucket= kBucketCreate(currRing);164 kBucketInit(erg_bucket,NULL,0 /*pLength(P.p)*/);165 166 int pot=n/2;167 assume(pot*2==n);168 169 170 //splitting171 poly f1=NULL;172 poly f0=NULL;//f(x^(pot)*F1);173 degsplit(pCopy(f),pot,f1,f0);174 div_by_x_power_n(f1,pot);175 poly g1=NULL;176 poly g0=NULL;177 degsplit(pCopy(g),pot,g1,g0);178 div_by_x_power_n(g1,pot);179 180 //p00181 //p11182 poly p00=unifastmult(f0,g0);183 poly p11=unifastmult(f1,g1);184 185 186 187 188 //eat up f0,f1,g0,g1189 poly pbig=unifastmult(pAdd(f0,f1),pAdd(g0,g1));190 poly factor=pOne();//pCopy(erg_mult);191 pSetExp(factor,1,n);192 pseudo_len=0;193 kBucket_Add_q(erg_bucket,ppMult_mm(p11,factor),&pseudo_len);194 pseudo_len=0;195 kBucket_Add_q(erg_bucket,pCopy(p00),&pseudo_len);196 pSetExp(factor,1,pot);197 198 //eat up pbig199 pseudo_len=0;200 kBucket_Add_q(erg_bucket,pMult_mm(pbig,factor),&pseudo_len);201 pseudo_len=0;202 //eat up p00203 kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p00),factor),&pseudo_len);204 pseudo_len=0;205 //eat up p11206 kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p11),factor),&pseudo_len);207 208 209 pseudo_len=0;210 211 212 pDelete(&factor);213 214 int len=0;215 poly erg=NULL;216 kBucketClear(erg_bucket,&erg,&len);217 kBucketDestroy(&erg_bucket);218 219 return erg;220 }148 // int dm; 149 // if(df>dg){ 150 // dm=df; 151 // }else{ 152 // dm=dg; 153 // } 154 // while(n<=dm) 155 // { 156 // n*=2; 157 // } 158 // int pseudo_len=0; 159 // if(n==1){ 160 // return ppMult_qq(f,g); 161 162 // } 163 // kBucket_pt erg_bucket= kBucketCreate(currRing); 164 // kBucketInit(erg_bucket,NULL,0 /*pLength(P.p)*/); 165 166 // int pot=n/2; 167 // assume(pot*2==n); 168 169 170 // //splitting 171 // poly f1=NULL; 172 // poly f0=NULL;//f(x^(pot)*F1); 173 // degsplit(pCopy(f),pot,f1,f0); 174 // div_by_x_power_n(f1,pot); 175 // poly g1=NULL; 176 // poly g0=NULL; 177 // degsplit(pCopy(g),pot,g1,g0); 178 // div_by_x_power_n(g1,pot); 179 180 // //p00 181 // //p11 182 // poly p00=unifastmult(f0,g0); 183 // poly p11=unifastmult(f1,g1); 184 185 186 187 188 // //eat up f0,f1,g0,g1 189 // poly pbig=unifastmult(pAdd(f0,f1),pAdd(g0,g1)); 190 // poly factor=pOne();//pCopy(erg_mult); 191 // pSetExp(factor,1,n); 192 // pseudo_len=0; 193 // kBucket_Add_q(erg_bucket,ppMult_mm(p11,factor),&pseudo_len); 194 // pseudo_len=0; 195 // kBucket_Add_q(erg_bucket,pCopy(p00),&pseudo_len); 196 // pSetExp(factor,1,pot); 197 198 // //eat up pbig 199 // pseudo_len=0; 200 // kBucket_Add_q(erg_bucket,pMult_mm(pbig,factor),&pseudo_len); 201 // pseudo_len=0; 202 // //eat up p00 203 // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p00),factor),&pseudo_len); 204 // pseudo_len=0; 205 // //eat up p11 206 // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p11),factor),&pseudo_len); 207 208 209 // pseudo_len=0; 210 211 212 // pDelete(&factor); 213 214 // int len=0; 215 // poly erg=NULL; 216 // kBucketClear(erg_bucket,&erg,&len); 217 // kBucketDestroy(&erg_bucket); 218 219 // return erg; 220 // } 221 221 poly unifastmult(poly f,poly g){ 222 int vn=1; 222 223 if((f==NULL)(g==NULL)) return NULL; 223 int df=pGetExp(f, 1);224 int dg=pGetExp(g, 1);225 if ((df== 1)(dg==1))224 int df=pGetExp(f,vn); 225 int dg=pGetExp(g,vn); 226 if ((df==0)(dg==0)) 226 227 return ppMult_qq(f,g); 227 228 if (df*dg<100) … … 231 232 // do_unifastmult_buckets(f,g); 232 233 //else 233 return do_unifastmult(f, g);234 235 } 236 234 return do_unifastmult(f,df,g,dg,vn); 235 236 } 237
Note: See TracChangeset
for help on using the changeset viewer.