Binomial improvements
Torbjorn Granlund
tg at gmplib.org
Sun Dec 11 23:29:09 CET 2011
bodrato at mail.dm.unipi.it 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
binomial.
OK...
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.
--
Torbjörn
More information about the gmp-devel
mailing list