[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