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

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

Definition at line 290 of file fast_mult.cc.

{
  mults++;
  if((f==NULL)||(g==NULL)) return NULL;
  if (pLength(f)*pLength(g)<100)
    return pp_Mult_qq(f,g,r);
  //find vn
  //determine df,dg simultaneously
  int i;
  int can_i=-1;
  int can_df=0;
  int can_dg=0;
  int can_crit=0;
  for(i=1;i<=rVar(r);i++)
  {
    poly p;
    int df=0;
    int dg=0;
    //max min max Strategie
    p=f;
    while(p)
    {
      df=max(df,p_GetExp(p,i,r));
      p=pNext(p);
    }
    if(df>can_crit)
    {
      p=g;
      while(p)
      {
        dg=max(dg,p_GetExp(p,i,r));
        p=pNext(p);
      }
      int crit=min(df,dg);
      if (crit>can_crit)
      {
        can_crit=crit;
        can_i=i;
        can_df=df;
        can_dg=dg;
      }
    }
  }
  if(can_crit==0)
    return pp_Mult_qq(f,g,r);
  else
    {
      poly erg=do_unifastmult(f,can_df,g,can_dg,can_i,multifastmult,r);
      p_Normalize(erg,r);
      return(erg);
    }
}

int Mults

(

)

Definition at line 14 of file fast_mult.cc.

{
  return mults;
}

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

Definition at line 342 of file fast_mult.cc.

{
  if (n==1) return f;
  if (n==0) return p_ISet(1,r);
  assume(n>=0);
  int i_max=1;
  int pot_max=0;
  while(i_max*2<=n)
  {
    i_max*=2;
    pot_max++;
  }
  int field_size=pot_max+1;
  int* int_pot_array=(int*) omAlloc(field_size*sizeof(int));
  poly* pot_array=(poly*) omAlloc(field_size*sizeof(poly));
  int i;
  int pot=1;
  //initializing int_pot
  for(i=0;i<field_size;i++)
  {
    int_pot_array[i]=pot;
    pot*=2;
  }
  //calculating pot_array
  pot_array[0]=f; //do not delete it
  for(i=1;i<field_size;i++)
  {
    poly p=pot_array[i-1];
    if(rVar(r)==1)
      pot_array[i]=multifastmult(p,p,r);
    else
      pot_array[i]=pp_Mult_qq(p,p,r);
  }



  int work_n=n;
  assume(work_n>=int_pot_array[field_size-1]);
  poly erg=p_ISet(1,r);


  //forward maybe faster, later
  // for(i=field_size-1;i>=0;i--){

//       assume(work_n<2*int_pot_array[i]);
//       if(int_pot_array[i]<=work_n){
//         work_n-=int_pot_array[i];
//         poly prod=multifastmult(erg,pot_array[i],r);
//         pDelete(&erg);
//         erg=prod;
//       }

//       if(i!=0) pDelete(&pot_array[i]);
//   }


  for(i=field_size-1;i>=0;i--)
  {

      assume(work_n<2*int_pot_array[i]);
      if(int_pot_array[i]<=work_n)
      {
        work_n-=int_pot_array[i];
        int_pot_array[i]=1;
      }
      else int_pot_array[i]=0;

  }
  for(i=0;i<field_size;i++)
  {
    if(int_pot_array[i]==1)
    {
      poly prod;
      if(rVar(r)==1)
        prod=multifastmult(erg,pot_array[i],r);
      else
        prod=pp_Mult_qq(erg,pot_array[i],r);
      pDelete(&erg);
      erg=prod;
    }
    if(i!=0) pDelete(&pot_array[i]);
  }
  //free res
  omfree(pot_array);
  omfree(int_pot_array);
  return erg;
}

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

Definition at line 585 of file fast_mult.cc.

{
  //only char=0

  if(rChar(r)!=0)
    Werror("Char not 0, pFastPowerMC not implemented for this case");
  if (n<=1)
    Werror("not implemented for so small n, recursion fails");//should be length(f)
   if (pLength(f)<=1)
    Werror("not implemented for so small length of f, recursion fails");
  //  number null_number=n_Init(0,r);
  number* facult=(number*) omAlloc((n+1)*sizeof(number));
  facult[0]=n_Init(1,r->cf);
  int i;
  for(i=1;i<=n;i++)
  {
    number this_n=n_Init(i,r->cf);
    facult[i]=n_Mult(this_n,facult[i-1],r->cf);
    n_Delete(&this_n,r->cf);
  }

  lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long));

  kBucket_pt erg_bucket= kBucketCreate(currRing);
  kBucketInit(erg_bucket,NULL,0);
  const int f_len=pLength(f);
  int* exp=(int*)omAlloc(f_len*sizeof(int));
  //poly f_terms[f_len];
  poly* f_terms=(poly*)omAlloc(f_len*sizeof(poly));
  poly** term_potences=(poly**) omAlloc(f_len*sizeof(poly*));

  poly f_iter=f;
  for(i=0;i<f_len;i++)
  {
    f_terms[i]=f_iter;
    f_iter=pNext(f_iter);
  }
  for(i=0;i<f_len;i++)
  {
    term_potences[i]=(poly*)omAlloc((n+1)*sizeof(poly));
    term_potences[i][0]=p_ISet(1,r);
    int j;
    for(j=1;j<=n;j++){
      term_potences[i][j]=p_MonMultCMB(f_terms[i],term_potences[i][j-1],r);
    }
  }
  assume(f_iter==NULL);
  poly zw=NULL;
  poly tmp=p_Init(r);
  number one=n_Init(1,r->cf);
  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);


  n_Delete(&one,r->cf);



  //free res

  //free facult
  for(i=0;i<=n;i++)
  {
    n_Delete(&facult[i],r->cf);
  }
  int i2;
  for (i=0;i<f_len;i++)
  {
    for(i2=0;i2<=n;i2++)
    {
      p_Delete(&term_potences[i][i2],r);
    }
    omfree(term_potences[i]);

  }
  omfree(term_potences);
  p_Delete(&tmp,r);
  omfree(exp);
  omfree(facult);
  omfree(f_terms);
  int len=0;
  poly erg;
  kBucketClear(erg_bucket,&erg, &len);
  kBucketDestroy(&erg_bucket);
  omUnGetSpecBin(&lm_bin);
  return erg;
}

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

Definition at line 272 of file fast_mult.cc.

{
  int vn=1;
  if((f==NULL)||(g==NULL)) return NULL;
  int df=p_GetExp(f,vn,r);
  int dg=p_GetExp(g,vn,r);
  if ((df==0)||(dg==0))
    return pp_Mult_qq(f,g,r);
  if (df*dg<100)
    return pp_Mult_qq(f,g,r);
  // if (df*dg>10000)
  //  return
  //    do_unifastmult_buckets(f,g);
  //else
  return do_unifastmult(f,df,g,dg,vn,unifastmult,r);

}