Binomial improvements

[Torbjorn Granlund]

I an Marco have discussed about improving the mpz_bin_uiui (and later
also mpz_bin_ui).  These two functions are very poorly implemented in
GMP today, using very rudimentary algorithms.

Here is a first attempt at a faster function, possibly useful as a
basecase for new, asympotically fast code.

This code makes individual multiplied become very fast by using straight
line code for as many product as fits into a limb, and by avoiding
scalar divisions.

The code accumulates reasonably large dividend (from n-k+1, n-k+2, ..., n)
and then as many factors for the divisor (from 1, 2, ..., k).  Since the
number of factors in the divisor is the same as in the dividend (given the
factor order) we know this division yields an integer.  We can therefore
divide using Hensel norm, i.e., using the smooth GMP bdiv functions.

We then loop back, accumulating the next chunk of factors.

The code is attached.  NB: This is rough and contains some silly
allocations.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: bin_uiui3.c
Type: application/octet-stream
Size: 6532 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20111209/1f0a9486/attachment.obj>
-------------- next part --------------

-- 
Torbj?rn