[CLN-list] efficient calculation of binomial

Silvestre Abruzzo abruzzo at thphy.uni-duesseldorf.de
Mon Mar 22 17:41:25 CET 2010


I need to initialize a vector with the binomial coefficients. The code 
is like the following:

for(size_t i=1; i<n;i++){
    nl[i]=cln::binomial(m,m-i);
}

where are involved very big number, something like m=10^10 and n=10^6. 
My purpose is to optimize the preceding optimization by using the result 
of the preceding iteration, i.e.

    binomial(n, n-(i+1))=binomial(n, i)* (n-i)/(i+1)

I tried to implement the multiplication  by storing the result of of 
(n-i)/(i+1) in one cl_RA number, but unfortunately the performance are 
worst than the direct calculation. Do you have any idea how to 
initialize efficiently this vector?

Thank you for your help,

Silvestre Abruzzo



More information about the CLN-list mailing list