1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | #ifdef HAVE_CONFIG_H |
---|
5 | #include "config.h" |
---|
6 | #endif /* HAVE_CONFIG_H */ |
---|
7 | #include "mod2.h" |
---|
8 | #include <polys/monomials/ring.h> |
---|
9 | #include <kernel/fast_mult.h> |
---|
10 | #include <polys/kbuckets.h> |
---|
11 | #include <kernel/febase.h> |
---|
12 | |
---|
13 | typedef poly fastmultrec(poly f, poly g, ring r); |
---|
14 | static const int pass_option=1; |
---|
15 | static int mults=0; |
---|
16 | int Mults() |
---|
17 | { |
---|
18 | return mults; |
---|
19 | } |
---|
20 | static void degsplit(poly p,int n,poly &p1,poly&p2, int vn, ring r) |
---|
21 | { |
---|
22 | poly erg1_i, erg2_i; |
---|
23 | erg1_i=NULL; |
---|
24 | erg2_i=NULL; |
---|
25 | while(p) |
---|
26 | { |
---|
27 | if(p_GetExp(p,vn,r)>=n) |
---|
28 | { |
---|
29 | if (p1==NULL) |
---|
30 | { |
---|
31 | p1=p; |
---|
32 | } |
---|
33 | else |
---|
34 | { |
---|
35 | pNext(erg1_i)=p; |
---|
36 | } |
---|
37 | erg1_i=p; |
---|
38 | } |
---|
39 | else |
---|
40 | { |
---|
41 | if (p2==NULL) |
---|
42 | { |
---|
43 | p2=p; |
---|
44 | } |
---|
45 | else |
---|
46 | { |
---|
47 | pNext(erg2_i)=p; |
---|
48 | } |
---|
49 | erg2_i=p; |
---|
50 | } |
---|
51 | p=pNext(p); |
---|
52 | } |
---|
53 | if(erg2_i) |
---|
54 | { |
---|
55 | pNext(erg2_i)=NULL; |
---|
56 | } |
---|
57 | if (erg1_i) |
---|
58 | { |
---|
59 | pNext(erg1_i)=NULL; |
---|
60 | } |
---|
61 | |
---|
62 | } |
---|
63 | static void div_by_x_power_n(poly p, int n, int vn, ring r) |
---|
64 | { |
---|
65 | while(p) |
---|
66 | { |
---|
67 | assume(p_GetExp(p,vn,r)>=n); |
---|
68 | int e=p_GetExp(p,vn,r); |
---|
69 | p_SetExp(p,vn,e-n,r); |
---|
70 | p=pNext(p); |
---|
71 | } |
---|
72 | } |
---|
73 | |
---|
74 | static poly do_unifastmult(poly f,int df,poly g,int dg, int vn, fastmultrec rec, ring r) |
---|
75 | { |
---|
76 | int n=1; |
---|
77 | if ((f==NULL)||(g==NULL)) return NULL; |
---|
78 | //int df=pGetExp(f,vn);//pFDeg(f); |
---|
79 | // int dg=pGetExp(g,vn);//pFDeg(g); |
---|
80 | |
---|
81 | int dm; |
---|
82 | if(df>dg) |
---|
83 | { |
---|
84 | dm=df; |
---|
85 | } |
---|
86 | else |
---|
87 | { |
---|
88 | dm=dg; |
---|
89 | } |
---|
90 | while(n<=dm) |
---|
91 | { |
---|
92 | n*=2; |
---|
93 | } |
---|
94 | if(n==1) |
---|
95 | { |
---|
96 | return(pp_Mult_qq(f,g,r)); |
---|
97 | } |
---|
98 | |
---|
99 | int pot=n/2; |
---|
100 | assume(pot*2==n); |
---|
101 | |
---|
102 | |
---|
103 | //splitting |
---|
104 | poly f1=NULL; |
---|
105 | poly f0=NULL;//f-(x^(pot)*F1); |
---|
106 | degsplit(p_Copy(f,r),pot,f1,f0,vn,r); |
---|
107 | div_by_x_power_n(f1,pot,vn,r); |
---|
108 | |
---|
109 | poly g1=NULL; |
---|
110 | poly g0=NULL; |
---|
111 | degsplit(p_Copy(g,r),pot,g1,g0,vn,r); |
---|
112 | div_by_x_power_n(g1,pot,vn,r); |
---|
113 | |
---|
114 | //p00, p11 |
---|
115 | poly p00=rec(f0,g0,r);//unifastmult(f0,g0); |
---|
116 | poly p11=rec(f1,g1,r); |
---|
117 | |
---|
118 | //construct erg, factor |
---|
119 | poly erg=NULL; |
---|
120 | poly factor=p_ISet(1,r); |
---|
121 | |
---|
122 | p_SetExp(factor,vn,n,r); |
---|
123 | erg=pp_Mult_mm(p11,factor,r); |
---|
124 | erg=p_Add_q(erg,p_Copy(p00,r),r); |
---|
125 | |
---|
126 | |
---|
127 | |
---|
128 | |
---|
129 | |
---|
130 | if((f1!=NULL) &&(f0!=NULL) &&(g0!=NULL) && (g1!=NULL)) |
---|
131 | { |
---|
132 | //if(true){ |
---|
133 | //eat up f0,f1,g0,g1 |
---|
134 | poly s1=p_Add_q(f0,f1,r); |
---|
135 | poly s2=p_Add_q(g0,g1,r); |
---|
136 | poly pbig=rec(s1,s2,r); |
---|
137 | p_Delete(&s1,r); |
---|
138 | p_Delete(&s2,r); |
---|
139 | |
---|
140 | |
---|
141 | //eat up pbig |
---|
142 | poly sum=pbig; |
---|
143 | p_SetExp(factor,vn,pot,r); |
---|
144 | |
---|
145 | //eat up p00 |
---|
146 | sum=p_Add_q(sum,p_Neg(p00,r),r); |
---|
147 | |
---|
148 | //eat up p11 |
---|
149 | sum=p_Add_q(sum,p_Neg(p11,r),r); |
---|
150 | |
---|
151 | |
---|
152 | sum=p_Mult_mm(sum,factor,r); |
---|
153 | |
---|
154 | |
---|
155 | //eat up sum |
---|
156 | erg=p_Add_q(sum,erg,r); |
---|
157 | } |
---|
158 | else |
---|
159 | { |
---|
160 | //eat up f0,f1,g0,g1 |
---|
161 | poly s1=rec(f0,g1,r); |
---|
162 | poly s2=rec(g0,f1,r); |
---|
163 | p_SetExp(factor,vn,pot,r); |
---|
164 | poly h=p_Mult_mm(((s1!=NULL)?s1:s2),factor,r); |
---|
165 | p_Delete(&f1,r); |
---|
166 | p_Delete(&f0,r); |
---|
167 | p_Delete(&g0,r); |
---|
168 | p_Delete(&g1,r); |
---|
169 | p_Delete(&p00,r); |
---|
170 | p_Delete(&p11,r); |
---|
171 | erg=p_Add_q(erg,h,r); |
---|
172 | } |
---|
173 | |
---|
174 | |
---|
175 | p_Delete(&factor,r); |
---|
176 | |
---|
177 | |
---|
178 | |
---|
179 | return(erg); |
---|
180 | } |
---|
181 | |
---|
182 | // poly do_unifastmult_buckets(poly f,poly g){ |
---|
183 | |
---|
184 | |
---|
185 | |
---|
186 | |
---|
187 | // int n=1; |
---|
188 | // if ((f==NULL)||(g==NULL)) return NULL; |
---|
189 | // int df=pGetExp(f,1);//pFDeg(f); |
---|
190 | // int dg=pGetExp(g,1);//pFDeg(g); |
---|
191 | |
---|
192 | // int dm; |
---|
193 | // if(df>dg){ |
---|
194 | // dm=df; |
---|
195 | // }else{ |
---|
196 | // dm=dg; |
---|
197 | // } |
---|
198 | // while(n<=dm) |
---|
199 | // { |
---|
200 | // n*=2; |
---|
201 | // } |
---|
202 | // int pseudo_len=0; |
---|
203 | // if(n==1){ |
---|
204 | // return ppMult_qq(f,g); |
---|
205 | |
---|
206 | // } |
---|
207 | // kBucket_pt erg_bucket= kBucketCreate(currRing); |
---|
208 | // kBucketInit(erg_bucket,NULL,0 /*pLength(P.p)*/); |
---|
209 | |
---|
210 | // int pot=n/2; |
---|
211 | // assume(pot*2==n); |
---|
212 | |
---|
213 | |
---|
214 | // //splitting |
---|
215 | // poly f1=NULL; |
---|
216 | // poly f0=NULL;//f-(x^(pot)*F1); |
---|
217 | // degsplit(pCopy(f),pot,f1,f0); |
---|
218 | // div_by_x_power_n(f1,pot); |
---|
219 | // poly g1=NULL; |
---|
220 | // poly g0=NULL; |
---|
221 | // degsplit(pCopy(g),pot,g1,g0); |
---|
222 | // div_by_x_power_n(g1,pot); |
---|
223 | |
---|
224 | // //p00 |
---|
225 | // //p11 |
---|
226 | // poly p00=unifastmult(f0,g0); |
---|
227 | // poly p11=unifastmult(f1,g1); |
---|
228 | |
---|
229 | |
---|
230 | |
---|
231 | |
---|
232 | // //eat up f0,f1,g0,g1 |
---|
233 | // poly pbig=unifastmult(pAdd(f0,f1),pAdd(g0,g1)); |
---|
234 | // poly factor=pOne();//pCopy(erg_mult); |
---|
235 | // pSetExp(factor,1,n); |
---|
236 | // pseudo_len=0; |
---|
237 | // kBucket_Add_q(erg_bucket,ppMult_mm(p11,factor),&pseudo_len); |
---|
238 | // pseudo_len=0; |
---|
239 | // kBucket_Add_q(erg_bucket,pCopy(p00),&pseudo_len); |
---|
240 | // pSetExp(factor,1,pot); |
---|
241 | |
---|
242 | // //eat up pbig |
---|
243 | // pseudo_len=0; |
---|
244 | // kBucket_Add_q(erg_bucket,pMult_mm(pbig,factor),&pseudo_len); |
---|
245 | // pseudo_len=0; |
---|
246 | // //eat up p00 |
---|
247 | // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p00),factor),&pseudo_len); |
---|
248 | // pseudo_len=0; |
---|
249 | // //eat up p11 |
---|
250 | // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p11),factor),&pseudo_len); |
---|
251 | |
---|
252 | |
---|
253 | // pseudo_len=0; |
---|
254 | |
---|
255 | |
---|
256 | // pDelete(&factor); |
---|
257 | |
---|
258 | // int len=0; |
---|
259 | // poly erg=NULL; |
---|
260 | // kBucketClear(erg_bucket,&erg,&len); |
---|
261 | // kBucketDestroy(&erg_bucket); |
---|
262 | |
---|
263 | // return erg; |
---|
264 | // } |
---|
265 | |
---|
266 | static inline int max(int a, int b) |
---|
267 | { |
---|
268 | return (a>b)? a:b; |
---|
269 | } |
---|
270 | static inline int min(int a, int b) |
---|
271 | { |
---|
272 | return (a>b)? b:a; |
---|
273 | } |
---|
274 | poly unifastmult(poly f,poly g, ring r) |
---|
275 | { |
---|
276 | int vn=1; |
---|
277 | if((f==NULL)||(g==NULL)) return NULL; |
---|
278 | int df=p_GetExp(f,vn,r); |
---|
279 | int dg=p_GetExp(g,vn,r); |
---|
280 | if ((df==0)||(dg==0)) |
---|
281 | return pp_Mult_qq(f,g,r); |
---|
282 | if (df*dg<100) |
---|
283 | return pp_Mult_qq(f,g,r); |
---|
284 | // if (df*dg>10000) |
---|
285 | // return |
---|
286 | // do_unifastmult_buckets(f,g); |
---|
287 | //else |
---|
288 | return do_unifastmult(f,df,g,dg,vn,unifastmult,r); |
---|
289 | |
---|
290 | } |
---|
291 | |
---|
292 | poly multifastmult(poly f, poly g, ring r) |
---|
293 | { |
---|
294 | mults++; |
---|
295 | if((f==NULL)||(g==NULL)) return NULL; |
---|
296 | if (pLength(f)*pLength(g)<100) |
---|
297 | return pp_Mult_qq(f,g,r); |
---|
298 | //find vn |
---|
299 | //determine df,dg simultaneously |
---|
300 | int i; |
---|
301 | int can_i=-1; |
---|
302 | int can_df=0; |
---|
303 | int can_dg=0; |
---|
304 | int can_crit=0; |
---|
305 | for(i=1;i<=rVar(r);i++) |
---|
306 | { |
---|
307 | poly p; |
---|
308 | int df=0; |
---|
309 | int dg=0; |
---|
310 | //max min max Strategie |
---|
311 | p=f; |
---|
312 | while(p) |
---|
313 | { |
---|
314 | df=max(df,p_GetExp(p,i,r)); |
---|
315 | p=pNext(p); |
---|
316 | } |
---|
317 | if(df>can_crit) |
---|
318 | { |
---|
319 | p=g; |
---|
320 | while(p) |
---|
321 | { |
---|
322 | dg=max(dg,p_GetExp(p,i,r)); |
---|
323 | p=pNext(p); |
---|
324 | } |
---|
325 | int crit=min(df,dg); |
---|
326 | if (crit>can_crit) |
---|
327 | { |
---|
328 | can_crit=crit; |
---|
329 | can_i=i; |
---|
330 | can_df=df; |
---|
331 | can_dg=dg; |
---|
332 | } |
---|
333 | } |
---|
334 | } |
---|
335 | if(can_crit==0) |
---|
336 | return pp_Mult_qq(f,g,r); |
---|
337 | else |
---|
338 | { |
---|
339 | poly erg=do_unifastmult(f,can_df,g,can_dg,can_i,multifastmult,r); |
---|
340 | p_Normalize(erg,r); |
---|
341 | return(erg); |
---|
342 | } |
---|
343 | } |
---|
344 | poly pFastPower(poly f, int n, ring r) |
---|
345 | { |
---|
346 | if (n==1) return f; |
---|
347 | if (n==0) return p_ISet(1,r); |
---|
348 | assume(n>=0); |
---|
349 | int i_max=1; |
---|
350 | int pot_max=0; |
---|
351 | while(i_max*2<=n) |
---|
352 | { |
---|
353 | i_max*=2; |
---|
354 | pot_max++; |
---|
355 | } |
---|
356 | int field_size=pot_max+1; |
---|
357 | int* int_pot_array=(int*) omAlloc(field_size*sizeof(int)); |
---|
358 | poly* pot_array=(poly*) omAlloc(field_size*sizeof(poly)); |
---|
359 | int i; |
---|
360 | int pot=1; |
---|
361 | //initializing int_pot |
---|
362 | for(i=0;i<field_size;i++) |
---|
363 | { |
---|
364 | int_pot_array[i]=pot; |
---|
365 | pot*=2; |
---|
366 | } |
---|
367 | //calculating pot_array |
---|
368 | pot_array[0]=f; //do not delete it |
---|
369 | for(i=1;i<field_size;i++) |
---|
370 | { |
---|
371 | poly p=pot_array[i-1]; |
---|
372 | if(rVar(r)==1) |
---|
373 | pot_array[i]=multifastmult(p,p,r); |
---|
374 | else |
---|
375 | pot_array[i]=pp_Mult_qq(p,p,r); |
---|
376 | } |
---|
377 | |
---|
378 | |
---|
379 | |
---|
380 | int work_n=n; |
---|
381 | assume(work_n>=int_pot_array[field_size-1]); |
---|
382 | poly erg=p_ISet(1,r); |
---|
383 | |
---|
384 | |
---|
385 | //forward maybe faster, later |
---|
386 | // for(i=field_size-1;i>=0;i--){ |
---|
387 | |
---|
388 | // assume(work_n<2*int_pot_array[i]); |
---|
389 | // if(int_pot_array[i]<=work_n){ |
---|
390 | // work_n-=int_pot_array[i]; |
---|
391 | // poly prod=multifastmult(erg,pot_array[i],r); |
---|
392 | // pDelete(&erg); |
---|
393 | // erg=prod; |
---|
394 | // } |
---|
395 | |
---|
396 | // if(i!=0) pDelete(&pot_array[i]); |
---|
397 | // } |
---|
398 | |
---|
399 | |
---|
400 | for(i=field_size-1;i>=0;i--) |
---|
401 | { |
---|
402 | |
---|
403 | assume(work_n<2*int_pot_array[i]); |
---|
404 | if(int_pot_array[i]<=work_n) |
---|
405 | { |
---|
406 | work_n-=int_pot_array[i]; |
---|
407 | int_pot_array[i]=1; |
---|
408 | } |
---|
409 | else int_pot_array[i]=0; |
---|
410 | |
---|
411 | } |
---|
412 | for(i=0;i<field_size;i++) |
---|
413 | { |
---|
414 | if(int_pot_array[i]==1) |
---|
415 | { |
---|
416 | poly prod; |
---|
417 | if(rVar(r)==1) |
---|
418 | prod=multifastmult(erg,pot_array[i],r); |
---|
419 | else |
---|
420 | prod=pp_Mult_qq(erg,pot_array[i],r); |
---|
421 | pDelete(&erg); |
---|
422 | erg=prod; |
---|
423 | } |
---|
424 | if(i!=0) pDelete(&pot_array[i]); |
---|
425 | } |
---|
426 | //free res |
---|
427 | omfree(pot_array); |
---|
428 | omfree(int_pot_array); |
---|
429 | return erg; |
---|
430 | } |
---|
431 | static omBin lm_bin=NULL; |
---|
432 | /*3 |
---|
433 | * compute for monomials p*q |
---|
434 | * destroys p, keeps q |
---|
435 | */ |
---|
436 | static void p_MonMultMB(poly p, poly q,ring r) |
---|
437 | { |
---|
438 | number x, y; |
---|
439 | // int i; |
---|
440 | |
---|
441 | y = p_GetCoeff(p,r); |
---|
442 | x = n_Mult(y,pGetCoeff(q),r->cf); |
---|
443 | n_Delete(&y,r->cf); |
---|
444 | p_SetCoeff0(p,x,r); |
---|
445 | //for (i=(currRing->N); i!=0; i--) |
---|
446 | //{ |
---|
447 | // pAddExp(p,i, pGetExp(q,i)); |
---|
448 | //} |
---|
449 | //p->Order += q->Order; |
---|
450 | p_ExpVectorAdd(p,q,r); |
---|
451 | } |
---|
452 | /*3 |
---|
453 | * compute for monomials p*q |
---|
454 | * keeps p, q |
---|
455 | * uses bin only available in MCPower |
---|
456 | */ |
---|
457 | static poly p_MonMultCMB(poly p, poly q, ring r) |
---|
458 | { |
---|
459 | number x; |
---|
460 | poly res = p_Init(r,lm_bin); |
---|
461 | |
---|
462 | x = n_Mult(p_GetCoeff(p,r),p_GetCoeff(q,r),r->cf); |
---|
463 | p_SetCoeff0(res,x,r); |
---|
464 | p_ExpVectorSum(res,p, q,r); |
---|
465 | return res; |
---|
466 | } |
---|
467 | static poly p_MonPowerMB(poly p, int exp, ring r) |
---|
468 | { |
---|
469 | int i; |
---|
470 | |
---|
471 | if(!n_IsOne(p_GetCoeff(p,r),r->cf)) |
---|
472 | { |
---|
473 | number x, y; |
---|
474 | y = p_GetCoeff(p,r); |
---|
475 | n_Power(y,exp,&x,r->cf); |
---|
476 | n_Delete(&y,r->cf); |
---|
477 | p_SetCoeff0(p,x,r); |
---|
478 | } |
---|
479 | for (i=rVar(r); i!=0; i--) |
---|
480 | { |
---|
481 | p_MultExp(p,i, exp,r); |
---|
482 | } |
---|
483 | p_Setm(p,r); |
---|
484 | return p; |
---|
485 | } |
---|
486 | static void buildTermAndAdd(int /*n*/,number* /*facult*/,poly* /*f_terms*/,int* exp,int f_len,kBucket_pt /*erg_bucket*/,ring r, number coef, poly & zw, poly /*tmp*/, poly** term_pot){ |
---|
487 | |
---|
488 | int i; |
---|
489 | // poly term=p_Init(r); |
---|
490 | |
---|
491 | // number denom=n_Init(1,r); |
---|
492 | // for(i=0;i<f_len;i++){ |
---|
493 | // if(exp[i]!=0){ |
---|
494 | // number trash=denom; |
---|
495 | // denom=n_Mult(denom,facult[exp[i]],r); |
---|
496 | // n_Delete(&trash,r); |
---|
497 | // } |
---|
498 | |
---|
499 | // } |
---|
500 | // number coef=n_IntDiv(facult[n],denom,r); //right function here? |
---|
501 | // n_Delete(&denom,r); |
---|
502 | // poly erg=p_NSet(coef,r); |
---|
503 | poly erg=p_Init(r,lm_bin); |
---|
504 | p_SetCoeff0(erg, coef,r); |
---|
505 | //p_NSet(n_Copy(coef,r),r); |
---|
506 | for(i=0;i<f_len;i++){ |
---|
507 | if(exp[i]!=0){ |
---|
508 | ///poly term=p_Copy(f_terms[i],r); |
---|
509 | poly term=term_pot[i][exp[i]]; |
---|
510 | //tmp; |
---|
511 | //p_ExpVectorCopy(term,f_terms[i],r); |
---|
512 | //p_SetCoeff(term, n_Copy(p_GetCoeff(f_terms[i],r),r),r); |
---|
513 | |
---|
514 | //term->next=NULL; |
---|
515 | |
---|
516 | //p_MonPowerMB(term, exp[i],r); |
---|
517 | p_MonMultMB(erg,term,r); |
---|
518 | //p_Delete(&term,r); |
---|
519 | } |
---|
520 | |
---|
521 | } |
---|
522 | zw=erg; |
---|
523 | } |
---|
524 | |
---|
525 | |
---|
526 | |
---|
527 | static void MC_iterate(poly f, int n, ring r, int f_len,number* facult, int* exp,poly* f_terms,kBucket_pt erg_bucket,int pos,int sum, number coef, poly & zw, poly tmp, poly** term_pot){ |
---|
528 | int i; |
---|
529 | |
---|
530 | if (pos<f_len-1) |
---|
531 | { |
---|
532 | poly zw_l=NULL; |
---|
533 | number new_coef; |
---|
534 | for(i=0;i<=n-sum;i++) |
---|
535 | { |
---|
536 | exp[pos]=i; |
---|
537 | if(i==0) |
---|
538 | { |
---|
539 | new_coef=n_Copy(coef,r->cf); |
---|
540 | } |
---|
541 | else |
---|
542 | { |
---|
543 | number old=new_coef; |
---|
544 | number old_rest=n_Init(n-sum-(i-1),r->cf); |
---|
545 | new_coef=n_Mult(new_coef,old_rest,r->cf); |
---|
546 | n_Delete(&old_rest,r->cf); |
---|
547 | n_Delete(&old,r->cf); |
---|
548 | number i_number=n_Init(i,r->cf); |
---|
549 | old=new_coef; |
---|
550 | new_coef=n_IntDiv(new_coef,i_number,r->cf); |
---|
551 | n_Delete(&old,r->cf); |
---|
552 | n_Delete(&i_number,r->cf); |
---|
553 | } |
---|
554 | //new_coef is |
---|
555 | //(n ) |
---|
556 | //(exp[0]..exp[pos] 0 0 0 rest) |
---|
557 | poly zw_real=NULL; |
---|
558 | MC_iterate(f, n, r, f_len,facult, exp,f_terms,erg_bucket,pos+1,sum+i,new_coef,zw_real,tmp,term_pot); |
---|
559 | if (pos==f_len-2) |
---|
560 | { |
---|
561 | //get first small polys |
---|
562 | |
---|
563 | zw_real->next=zw_l; |
---|
564 | zw_l=zw_real; |
---|
565 | } |
---|
566 | //n_Delete(& new_coef,r->cf); |
---|
567 | } |
---|
568 | n_Delete(&new_coef,r->cf); |
---|
569 | if (pos==f_len-2) |
---|
570 | { |
---|
571 | int len=n-sum+1; |
---|
572 | kBucket_Add_q(erg_bucket,zw_l,&len); |
---|
573 | } |
---|
574 | return; |
---|
575 | } |
---|
576 | if(pos==f_len-1) |
---|
577 | { |
---|
578 | i=n-sum; |
---|
579 | exp[pos]=i; |
---|
580 | number new_coef=n_Copy(coef,r->cf);//n_IntDiv(coef,facult[i],r); //really consumed??????? |
---|
581 | buildTermAndAdd(n,facult,f_terms,exp,f_len,erg_bucket,r, new_coef,zw, tmp,term_pot); |
---|
582 | // n_Delete(& new_coef,r); |
---|
583 | } |
---|
584 | assume(pos<=f_len-1); |
---|
585 | } |
---|
586 | poly pFastPowerMC(poly f, int n, ring r) |
---|
587 | { |
---|
588 | //only char=0 |
---|
589 | |
---|
590 | if(rChar(r)!=0) |
---|
591 | Werror("Char not 0, pFastPowerMC not implemented for this case"); |
---|
592 | if (n<=1) |
---|
593 | Werror("not implemented for so small n, recursion fails");//should be length(f) |
---|
594 | if (pLength(f)<=1) |
---|
595 | Werror("not implemented for so small lenght of f, recursion fails"); |
---|
596 | // number null_number=n_Init(0,r); |
---|
597 | number* facult=(number*) omAlloc((n+1)*sizeof(number)); |
---|
598 | facult[0]=n_Init(1,r->cf); |
---|
599 | int i; |
---|
600 | for(i=1;i<=n;i++) |
---|
601 | { |
---|
602 | number this_n=n_Init(i,r->cf); |
---|
603 | facult[i]=n_Mult(this_n,facult[i-1],r->cf); |
---|
604 | n_Delete(&this_n,r->cf); |
---|
605 | } |
---|
606 | |
---|
607 | lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long)); |
---|
608 | |
---|
609 | kBucket_pt erg_bucket= kBucketCreate(currRing); |
---|
610 | kBucketInit(erg_bucket,NULL,0); |
---|
611 | const int f_len=pLength(f); |
---|
612 | int* exp=(int*)omAlloc(f_len*sizeof(int)); |
---|
613 | //poly f_terms[f_len]; |
---|
614 | poly* f_terms=(poly*)omAlloc(f_len*sizeof(poly)); |
---|
615 | poly** term_potences=(poly**) omAlloc(f_len*sizeof(poly*)); |
---|
616 | |
---|
617 | poly f_iter=f; |
---|
618 | for(i=0;i<f_len;i++) |
---|
619 | { |
---|
620 | f_terms[i]=f_iter; |
---|
621 | f_iter=pNext(f_iter); |
---|
622 | } |
---|
623 | for(i=0;i<f_len;i++) |
---|
624 | { |
---|
625 | term_potences[i]=(poly*)omAlloc((n+1)*sizeof(poly)); |
---|
626 | term_potences[i][0]=p_ISet(1,r); |
---|
627 | int j; |
---|
628 | for(j=1;j<=n;j++){ |
---|
629 | term_potences[i][j]=p_MonMultCMB(f_terms[i],term_potences[i][j-1],r); |
---|
630 | } |
---|
631 | } |
---|
632 | assume(f_iter==NULL); |
---|
633 | poly zw=NULL; |
---|
634 | poly tmp=p_Init(r); |
---|
635 | number one=n_Init(1,r->cf); |
---|
636 | MC_iterate(f,n,r,f_len,&facult[0], &exp[0], &f_terms[0],erg_bucket,0,0,one/*facult[n]*/,zw,tmp, term_potences); |
---|
637 | |
---|
638 | |
---|
639 | n_Delete(&one,r->cf); |
---|
640 | |
---|
641 | |
---|
642 | |
---|
643 | //free res |
---|
644 | |
---|
645 | //free facult |
---|
646 | for(i=0;i<=n;i++) |
---|
647 | { |
---|
648 | n_Delete(&facult[i],r->cf); |
---|
649 | } |
---|
650 | int i2; |
---|
651 | for (i=0;i<f_len;i++) |
---|
652 | { |
---|
653 | for(i2=0;i2<=n;i2++) |
---|
654 | { |
---|
655 | p_Delete(&term_potences[i][i2],r); |
---|
656 | } |
---|
657 | omfree(term_potences[i]); |
---|
658 | |
---|
659 | } |
---|
660 | omfree(term_potences); |
---|
661 | p_Delete(&tmp,r); |
---|
662 | omfree(exp); |
---|
663 | omfree(facult); |
---|
664 | omfree(f_terms); |
---|
665 | int len=0; |
---|
666 | poly erg; |
---|
667 | kBucketClear(erg_bucket,&erg, &len); |
---|
668 | kBucketDestroy(&erg_bucket); |
---|
669 | omUnGetSpecBin(&lm_bin); |
---|
670 | return erg; |
---|
671 | } |
---|