1 | #include "fast_mult.h" |
---|
2 | #include "kbuckets.h" |
---|
3 | #include "febase.h" |
---|
4 | typedef poly fastmultrec(poly f, poly g, ring r); |
---|
5 | static const int pass_option=1; |
---|
6 | static int mults=0; |
---|
7 | int Mults(){ |
---|
8 | return mults; |
---|
9 | } |
---|
10 | static void degsplit(poly p,int n,poly &p1,poly&p2, int vn, ring r){ |
---|
11 | poly erg1_i, erg2_i; |
---|
12 | erg1_i=NULL; |
---|
13 | erg2_i=NULL; |
---|
14 | while(p){ |
---|
15 | if(p_GetExp(p,vn,r)>=n){ |
---|
16 | if (p1==NULL){ |
---|
17 | p1=p; |
---|
18 | } else{ |
---|
19 | pNext(erg1_i)=p; |
---|
20 | } |
---|
21 | erg1_i=p; |
---|
22 | } else{ |
---|
23 | if (p2==NULL){ |
---|
24 | p2=p; |
---|
25 | } else{ |
---|
26 | pNext(erg2_i)=p; |
---|
27 | } |
---|
28 | erg2_i=p; |
---|
29 | } |
---|
30 | p=pNext(p); |
---|
31 | } |
---|
32 | if(erg2_i){ |
---|
33 | pNext(erg2_i)=NULL; |
---|
34 | } |
---|
35 | if (erg1_i){ |
---|
36 | pNext(erg1_i)=NULL; |
---|
37 | } |
---|
38 | |
---|
39 | } |
---|
40 | static void div_by_x_power_n(poly p, int n, int vn, ring r){ |
---|
41 | while(p){ |
---|
42 | assume(p_GetExp(p,vn,r)>=n); |
---|
43 | int e=p_GetExp(p,vn,r); |
---|
44 | p_SetExp(p,vn,e-n,r); |
---|
45 | p=pNext(p); |
---|
46 | } |
---|
47 | } |
---|
48 | |
---|
49 | static poly do_unifastmult(poly f,int df,poly g,int dg, int vn, fastmultrec rec, ring r){ |
---|
50 | int n=1; |
---|
51 | if ((f==NULL)||(g==NULL)) return NULL; |
---|
52 | //int df=pGetExp(f,vn);//pFDeg(f); |
---|
53 | // int dg=pGetExp(g,vn);//pFDeg(g); |
---|
54 | |
---|
55 | int dm; |
---|
56 | if(df>dg){ |
---|
57 | dm=df; |
---|
58 | }else{ |
---|
59 | dm=dg; |
---|
60 | } |
---|
61 | while(n<=dm) |
---|
62 | { |
---|
63 | n*=2; |
---|
64 | } |
---|
65 | if(n==1){ |
---|
66 | return(pp_Mult_qq(f,g,r)); |
---|
67 | } |
---|
68 | |
---|
69 | int pot=n/2; |
---|
70 | assume(pot*2==n); |
---|
71 | |
---|
72 | |
---|
73 | //splitting |
---|
74 | poly f1=NULL; |
---|
75 | poly f0=NULL;//f-(x^(pot)*F1); |
---|
76 | degsplit(p_Copy(f,r),pot,f1,f0,vn,r); |
---|
77 | div_by_x_power_n(f1,pot,vn,r); |
---|
78 | |
---|
79 | poly g1=NULL; |
---|
80 | poly g0=NULL; |
---|
81 | degsplit(p_Copy(g,r),pot,g1,g0,vn,r); |
---|
82 | div_by_x_power_n(g1,pot,vn,r); |
---|
83 | |
---|
84 | //p00, p11 |
---|
85 | poly p00=rec(f0,g0,r);//unifastmult(f0,g0); |
---|
86 | poly p11=rec(f1,g1,r); |
---|
87 | |
---|
88 | //construct erg, factor |
---|
89 | poly erg=NULL; |
---|
90 | poly factor=p_ISet(1,r); |
---|
91 | |
---|
92 | p_SetExp(factor,vn,n,r); |
---|
93 | erg=pp_Mult_mm(p11,factor,r); |
---|
94 | erg=p_Add_q(erg,p_Copy(p00,r),r); |
---|
95 | |
---|
96 | |
---|
97 | |
---|
98 | |
---|
99 | |
---|
100 | if((f1!=NULL) &&(f0!=NULL) &&(g0!=NULL) && (g1!=NULL)){ |
---|
101 | //if(true){ |
---|
102 | //eat up f0,f1,g0,g1 |
---|
103 | poly s1=p_Add_q(f0,f1,r); |
---|
104 | poly s2=p_Add_q(g0,g1,r); |
---|
105 | poly pbig=rec(s1,s2,r); |
---|
106 | p_Delete(&s1,r); |
---|
107 | p_Delete(&s2,r); |
---|
108 | |
---|
109 | |
---|
110 | //eat up pbig |
---|
111 | poly sum=pbig; |
---|
112 | p_SetExp(factor,vn,pot,r); |
---|
113 | |
---|
114 | //eat up p00 |
---|
115 | sum=p_Add_q(sum,p_Neg(p00,r),r); |
---|
116 | |
---|
117 | //eat up p11 |
---|
118 | sum=p_Add_q(sum,p_Neg(p11,r),r); |
---|
119 | |
---|
120 | |
---|
121 | sum=p_Mult_mm(sum,factor,r); |
---|
122 | |
---|
123 | |
---|
124 | //eat up sum |
---|
125 | erg=p_Add_q(sum,erg,r); |
---|
126 | } else { |
---|
127 | //eat up f0,f1,g0,g1 |
---|
128 | poly s1=rec(f0,g1,r); |
---|
129 | poly s2=rec(g0,f1,r); |
---|
130 | p_SetExp(factor,vn,pot,r); |
---|
131 | poly h=p_Mult_mm(((s1!=NULL)?s1:s2),factor,r); |
---|
132 | p_Delete(&f1,r); |
---|
133 | p_Delete(&f0,r); |
---|
134 | p_Delete(&g0,r); |
---|
135 | p_Delete(&g1,r); |
---|
136 | p_Delete(&p00,r); |
---|
137 | p_Delete(&p11,r); |
---|
138 | erg=p_Add_q(erg,h,r); |
---|
139 | } |
---|
140 | |
---|
141 | |
---|
142 | p_Delete(&factor,r); |
---|
143 | |
---|
144 | |
---|
145 | |
---|
146 | return(erg); |
---|
147 | } |
---|
148 | |
---|
149 | // poly do_unifastmult_buckets(poly f,poly g){ |
---|
150 | |
---|
151 | |
---|
152 | |
---|
153 | |
---|
154 | // int n=1; |
---|
155 | // if ((f==NULL)||(g==NULL)) return NULL; |
---|
156 | // int df=pGetExp(f,1);//pFDeg(f); |
---|
157 | // int dg=pGetExp(g,1);//pFDeg(g); |
---|
158 | |
---|
159 | // int dm; |
---|
160 | // if(df>dg){ |
---|
161 | // dm=df; |
---|
162 | // }else{ |
---|
163 | // dm=dg; |
---|
164 | // } |
---|
165 | // while(n<=dm) |
---|
166 | // { |
---|
167 | // n*=2; |
---|
168 | // } |
---|
169 | // int pseudo_len=0; |
---|
170 | // if(n==1){ |
---|
171 | // return ppMult_qq(f,g); |
---|
172 | |
---|
173 | // } |
---|
174 | // kBucket_pt erg_bucket= kBucketCreate(currRing); |
---|
175 | // kBucketInit(erg_bucket,NULL,0 /*pLength(P.p)*/); |
---|
176 | |
---|
177 | // int pot=n/2; |
---|
178 | // assume(pot*2==n); |
---|
179 | |
---|
180 | |
---|
181 | // //splitting |
---|
182 | // poly f1=NULL; |
---|
183 | // poly f0=NULL;//f-(x^(pot)*F1); |
---|
184 | // degsplit(pCopy(f),pot,f1,f0); |
---|
185 | // div_by_x_power_n(f1,pot); |
---|
186 | // poly g1=NULL; |
---|
187 | // poly g0=NULL; |
---|
188 | // degsplit(pCopy(g),pot,g1,g0); |
---|
189 | // div_by_x_power_n(g1,pot); |
---|
190 | |
---|
191 | // //p00 |
---|
192 | // //p11 |
---|
193 | // poly p00=unifastmult(f0,g0); |
---|
194 | // poly p11=unifastmult(f1,g1); |
---|
195 | |
---|
196 | |
---|
197 | |
---|
198 | |
---|
199 | // //eat up f0,f1,g0,g1 |
---|
200 | // poly pbig=unifastmult(pAdd(f0,f1),pAdd(g0,g1)); |
---|
201 | // poly factor=pOne();//pCopy(erg_mult); |
---|
202 | // pSetExp(factor,1,n); |
---|
203 | // pseudo_len=0; |
---|
204 | // kBucket_Add_q(erg_bucket,ppMult_mm(p11,factor),&pseudo_len); |
---|
205 | // pseudo_len=0; |
---|
206 | // kBucket_Add_q(erg_bucket,pCopy(p00),&pseudo_len); |
---|
207 | // pSetExp(factor,1,pot); |
---|
208 | |
---|
209 | // //eat up pbig |
---|
210 | // pseudo_len=0; |
---|
211 | // kBucket_Add_q(erg_bucket,pMult_mm(pbig,factor),&pseudo_len); |
---|
212 | // pseudo_len=0; |
---|
213 | // //eat up p00 |
---|
214 | // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p00),factor),&pseudo_len); |
---|
215 | // pseudo_len=0; |
---|
216 | // //eat up p11 |
---|
217 | // kBucket_Add_q(erg_bucket,pMult_mm(pNeg(p11),factor),&pseudo_len); |
---|
218 | |
---|
219 | |
---|
220 | // pseudo_len=0; |
---|
221 | |
---|
222 | |
---|
223 | // pDelete(&factor); |
---|
224 | |
---|
225 | // int len=0; |
---|
226 | // poly erg=NULL; |
---|
227 | // kBucketClear(erg_bucket,&erg,&len); |
---|
228 | // kBucketDestroy(&erg_bucket); |
---|
229 | |
---|
230 | // return erg; |
---|
231 | // } |
---|
232 | |
---|
233 | static inline int max(int a, int b){ |
---|
234 | return (a>b)? a:b; |
---|
235 | } |
---|
236 | static inline int min(int a, int b){ |
---|
237 | return (a>b)? b:a; |
---|
238 | } |
---|
239 | poly unifastmult(poly f,poly g, ring r){ |
---|
240 | int vn=1; |
---|
241 | if((f==NULL)||(g==NULL)) return NULL; |
---|
242 | int df=p_GetExp(f,vn,r); |
---|
243 | int dg=p_GetExp(g,vn,r); |
---|
244 | if ((df==0)||(dg==0)) |
---|
245 | return pp_Mult_qq(f,g,r); |
---|
246 | if (df*dg<100) |
---|
247 | return pp_Mult_qq(f,g,r); |
---|
248 | // if (df*dg>10000) |
---|
249 | // return |
---|
250 | // do_unifastmult_buckets(f,g); |
---|
251 | //else |
---|
252 | return do_unifastmult(f,df,g,dg,vn,unifastmult,r); |
---|
253 | |
---|
254 | } |
---|
255 | |
---|
256 | poly multifastmult(poly f, poly g, ring r){ |
---|
257 | mults++; |
---|
258 | if((f==NULL)||(g==NULL)) return NULL; |
---|
259 | if (pLength(f)*pLength(g)<100) |
---|
260 | return pp_Mult_qq(f,g,r); |
---|
261 | //find vn |
---|
262 | //determine df,dg simultaneously |
---|
263 | int i; |
---|
264 | int can_i=-1; |
---|
265 | int can_df=0; |
---|
266 | int can_dg=0; |
---|
267 | int can_crit=0; |
---|
268 | for(i=1;i<=rVar(r);i++){ |
---|
269 | poly p; |
---|
270 | int df=0; |
---|
271 | int dg=0; |
---|
272 | //max min max Strategie |
---|
273 | p=f; |
---|
274 | while(p){ |
---|
275 | df=max(df,p_GetExp(p,i,r)); |
---|
276 | p=pNext(p); |
---|
277 | } |
---|
278 | if(df>can_crit){ |
---|
279 | p=g; |
---|
280 | while(p){ |
---|
281 | dg=max(dg,p_GetExp(p,i,r)); |
---|
282 | p=pNext(p); |
---|
283 | } |
---|
284 | int crit=min(df,dg); |
---|
285 | if (crit>can_crit){ |
---|
286 | can_crit=crit; |
---|
287 | can_i=i; |
---|
288 | can_df=df; |
---|
289 | can_dg=dg; |
---|
290 | } |
---|
291 | } |
---|
292 | } |
---|
293 | if(can_crit==0) |
---|
294 | return pp_Mult_qq(f,g,r); |
---|
295 | else |
---|
296 | { |
---|
297 | poly erg=do_unifastmult(f,can_df,g,can_dg,can_i,multifastmult,r); |
---|
298 | p_Normalize(erg,r); |
---|
299 | return(erg); |
---|
300 | } |
---|
301 | } |
---|
302 | poly pFastPower(poly f, int n, ring r){ |
---|
303 | if (n==1) return f; |
---|
304 | if (n==0) return p_ISet(1,r); |
---|
305 | assume(n>=0); |
---|
306 | int i_max=1; |
---|
307 | int pot_max=0; |
---|
308 | while(i_max*2<=n){ |
---|
309 | i_max*=2; |
---|
310 | pot_max++; |
---|
311 | } |
---|
312 | int field_size=pot_max+1; |
---|
313 | int* int_pot_array=(int*) omalloc(field_size*sizeof(int)); |
---|
314 | poly* pot_array=(poly*) omalloc(field_size*sizeof(poly)); |
---|
315 | int i; |
---|
316 | int pot=1; |
---|
317 | //initializing int_pot |
---|
318 | for(i=0;i<field_size;i++){ |
---|
319 | int_pot_array[i]=pot; |
---|
320 | pot*=2; |
---|
321 | } |
---|
322 | //calculating pot_array |
---|
323 | pot_array[0]=f; //do not delete it |
---|
324 | for(i=1;i<field_size;i++){ |
---|
325 | poly p=pot_array[i-1]; |
---|
326 | if(rVar(r)==1) |
---|
327 | pot_array[i]=multifastmult(p,p,r); |
---|
328 | else |
---|
329 | pot_array[i]=pp_Mult_qq(p,p,r); |
---|
330 | } |
---|
331 | |
---|
332 | |
---|
333 | |
---|
334 | int work_n=n; |
---|
335 | assume(work_n>=int_pot_array[field_size-1]); |
---|
336 | poly erg=p_ISet(1,r); |
---|
337 | |
---|
338 | |
---|
339 | //forward maybe faster, later |
---|
340 | // for(i=field_size-1;i>=0;i--){ |
---|
341 | |
---|
342 | // assume(work_n<2*int_pot_array[i]); |
---|
343 | // if(int_pot_array[i]<=work_n){ |
---|
344 | // work_n-=int_pot_array[i]; |
---|
345 | // poly prod=multifastmult(erg,pot_array[i],r); |
---|
346 | // pDelete(&erg); |
---|
347 | // erg=prod; |
---|
348 | // } |
---|
349 | |
---|
350 | // if(i!=0) pDelete(&pot_array[i]); |
---|
351 | // } |
---|
352 | |
---|
353 | |
---|
354 | for(i=field_size-1;i>=0;i--){ |
---|
355 | |
---|
356 | assume(work_n<2*int_pot_array[i]); |
---|
357 | if(int_pot_array[i]<=work_n){ |
---|
358 | work_n-=int_pot_array[i]; |
---|
359 | int_pot_array[i]=1; |
---|
360 | } |
---|
361 | else int_pot_array[i]=0; |
---|
362 | |
---|
363 | } |
---|
364 | for(i=0;i<field_size;i++){ |
---|
365 | if(int_pot_array[i]==1){ |
---|
366 | poly prod; |
---|
367 | if(rVar(r)==1) |
---|
368 | prod=multifastmult(erg,pot_array[i],r); |
---|
369 | else |
---|
370 | prod=pp_Mult_qq(erg,pot_array[i],r); |
---|
371 | pDelete(&erg); |
---|
372 | erg=prod; |
---|
373 | } |
---|
374 | if(i!=0) pDelete(&pot_array[i]); |
---|
375 | } |
---|
376 | //free res |
---|
377 | omfree(pot_array); |
---|
378 | omfree(int_pot_array); |
---|
379 | return erg; |
---|
380 | } |
---|
381 | |
---|
382 | static poly p_MonPowerMB(poly p, int exp, ring r) |
---|
383 | { |
---|
384 | int i; |
---|
385 | |
---|
386 | if(!n_IsOne(p_GetCoeff(p,r),r)) |
---|
387 | { |
---|
388 | number x, y; |
---|
389 | y = p_GetCoeff(p,r); |
---|
390 | n_Power(y,exp,&x,r); |
---|
391 | n_Delete(&y,r); |
---|
392 | p_SetCoeff0(p,x,r); |
---|
393 | } |
---|
394 | for (i=rVar(r); i!=0; i--) |
---|
395 | { |
---|
396 | p_MultExp(p,i, exp,r); |
---|
397 | } |
---|
398 | p_Setm(p,r); |
---|
399 | return p; |
---|
400 | } |
---|
401 | static void buildTermAndAdd(int n,number* facult,poly* f_terms,int* exp,int f_len,kBucket_pt erg_bucket,ring r){ |
---|
402 | number denom=n_Init(1,r); |
---|
403 | int i; |
---|
404 | poly term=p_Init(r); |
---|
405 | for(i=0;i<f_len;i++){ |
---|
406 | if(exp[i]!=0){ |
---|
407 | number trash=denom; |
---|
408 | denom=n_Mult(denom,facult[exp[i]],r); |
---|
409 | n_Delete(&trash,r); |
---|
410 | } |
---|
411 | |
---|
412 | } |
---|
413 | number coef=n_IntDiv(facult[n],denom,r); //right function here? |
---|
414 | n_Delete(&denom,r); |
---|
415 | poly erg=p_NSet(coef,r); |
---|
416 | for(i=0;i<f_len;i++){ |
---|
417 | if(exp[i]!=0){ |
---|
418 | poly term=p_Copy(f_terms[i],r); |
---|
419 | term->next=NULL; |
---|
420 | p_MonPowerMB(term, exp[i],r); |
---|
421 | erg=p_Mult_mm(erg,term,r); |
---|
422 | p_Delete(&term,r); |
---|
423 | } |
---|
424 | |
---|
425 | } |
---|
426 | int pseudo_len=0; |
---|
427 | kBucket_Add_q(erg_bucket,erg,&pseudo_len); |
---|
428 | } |
---|
429 | |
---|
430 | |
---|
431 | |
---|
432 | 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){ |
---|
433 | int i; |
---|
434 | if (pos<f_len-1){ |
---|
435 | for(i=0;i<=n-sum;i++){ |
---|
436 | exp[pos]=i; |
---|
437 | MC_iterate(f, n, r, f_len,facult, exp,f_terms,erg_bucket,pos+1,sum+i); |
---|
438 | } |
---|
439 | return; |
---|
440 | } |
---|
441 | if(pos==f_len-1){ |
---|
442 | i=n-sum; |
---|
443 | exp[pos]=i; |
---|
444 | buildTermAndAdd(n,facult,f_terms,exp,f_len,erg_bucket,r); |
---|
445 | } |
---|
446 | assume(pos<=f_len-1); |
---|
447 | } |
---|
448 | poly pFastPowerMC(poly f, int n, ring r){ |
---|
449 | //only char=0 |
---|
450 | if(rChar(r)!=0) |
---|
451 | Werror("Char not 0, pFastPowerMC not implemented for this case"); |
---|
452 | |
---|
453 | // number null_number=n_Init(0,r); |
---|
454 | number* facult=(number*) omalloc((n+1)*sizeof(number)); |
---|
455 | facult[0]=n_Init(1,r); |
---|
456 | int i; |
---|
457 | for(i=1;i<=n;i++){ |
---|
458 | number this_n=n_Init(i,r); |
---|
459 | facult[i]=n_Mult(this_n,facult[i-1],r); |
---|
460 | n_Delete(&this_n,r); |
---|
461 | } |
---|
462 | kBucket_pt erg_bucket= kBucketCreate(currRing); |
---|
463 | kBucketInit(erg_bucket,NULL,0); |
---|
464 | const int f_len=pLength(f); |
---|
465 | int* exp=(int*)omalloc(f_len*sizeof(int)); |
---|
466 | //poly f_terms[f_len]; |
---|
467 | poly* f_terms=(poly*)omalloc(f_len*sizeof(poly)); |
---|
468 | poly f_iter=f; |
---|
469 | for(i=0;i<f_len;i++){ |
---|
470 | f_terms[i]=f_iter; |
---|
471 | f_iter=pNext(f_iter); |
---|
472 | } |
---|
473 | assume(f_iter==NULL); |
---|
474 | MC_iterate(f,n,r,f_len,&facult[0], &exp[0], &f_terms[0],erg_bucket,0,0); |
---|
475 | |
---|
476 | |
---|
477 | |
---|
478 | |
---|
479 | |
---|
480 | |
---|
481 | //free res |
---|
482 | |
---|
483 | //free facult |
---|
484 | for(i=0;i<=n;i++){ |
---|
485 | nDelete(&facult[0]); |
---|
486 | } |
---|
487 | omfree(exp); |
---|
488 | omfree(facult); |
---|
489 | omfree(f_terms); |
---|
490 | int len=0; |
---|
491 | poly erg; |
---|
492 | kBucketClear(erg_bucket,&erg, &len); |
---|
493 | return erg; |
---|
494 | } |
---|