Floating-point oblivious way to compute multiset numbers I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{1\cdot 2\ \cdots\ k}.$$
The problem is that, if you compute the numerator and denominator separately, you will run very soon into overflow territory, so a better way to calculate this division, since both parts of the fraction have same number of components, is by: $$R = \left(\frac{n+1}{1}\right)\left(\frac{n+2}{2}\right)\cdots\left(\frac{n+k}{k}\right) = \prod_{i=1}^k\frac{n+i}{i} = \prod_{i=1}^k\left(\frac{n}{i} + 1\right)$$
The problem of this approach is that you have to apply floating point arithmetic to do the divisions, which are way more inefficient than using simple integral arithmetic.
But, knowing that the final result would be integral, is there any[1] way to split the big fraction into a sequence of products of fractions so that each fraction has a numerator that is a multiple of its denominator? The idea is to remove any floating point operation to calculate $R$.
Has this formula any property that guarantees that such sequence exists?
[1] Ok, maybe not &quot;any&quot; way would be valid. If the process to avoid the floating point arithmetic would cost more than the floating point arithmetic itself, it won't be worthy.
One common way to work with binomial coefficients without overflow is to use prime factorisation.
Legendre discovered the formula for this, and it is worth proving it for yourself. The factorial of a number can be factorised as powers of primes:
$$n! = p_1^{q_1} p_2^{q_2} \cdots$$
where:
$$q_i = \sum_{k=1}^{\left\lfloor \log_{p_i} n \right\rfloor} \left\lfloor \frac{n}{p_i^k}\right\rfloor$$
Instead of multiplying and dividing, therefore, you can just add and subtract exponents of primes.