Binomial improvements

Niels Möller nisse at lysator.liu.se
Sun Dec 11 09:44:18 CET 2011


Torbjorn Granlund <tg at gmplib.org> writes:

> We could actually walk down the factorial path and tabulate for n < n'
> and k < k', for some suitably small n', k'.

At least a table för k should take little memory. For each k < k', it
could tabulate not only k! but also a hensel inverse (of the odd part,
and the shift count) of one or two limbs. Should be useful also for the
case of large n and small k.

> I doubt applications will be dependent on the performance of
> limb sized binomial coefficients.  (They should then perhaps not be
> using GMP, but the well-known type "int"...)

Maybe the single-limb result case is not very interesting, but
applications which need that could make use of the same tables and bdiv
machinery, so it would make sense to me to provide some well optimized
gmp function for that.

Regards,
/nisse

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.


More information about the gmp-devel mailing list