Binomial improvements

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

>   c = n - k + 1;
>   i = n - k + 2;
>   for (j = 1; j < k; j++)
>     {
>       c = c * i;
>       i++;
>       c = c * zinv[j] >> ctz[j];
>     }

> Is this the best way to handle really small numbers?  This code cannot
> handle k > 32 (with present tables) and n greater then GMP_LIMB_BITS +
> 2.

I think one could tabulate the inverse of k!, rather than the inverse of
each factor. Then you can move that multiply by inverse out of the loop,

   for (j = 1; j < k; j++)
     {
       c = c * i;
       i++;
     }

   c = c * fac_inv[k] >> fac_shift[k];

Maybe this doesn't handle the powers of two right (or at least, it loses
precision by letting zeros accumulate at the low end of c). So maybe one
should do the *shifts* in the loop, but one can still delay the
multiplication by inverse, like

   for (j = 1; j < k; j++)
     {
       c = c * i >> ctz[j];
       i++;       
     }

   c = c * fac_inv[k];

Would that work (I haven't thought very carefully about the math)? The
size of the needed tables is the same, and it ought to give a decent
speedup. fac_inv[k] holds the mod B inverse of the odd part of k!.


/nisse

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