Divide and conquer binomial

[Niels Möller]

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.