Binomial improvements

Torbjorn Granlund tg at
Sun Dec 11 23:29:09 CET 2011

bodrato at writes:

  There is one strength in the code I wrote for binomial: code recycling.
Yes, that's very nice.

  For example: my basecase code to compute the odd component of the
  factorial does not "shift out twos", it uses the following trick.
  Let n be an integer. And let oddfac(n)= n! >> (n-popcount(n)) be the odd
  factor of the factorial of n. Then oddfac(n)=oddfac(floor(n/2))*(n-n%2)!!
I need to think more about that (after some sleep).
  Maybe this is a good trick, maybe it is not, but my proposal is: let's
  start optimising the factorial, then we will recycle the code for the

  Both my factorial and my binomial code use a function (you can find it in
  the current fac_ui.c in the repo) taking a vector of limbs, and obtaining
  the product of them all: it is currently called mpz_prodlimbs(res, *vec,
  len). Again, is it good or is it not? Please look at it and comment. If it
  is good, let's use it for the binomial too. If it is not, let's change it
  also for the factorial...
I'll have a look the next few days.

More information about the gmp-devel mailing list