My Project
Loading...
Searching...
No Matches
Functions
fast_mult.h File Reference
#include "kernel/mod2.h"
#include "kernel/polys.h"

Go to the source code of this file.

Functions

poly unifastmult (poly f, poly g, ring r)
 
poly multifastmult (poly f, poly g, ring r)
 
int Mults ()
 
poly pFastPower (poly f, int n, ring r)
 
poly pFastPowerMC (poly f, int n, ring r)
 

Function Documentation

◆ multifastmult()

poly multifastmult ( poly  f,
poly  g,
ring  r 
)

Definition at line 290 of file fast_mult.cc.

291{
292 mults++;
293 if((f==NULL)||(g==NULL)) return NULL;
294 if (pLength(f)*pLength(g)<100)
295 return pp_Mult_qq(f,g,r);
296 //find vn
297 //determine df,dg simultaneously
298 int i;
299 int can_i=-1;
300 int can_df=0;
301 int can_dg=0;
302 int can_crit=0;
303 for(i=1;i<=rVar(r);i++)
304 {
305 poly p;
306 int df=0;
307 int dg=0;
308 //max min max Strategie
309 p=f;
310 while(p)
311 {
312 df=max(df,p_GetExp(p,i,r));
313 p=pNext(p);
314 }
315 if(df>can_crit)
316 {
317 p=g;
318 while(p)
319 {
320 dg=max(dg,p_GetExp(p,i,r));
321 p=pNext(p);
322 }
323 int crit=min(df,dg);
324 if (crit>can_crit)
325 {
326 can_crit=crit;
327 can_i=i;
328 can_df=df;
329 can_dg=dg;
330 }
331 }
332 }
333 if(can_crit==0)
334 return pp_Mult_qq(f,g,r);
335 else
336 {
337 poly erg=do_unifastmult(f,can_df,g,can_dg,can_i,multifastmult,r);
338 p_Normalize(erg,r);
339 return(erg);
340 }
341}
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4078
g
Definition: cfModGcd.cc:4090
FILE * f
Definition: checklibs.c:9
static int min(int a, int b)
Definition: fast_mult.cc:268
STATIC_VAR int mults
Definition: fast_mult.cc:13
static poly do_unifastmult(poly f, int df, poly g, int dg, int vn, fastmultrec rec, ring r)
Definition: fast_mult.cc:72
static int max(int a, int b)
Definition: fast_mult.cc:264
poly multifastmult(poly f, poly g, ring r)
Definition: fast_mult.cc:290
#define pNext(p)
Definition: monomials.h:36
#define NULL
Definition: omList.c:12
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3813
static int pLength(poly a)
Definition: p_polys.h:188
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:467
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1149
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592

◆ Mults()

int Mults ( )

Definition at line 14 of file fast_mult.cc.

15{
16 return mults;
17}

◆ pFastPower()

poly pFastPower ( poly  f,
int  n,
ring  r 
)

Definition at line 342 of file fast_mult.cc.

343{
344 if (n==1) return f;
345 if (n==0) return p_ISet(1,r);
346 assume(n>=0);
347 int i_max=1;
348 int pot_max=0;
349 while(i_max*2<=n)
350 {
351 i_max*=2;
352 pot_max++;
353 }
354 int field_size=pot_max+1;
355 int* int_pot_array=(int*) omAlloc(field_size*sizeof(int));
356 poly* pot_array=(poly*) omAlloc(field_size*sizeof(poly));
357 int i;
358 int pot=1;
359 //initializing int_pot
360 for(i=0;i<field_size;i++)
361 {
362 int_pot_array[i]=pot;
363 pot*=2;
364 }
365 //calculating pot_array
366 pot_array[0]=f; //do not delete it
367 for(i=1;i<field_size;i++)
368 {
369 poly p=pot_array[i-1];
370 if(rVar(r)==1)
371 pot_array[i]=multifastmult(p,p,r);
372 else
373 pot_array[i]=pp_Mult_qq(p,p,r);
374 }
375
376
377
378 int work_n=n;
379 assume(work_n>=int_pot_array[field_size-1]);
380 poly erg=p_ISet(1,r);
381
382
383 //forward maybe faster, later
384 // for(i=field_size-1;i>=0;i--){
385
386// assume(work_n<2*int_pot_array[i]);
387// if(int_pot_array[i]<=work_n){
388// work_n-=int_pot_array[i];
389// poly prod=multifastmult(erg,pot_array[i],r);
390// pDelete(&erg);
391// erg=prod;
392// }
393
394// if(i!=0) pDelete(&pot_array[i]);
395// }
396
397
398 for(i=field_size-1;i>=0;i--)
399 {
400
401 assume(work_n<2*int_pot_array[i]);
402 if(int_pot_array[i]<=work_n)
403 {
404 work_n-=int_pot_array[i];
405 int_pot_array[i]=1;
406 }
407 else int_pot_array[i]=0;
408
409 }
410 for(i=0;i<field_size;i++)
411 {
412 if(int_pot_array[i]==1)
413 {
414 poly prod;
415 if(rVar(r)==1)
416 prod=multifastmult(erg,pot_array[i],r);
417 else
418 prod=pp_Mult_qq(erg,pot_array[i],r);
419 pDelete(&erg);
420 erg=prod;
421 }
422 if(i!=0) pDelete(&pot_array[i]);
423 }
424 //free res
425 omfree(pot_array);
426 omfree(int_pot_array);
427 return erg;
428}
fq_nmod_poly_t prod
Definition: facHensel.cc:100
#define assume(x)
Definition: mod2.h:389
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omAlloc(size)
Definition: omAllocDecl.h:210
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1297
#define pDelete(p_ptr)
Definition: polys.h:186

◆ pFastPowerMC()

poly pFastPowerMC ( poly  f,
int  n,
ring  r 
)

Definition at line 588 of file fast_mult.cc.

589{
590 //only char=0
591
592 if(rChar(r)!=0)
593 WerrorS("Char not 0, pFastPowerMC not implemented for this case");
594 if (n<=1)
595 WerrorS("not implemented for so small n, recursion fails");//should be length(f)
596 if (pLength(f)<=1)
597 WerrorS("not implemented for so small length of f, recursion fails");
598 // number null_number=n_Init(0,r);
599 number* facult=(number*) omAlloc((n+1)*sizeof(number));
600 facult[0]=n_Init(1,r->cf);
601 int i;
602 for(i=1;i<=n;i++)
603 {
604 number this_n=n_Init(i,r->cf);
605 facult[i]=n_Mult(this_n,facult[i-1],r->cf);
606 n_Delete(&this_n,r->cf);
607 }
608
609 lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long));
610
611 kBucket_pt erg_bucket= kBucketCreate(currRing);
612 kBucketInit(erg_bucket,NULL,0);
613 const int f_len=pLength(f);
614 int* exp=(int*)omAlloc(f_len*sizeof(int));
615 //poly f_terms[f_len];
616 poly* f_terms=(poly*)omAlloc(f_len*sizeof(poly));
617 poly** term_potences=(poly**) omAlloc(f_len*sizeof(poly*));
618
619 poly f_iter=f;
620 for(i=0;i<f_len;i++)
621 {
622 f_terms[i]=f_iter;
623 f_iter=pNext(f_iter);
624 }
625 for(i=0;i<f_len;i++)
626 {
627 term_potences[i]=(poly*)omAlloc((n+1)*sizeof(poly));
628 term_potences[i][0]=p_ISet(1,r);
629 int j;
630 for(j=1;j<=n;j++){
631 term_potences[i][j]=p_MonMultCMB(f_terms[i],term_potences[i][j-1],r);
632 }
633 }
634 assume(f_iter==NULL);
635 poly zw=NULL;
636 poly tmp=p_Init(r);
637 number one=n_Init(1,r->cf);
638 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);
639
640
641 n_Delete(&one,r->cf);
642
643
644
645 //free res
646
647 //free facult
648 for(i=0;i<=n;i++)
649 {
650 n_Delete(&facult[i],r->cf);
651 }
652 int i2;
653 for (i=0;i<f_len;i++)
654 {
655 for(i2=0;i2<=n;i2++)
656 {
657 p_Delete(&term_potences[i][i2],r);
658 }
659 omfree(term_potences[i]);
660
661 }
662 omfree(term_potences);
663 p_Delete(&tmp,r);
664 omfree(exp);
665 omfree(facult);
666 omfree(f_terms);
667 int len=0;
668 poly erg;
669 kBucketClear(erg_bucket,&erg, &len);
670 kBucketDestroy(&erg_bucket);
672 return erg;
673}
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:633
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:535
int j
Definition: facHensel.cc:110
STATIC_VAR omBin lm_bin
Definition: fast_mult.cc:429
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)
Definition: fast_mult.cc:528
static poly p_MonMultCMB(poly p, poly q, ring r)
Definition: fast_mult.cc:455
void WerrorS(const char *s)
Definition: feFopen.cc:24
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
#define POLYSIZE
Definition: monomials.h:233
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
#define omGetSpecBin(size)
Definition: omBin.h:11
#define omUnGetSpecBin(bin_ptr)
Definition: omBin.h:14
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1318
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
int rChar(ring r)
Definition: ring.cc:713

◆ unifastmult()

poly unifastmult ( poly  f,
poly  g,
ring  r 
)

Definition at line 272 of file fast_mult.cc.

273{
274 int vn=1;
275 if((f==NULL)||(g==NULL)) return NULL;
276 int df=p_GetExp(f,vn,r);
277 int dg=p_GetExp(g,vn,r);
278 if ((df==0)||(dg==0))
279 return pp_Mult_qq(f,g,r);
280 if (df*dg<100)
281 return pp_Mult_qq(f,g,r);
282 // if (df*dg>10000)
283 // return
284 // do_unifastmult_buckets(f,g);
285 //else
286 return do_unifastmult(f,df,g,dg,vn,unifastmult,r);
287
288}
poly unifastmult(poly f, poly g, ring r)
Definition: fast_mult.cc:272