Binomial improvements

[bodrato at mail.dm.unipi.it]

Ciao!

Torbjorn Granlund <tg at gmplib.org> writes:
>   (1) Now the number of allowable factors that fit into a limb is tabled.
>       This table takes into account that the mulN functions now shift out
>       twos.

There is one strength in the code I wrote for binomial: code recycling.

I think that this kind of optimisation is very interesting, and it should
be applied also to the basecase factorial.

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.e. we can compute the product of odd numbers from 3 to n, times the odd
numbers from 3 to n>>1, times... till we reach a tabled oddfac().

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.

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...


>   (2) Less scratch space usage, for this needs the latest repo bdiv
>       updates (allowing dividend/quotient operand overlap).

This is a nice improvement.

>   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
>   the dividend, that might be possible.

It is! Also the factorial needs this optimisation.

> Forgot to point to the updated code: See http://gmplib.org/devel/ under
> New binomial code.

I can not find it...

Regards,
Marco

-- 
http://bodrato.it/software/combinatorics.html