Divide and conquer binomial
Niels Möller
nisse at lysator.liu.se
Thu Dec 15 16:08:51 CET 2011
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.
More information about the gmp-devel
mailing list