Re: Binomial Coefficients

[Kevin Ryde]

Libor Spacek <address@hidden> writes:
>
> I wonder whether the following formula may be faster than your
> implementation? I know it is recursive (oh horror!!) but it does reduce 
> quickly and, most importantly, it completely eliminates division:
>
> binom(n,k) = 1 + k(n-k) + sum(i=2,min(k,n-k), binom(k,i)*binom(n-k,i) )

Don't know, maybe.  Looks like it might end up doing quite a bit of
work by the time it sums and recurses.

It's certainly likely the current implementation could be improved
though.  It ends up more or less quadratic, due to doing Nx1
multiplies and divides all the way up to the final result.  Fine if k
is small, but not good if k is close to n/2.

One fairly obvious possibility, if n is not too big, would be to work
out the prime factors of the result, based on the factorials involved,
and multiply them up in a "balanced" fashion like mpz_fac_ui does.