Divide and conquer binomial
Niels Möller
nisse at lysator.liu.se
Thu Dec 15 11:10:21 CET 2011
bodrato at mail.dm.unipi.it writes:
> Yes, there is a _very_naive_ implementation of this in the code I tested
> last year ( http://bodrato.it/software/combinatorics.html#bin_uiui ).
Do you think a dc algorithm of this type can be powerful enough to
compute, e.g., bin(2^80, 2^20)? The bitsize of bin(n,k) should be
computable using
(lngamma(n+1) - lngamma(k+1) - lngamma(n-k+1)) / log(2)
if one uses sufficient precision (I just increased the pari/gp precision
to 100 digits, "\p 100", which ought to be more than enough). (An even
rougher approximation is k log_2(n/k)). Then I get the following sizes
of the involved expressions:
bin(2^80, 2^20) 64427324 7.7 MB
= bin(2^80, 2^19) 32737944 3.9 MB
* bin(2^80-2^19, 2^19) 32737944 3.9 MB
/ bin(2^20/2^19) 1048565 0.12 MB
It seems the algorithm must be applied recursively, but one would still
want to reuse common expressions.
> Let's look at the second level:
>
> bin(n,k)=(bin(n , k/4) bin(n-k/4 , k/4) / bin(k/2,k/4)) *
> (bin(n-k/2, k/4) bin(n-k/2-k/4, k/4) / bin(k/2,k/4)) / bin(k,k/2) .
If we expand the bin(k, k/2) term as well, we get
bin(n, k/4) bin(n-k/4, k/4) bin(n-k/2, k/4) bin(n-3k/4, k/4)
bin(n, k) = --------------------------------------------------------------
bin(k, k/4) bin(3k/4, k/4) bin(k/2, k/4)
It's not obvious to me which factors divide which, but it's clearly
desirable to do divisions early, before forming a large product.
/nisse
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list