Binomial improvements

Torbjorn Granlund tg at
Sun Dec 11 23:39:24 CET 2011

bodrato at writes:

  > I suspect that one remaining optimisation for the smallest operands is
  > to get rid of the final lshift.  By being cleverer with 2 removal from
  You can get rid of the final lshift (and all i2cnt and j2cnt update code)
  by pre-computing the exponent of 2 in advance:
  cnt = popcount(k) + popcount(n - k) - popcount(n)
Could you please elaborate somewhat on this?

I buy your expression for cnt.

But that doesn't make it obvious how to eliminate the lshift and the
bookkeeping of made shifts.

I assume your idea is to suppress all but cnt dividend factor right
shifts.  It will probably be easiest to suppress the first ones (even if
that means we carry around slightly larger numbers).


More information about the gmp-devel mailing list