Binomial Coefficients
Josh Liu
zliu2 at student.gsu.edu
Wed May 12 02:01:26 CEST 2004
If one wants to compute Binomial[n,k] for fixed n and a large range of
k then it might be more efficient to just compute (x+1)^n using a fast
polynomial multiplication algorithm in conjunction with a fast
exponentiation algorithm. The question I have is rather it is possible
to compute only one coefficient in (x+1)^n using minimum storage space
and/or minimum time using a fast exponentiation algorithm. One can use
Comba's multiplication method in the last stage of the exponentiation
to calculate that single coefficient. It is preferable for the last
multiplication step to be of numbers of roughly equal size in that
case. It's just that the rest of the computation is time and space
consuming. I doubt that it is ever better to use the polynomial
exponentiation method to compute the binomial coefficient.
More information about the gmp-discuss
mailing list