Binomial improvements

[Torbjorn Granlund]

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