Loading...
Searching...
No Matches
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.

{
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);
}
}
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
f
FILE * f
Definition checklibs.c:9
min
static int min(int a, int b)
Definition fast_mult.cc:268
mults
STATIC_VAR int mults
Definition fast_mult.cc:13
do_unifastmult
static poly do_unifastmult(poly f, int df, poly g, int dg, int vn, fastmultrec rec, ring r)
Definition fast_mult.cc:72
max
static int max(int a, int b)
Definition fast_mult.cc:264
multifastmult
poly multifastmult(poly f, poly g, ring r)
Definition fast_mult.cc:290
pNext
#define pNext(p)
Definition monomials.h:36
NULL
#define NULL
Definition omList.c:12
p_Normalize
void p_Normalize(poly p, const ring r)
Definition p_polys.cc:3939
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_GetExp
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:471
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition p_polys.h:1167
rVar
static short rVar(const ring r)
define rVar(r) (r->N)
Definition ring.h:598

## Mults()

int Mults | ( |  | ) |

Definition at line 14 of file fast_mult.cc.

{
return mults;
}

## pFastPower()

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;
}
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
assume
#define assume(x)
Definition mod2.h:389
omfree
#define omfree(addr)
Definition omAllocDecl.h:237
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
p_ISet
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition p_polys.cc:1298
pDelete
#define pDelete(p_ptr)
Definition polys.h:187

## pFastPowerMC()

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

Definition at line 588 of file fast_mult.cc.

{
//only char=0
if(rChar(r)!=0)
WerrorS("Char not 0, pFastPowerMC not implemented for this case");
if (n<=1)
WerrorS("not implemented for so small n, recursion fails");//should be length(f)
if (pLength(f)<=1)
WerrorS("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;
}
n_Mult
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:639
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_Init
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:541
j
int j
Definition facHensel.cc:110
lm_bin
STATIC_VAR omBin lm_bin
Definition fast_mult.cc:429
MC_iterate
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
p_MonMultCMB
static poly p_MonMultCMB(poly p, poly q, ring r)
Definition fast_mult.cc:455
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
POLYSIZE
#define POLYSIZE
Definition monomials.h:233
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349
omGetSpecBin
#define omGetSpecBin(size)
Definition omBin.h:11
omUnGetSpecBin
#define omUnGetSpecBin(bin_ptr)
Definition omBin.h:14
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
p_Init
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1341
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
rChar
int rChar(ring r)
Definition ring.cc:719
kBucket_pt
kBucket * kBucket_pt
Definition ring.h:26

## unifastmult()

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);
}
unifastmult
poly unifastmult(poly f, poly g, ring r)
Definition fast_mult.cc:272