3
$\begingroup$

Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known) I know that for primes and factorials we can apply Wilson's Theorem but I was wondering if there is also a fast method for composite numbers. For binomial coefficients I was thinking of using recursion and the addition rule: $$\binom{n}{x} + \binom{n}{x+1} = \binom{n+1}{x+1}$$ somehow but I'm not sure really how to go about it. Any suggessions? Thanks.

$\endgroup$
1
  • $\begingroup$ Do you know the factorization of the modulus? Please edit the question to specify, as that makes a tremendous difference to the best answer. $\endgroup$
    – D.W.
    Jul 21, 2014 at 22:20

1 Answer 1

6
$\begingroup$

If $p$ is prime and $n = n_\ell \ldots n_0$, $x = x_\ell \ldots x_0$ in base $p$, then (Lucas' theorem) $$ \binom{n}{x} \equiv \binom{n_\ell}{x_\ell} \cdots \binom{n_0}{x_0} \pmod{p}. $$

For a product of distinct primes, you can apply the Chinese remainder theorem. So it remains to deal with prime powers. Such a method is described in this paper of Andrew Granville, though it's not as nice as the formula above.

$\endgroup$
3
  • $\begingroup$ Thanks. Is there another efficient method if the factorization of the modulus is not initially known? $\endgroup$
    – Ari
    Jul 21, 2014 at 17:53
  • $\begingroup$ Nothing that I'm aware of. $\endgroup$ Jul 21, 2014 at 18:38
  • $\begingroup$ I implemented Andrew Granville's algorithm here : github.com/elaqqad/HackerRank/blob/master/… $\endgroup$
    – Elaqqad
    Dec 20, 2016 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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