Binomial improvements
Torbjorn Granlund
tg at gmplib.org
Sun Dec 11 03:30:54 CET 2011
nisse at lysator.liu.se (Niels Möller) writes:
For the smallest n (where the result is known to fit in one limb), maybe
one could do the simple thing and just compute
n (n-1) ...(n-k+1) k^{-1} (k-1)^{-1} ... (mod B)
one factor at a time (and with a table of the needed inverses)? There's
no point in trying to get operations balanced. Although it might make
sense to not have a single long dependency chain, for machines which can
do several multiplications in parallel.
Will k^{-1} and (k-1)^{-1} mod B, with B presumably being a power of 2,
both really exist? ;-)
We could actually walk down the factorial path and tabulate for n < n'
and k < k', for some suitably small n', k'.
But that should not be don't unless it simplifies the general basecase
code, since 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"...)
Which is the largest n such that n over floor(n/2) fits in 32 or 64
bits? A test which uses a specific k, rather than the worst case, would
also be useful. I think you mentioned getting a size estimate from
Stirlings formula.
log2(2n over n) ~= 2n.
(Actually, this might not be 100% true, but for interesting values of n,
it is close.)
--
Torbjörn
More information about the gmp-devel
mailing list