2
$\begingroup$

I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:

$$ \dbinom n k = \frac n k \dbinom {n - 1} {k - 1} $$

Currently, the algorithm computes $\dbinom {n - 1} {k - 1}$, multiplies it by $n$, then divides by $k$. Since signed integers are capped at $2^{32} - 1$ on a computer, which can be a very small limit for large $n$, I want to change the algorithm to divide by $k$ before mixing in $n$. However, computer integer division floors the result if the dividend isn't a multiple of the divisor; for example, $11 / 5 = 2$. So I want to come up with a criteria for whether $k$ divides $\dbinom {n - 1} {k - 1}$ that can be cheaply checked.

Here's my work so far: assuming $n > k$, then $n - 1 \geq k$. Then $(n - 1)!$ will have at least 1 factor of $k$, and $k \mid \dbinom {n - 1} {k - 1}$ if the $(k - 1)!(n - k)!$ factor does not cancel those factors out. If $k$ is prime, then $(k - 1)!$ will have no factors of $k$. $(n - k)!$ will often have less factors of $k$ than $(n - 1)!$, but that is not the case if $n \equiv -1 \mod k$. For example, $5 \not\mid \dbinom 9 4$, because both the numerator and denominator have exactly one factor of $5$.

So I figured out that $n \not\equiv -1 \mod k$ must be true for primes, but I've no idea how to deal with composites. I played around a bit with them, though, and $6$ is another value of $k$ for which $6 \not\mid \dbinom 11 5$, so clearly $k$ doesn't have to be prime. Any tips?

$\endgroup$
4
$\begingroup$

If division by $k$ would give you a non-integer, multiplication by $n$ would give you back an integer. So if you reduce $n/k$ to lowest terms, $n/k = a/b$ with $\gcd(a,b) = 1$, then you can safely divide by $b$ and then multiply by $a$.

EDIT: Another method: Let $q$ be the result of integer division of $N = {n-1 \choose k-1}$ by $k$, and $r = N - q k$ (so $0 \le r < k$ and $N \equiv r \mod k$). Then $\frac{n N}{k} = n q + (n r)/k$, where the multiplication $n r$ is much less likely to produce an overflow.

$\endgroup$
  • $\begingroup$ Thank you, that's a pretty ingenious solution. It is not computationally cheap to reduce a fraction to simplest terms, though (you have to find the GCD, which takes non-constant time). I might end up using this method if no other solutions are available, however. $\endgroup$ – James Ko Apr 29 '17 at 1:16
  • $\begingroup$ Your second solution pretty much hit the mark, since $q$ can be easily gotten by dividing by $k$ and calculating $r$ with a couple of subtractions/multiplications is pretty cheap. For anyone interested, here is the new revision of my binomial algorithm: gist.github.com/jamesqo/d4ccd1c159479bc6b48b58933180a200 $\endgroup$ – James Ko Apr 29 '17 at 4:53
1
$\begingroup$

You might be better off memoizing the traditional formula? If you have a 32-bit roof there isn't much that can take that long.

    #include <stdio.h>
    #define N 50
    int cache[N][N];

    int f(int n, int k) {
            if (k == 0 || k == n) {
                    return 1;
            }
            if (cache[n][k] != 0) {
                    return cache[n][k];
            }
            cache[n][k] = f(n-1, k-1) + f(n-1, k);
            return cache[n][k];
    }

    int main() {
            printf("%d\n", f(2*15, 15));
    }

Edit: as per comment, got rid of bad idea for dealing with leafs of recursion (sorry wrote the original when sleep deprived)

$\endgroup$
  • 1
    $\begingroup$ Interesting method. Why did you choose not to cache and do recursion for values below 2^16, though? $\endgroup$ – James Ko Apr 29 '17 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.