Binomial Coefficients

Kevin Ryde user42 at
Fri May 7 02:59:16 CEST 2004

Come BERBAIN <berbain at> writes:
> what exactly is this prime powering scheme?
> how to use the decomposition of n to compute (n n/2)?

You can pretty easily work out the primes which occur in a factorial
n!, and can calculate by raising those primes to the right power.

Writing a binomial in terms of factorials lets you work out the powers
the apply in it (powers in the numerator, less the powers in the

The current gmp binomial code is quadratic, in that it just works
along multiplying and dividing by individual "i" values (or a limb
worth of those).  Powering gets bigger operands into play, allowing
the sub-quadratic multiplication algorithms to be used.

More information about the gmp-discuss mailing list