My Project  UNKNOWN_GIT_VERSION
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 }
static int min(int a, int b)
Definition: fast_mult.cc:268
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
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 mults
Definition: fast_mult.cc:13
g
Definition: cfModGcd.cc:4031
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:470
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
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1088
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
static unsigned pLength(poly a)
Definition: p_polys.h:193
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3723
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:37
int p
Definition: cfModGcd.cc:4019

◆ Mults()

int Mults ( )

Definition at line 14 of file fast_mult.cc.

15 {
16  return mults;
17 }
static int mults
Definition: fast_mult.cc:13

◆ 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 }
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define assume(x)
Definition: mod2.h:390
poly multifastmult(poly f, poly g, ring r)
Definition: fast_mult.cc:290
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1088
#define omfree(addr)
Definition: omAllocDecl.h:237
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
fq_nmod_poly_t prod
Definition: facHensel.cc:95
#define pDelete(p_ptr)
Definition: polys.h:181
int p
Definition: cfModGcd.cc:4019
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1289

◆ 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 }
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:518
int j
Definition: facHensel.cc:105
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:490
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358
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:538
int rChar(ring r)
Definition: ring.cc:686
#define omUnGetSpecBin(bin_ptr)
Definition: omBin.h:14
#define POLYSIZE
Definition: monomials.h:234
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define omAlloc(size)
Definition: omAllocDecl.h:210
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:636
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
#define assume(x)
Definition: mod2.h:390
#define omfree(addr)
Definition: omAllocDecl.h:237
static poly p_MonMultCMB(poly p, poly q, ring r)
Definition: fast_mult.cc:455
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:125
static omBin lm_bin
Definition: fast_mult.cc:429
static unsigned pLength(poly a)
Definition: p_polys.h:193
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
#define omGetSpecBin(size)
Definition: omBin.h:11
#define NULL
Definition: omList.c:10
#define pNext(p)
Definition: monomials.h:37
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
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 FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1257
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition: p_polys.cc:1289

◆ 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 }
static poly do_unifastmult(poly f, int df, poly g, int dg, int vn, fastmultrec rec, ring r)
Definition: fast_mult.cc:72
g
Definition: cfModGcd.cc:4031
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:470
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1088
FILE * f
Definition: checklibs.c:9
#define NULL
Definition: omList.c:10
poly unifastmult(poly f, poly g, ring r)
Definition: fast_mult.cc:272