Divide and conquer binomial

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> Yes, I think it is. I'll try to write a general code for this. My first
> goal will be to compute bin(2^71,1234567)

Cool.

>> If we expand the bin(k, k/2) term as well, we get
>
> It is not a good idea, in my opinion. Because we already have a fast code
> for it, and its factors are "randomly" distributed among the dividend.

Maybe you're right. The advantage of expanding it as

  bin(k, k/4) bin(3k/4, k/4) / bin(k/2, k)

is that the bin(k/2, k) cancels out. There's a factor (bin(k/2, k))^2 on
the other side of the division, from the expansion of the other binomial
factors.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.