Binomial Coefficients

Josh Liu zliu2 at
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