Binomial improvements
Niels Möller
nisse at lysator.liu.se
Sat Dec 10 20:52:28 CET 2011
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.
With some more cleverness, I guess one could also tabulate some partial
products.
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.
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