I am trying to find the sum of the first r binomial coefficients for a fixed n.
(nC1 + nC2 + nC3 + ... + nCr) % M
where r < = n.
Is there an efficient algorithm to solve this problem ?
I am trying to find the sum of the first r binomial coefficients for a fixed n.
where r < = n.
Is there an efficient algorithm to solve this problem ?
My first answer was unsatisfactory for several reasons, one of which being that the paper which I referenced is difficult to understand and to implement. So I'm going to propose a different solution to the problem below.
We want to calculate the sum of the first r binomial coefficients for fixed n,
nC0 + nC1 + ... + nC(r-1)
, modulo M. Instead of reducing the computation ofnCk
by reducing n, it makes more sense to reduce k: we neednC(k-1)
already as part of the sum; in addition, we may have r much less than n, so getting at the values by incrementing n could be far less efficient than incrementing r.Here's the idea: First note that if r > n/2 we have
nC0 + ... + nC(r-1) = 2^n - (nCr + ... + nCn) = 2^n - (nC0 + ... + nC(n-r))
where n-r < n/2, so we have reduced the problem to the case where r <= n/2.Next, apply the identity
to calculate the terms of the sum in order. If out integers were unbounded in size, we could calculate
The problem with this is that numbers nCi (and therefore sum) can become enormous, so we have to use big integers, which slow down the calculation. However, we only need the result mod M, so we can use
int
s if we perform calculations mod M inside the loop.Sum and product are straightforward mod M, but division isn't. To divide nCi by k mod 10^6, we need to write nCi and k in the form 2^s 5^t u where u is relatively prime to 10^6. Then we subtract exponents, and multiply by the inverse of u mod 10^6. In order to write nCi in that form, we also need to write n-k+1 in that form.
To put k and n-k+1 into the form 2^s 5^t u where u is relatively prime to 10^6, we could repeatedly check for divisibility by then divide by 2, and the same for 5. However, it seems there should be a faster way.
In any case, the algorithm is now O(r), which seems to be the fastest possible, barring the discovery for a simple mathematical expression for the sum.
Note that the "first" binomial coefficient for fixed
i.e.,n
isnC0
. Letf(n) = nC0 + nC1 + ... + nC(r-1)
. Using the "Pascal's triangle" identity,nCk = (n-1)C(k-1) + (n-1)Ck
we havef(n) = 2f(n-1) - (n-1)C(r-1)
so each of the sums can be computed from the previous by doubling the previous and subtracting(n-1)C(r-1)
.For example, if
and so on.r=3
, thenTo perform the calculations mod m, you would need to pre-calculate the binomial coefficients
(n-1)C(r-1) mod m
. Ifm
is prime, the binomial coefficientsmod m
are cyclic with cyclem^k
(the power ofm
greater thanr-1
). Ifm
is a power of a prime, the results are rather more complicated. (See http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf.) If m has more than one prime factor, the calculations can be reduced to the previous cases using the Chinese Remainder Theorem.