Divide and conquer binomial

bodrato at mail.dm.unipi.it bodrato at mail.dm.unipi.it
Thu Dec 22 08:25:34 CET 2011

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

I wrote some code to generalize the DC approach to binomial
I tested it with bin(12345678901234567890123,k), here are the timings:

k  old-cycles   new-cycles sizeinbase(res,2)
0        1630         1440          1
1        1830          790         74
2        2670         1310        146
4        3850         8150        289
9        7690        12040        643
18       18570        25170       1269
37       42130        58170       2572
75      134220       181020       5141
150      483330       395640      10136
301     1755640      1052250      20040
602     6198380      2750300      39483
1205    22748170      7240040      77830
2411    91214650     19464480     153318
4822   367013120     52394570     301820
9645  1524299180    140377010     594062
19290  6307145390    372390070    1168842
38580 25443596180   1013052090    2299111
77160 ###########   2404496880    4521070
154320 ###########   5902365890    8887828
308641 ###########  13789221420   17467080
617283 ###########  32058174180   34316941
1234567 ###########  75451795730   67399379

As you can see, with k=38580 the new code is 25 times faster than current
bin_ui. With k=1234567 it takes almost 75Gcycles to produce the 8Mb of the
result.

Regards,
Marco

--
http://bodrato.it/software/combinatorics.html

```