# Divide and conquer binomial

Niels Möller nisse at lysator.liu.se
Wed Dec 14 22:42:39 CET 2011

```Let me summarize my understanding of the binomial, and see if anybody
has any additions. I'm aware of a couple of different algorithms:

1. When the result is small (single limb, possibly with extensions to a
few limbs):

Tabulate the odd part of n! mod B and the corresponding mod B
inverse. Then one can compute the odd part of bin(n, k) using n! /
(k! (n-k)!) and these tables. To deal with the powers of two, use the
cute formula

ctz(n!) = n - popcount(n)

(ctz is count trailing zeros, aka 2-adic valuation, often denoted
v_2).

2. When k is small and n is large, just multiply together n (n-1) ...
(n-k+1), preferably in an order using roughly balanced
multiplications, and divide by k! using tabulated values and
inverses.

3. When k and n are of moderate size, so that it is practical to iterate
over all primes <= n, count multiplicity of each prime in dividend
and divisor. I think Marco has implemented this.

4. When k is of moderate size, and n is too large for iterating over the
primes, but n and k still small enough so that bin(n, k) fits in
available storage, it would make sense to use some divide and conquer
algorithm. For example, bin(2^80, 2^20), which is approximately
2^{64427324.069447006302169138472946275466} (using pari/gp with
default precision and the lngamma function) and needs 61 Mb of
storage.

First, one question is what complexity to expect. The result is of
size N = O(k log n), so I don't think one can't hope for anything
better than O(M(k log n)). I think one should be happy if one get
within a log N factor of that.

One possibly useful identity (assume for simplicity that k is
even) is:

bin(n, k) = bin(n, k/2) bin(n-k/2, k/2) / bin(k, k/2)

Here, we halve the size of k, getting two recursive calls with
essentially the same n (which means that we will unfortunately not
get to use (3) as a base case, only (2). And one recursive call for

I think Marco has tried this or something similar.

* If the complexity is supposed to be close to linear in k, it seems
right to divide into two pieces with size k/2. It should save work
by both (i) getting a reasonably balanced multiplication tree, and
(ii) divide out many common factors early.

* What about bin(k, k/2)? I imagine that k is typically in range for
method (3). Or are there any other shortcuts for this particular
form?

* The factor bin(k, k/2) is still pretty large, of size close to k
(i.e., value on the order of 2^k, or 2^{2^20} in the example
bin(2^80, 2^20)).

If we can somehow divide out most of those factors earlier, that
should save considerable work.

/Niels

--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

```
{"ft_lang_label":"__label__en","ft_lang_prob":0.8879081,"math_prob":0.9584859,"size":2872,"snap":"2023-40-2023-50","text_gpt3_token_len":784,"char_repetition_ratio":0.083333336,"word_repetition_ratio":0.0,"special_character_ratio":0.27715877,"punctuation_ratio":0.13650794,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9974176,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-01T09:08:39Z\",\"WARC-Record-ID\":\"<urn:uuid:c1df08ec-aec6-4554-b3ed-ef8b60778622>\",\"Content-Length\":\"5469\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:84fa4931-6cb6-42b6-8e4b-c627184fb2c5>\",\"WARC-Concurrent-To\":\"<urn:uuid:baba6c96-1449-4cdc-95ef-0ba3d37f05ca>\",\"WARC-IP-Address\":\"130.242.124.102\",\"WARC-Target-URI\":\"https://gmplib.org/list-archives/gmp-devel/2011-December/002095.html\",\"WARC-Payload-Digest\":\"sha1:XM6LAYVBOAYKHQBPZEYZ76SUKUBDSI2A\",\"WARC-Block-Digest\":\"sha1:XHKDXSA457STR7BDWO3FL3EO256HEGUP\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100286.10_warc_CC-MAIN-20231201084429-20231201114429-00561.warc.gz\"}"}