Divide and conquer binomial

[bodrato at mail.dm.unipi.it]

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