# Divide and conquer binomial

Torbjorn Granlund tg at gmplib.org
Thu Dec 22 12:44:43 CET 2011

```bodrato at mail.dm.unipi.it writes:

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.

Very interesting!  Nice apparent complexity.  (Did you analyse it?)

This code does not cope with non-zero remainders in any divisions,
right?  I sketched an algorithms that allow that, and discussed it with
Niels.  He wasn't very convinced about the viability of my approach, and
I ran out of time for the moment.  I'd like to explore that idea in the
future, though, since it makes for a very balanced computation.

Before I temporarily abandoned GMP combinatorics for uni duties, I
hacked a(nother) basecase n-over-k function, this time for small k and
unlimited n, aptly named smallk_bin_uiui.c (see
http://gmplib.org/devel/).  This time, I think I finally obsolete the
old code over the entire place, perhaps also your improved verson of it.

--
Torbjörn
```