Binomial Coefficients

[Kevin Ryde]

Come BERBAIN <berbain at ensta.fr> 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
denominator).

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.