Divide and conquer binomial

[Torbjorn Granlund]

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