Binomial improvements

[Niels Möller]

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.