Divide and conquer binomial

[bodrato at mail.dm.unipi.it]

Ciao,

Il Gio, 15 Dicembre 2011 11:10 am, Niels M�ller ha scritto:
> 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

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)

>      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

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

Regards,
Marco

-- 
http://bodrato.it/