How to simplify or calculate a formula with very big factorials

Question

I'm facing a practical problem where I've calculated a formula that, with the help of some programming, can bring me to my final answer. However, the numbers involved are so big that it takes ages to compute, and I think it might not be necessary. I have the following formula,

$\sum\limits^{k}_{i=m}(N-i)^{k-i}(\frac{1}{N})^k\frac{k!}{(k-i)!i!} \leq a$

from which I need to calculate N. The rest of the values are constants, but in the range of the 100,000s. The factorial there is giving me a headache, since the values involved are too large; what simplifications could I make that will loosen the bounds slightly and thereby simplify the calculation? Are there any standard tricks? Or perhaps a way to calculate this in matlab / octave?

Answer 1

You need Stirling's approximation. It is very accurate for large factorials.

Answer 2

You don't need to compute the individual factorials in order to compute $k!/(k-i)!i!$, since that's the binomial coefficient $\binom{k}{i}$. A simple algorithm for computing binomial coefficients can be found on Wikipedia. A more sophisticated algorithm is due to Goetgheluck (JSTOR); implementations can be found here and here.

Of course, with numbers of the size that you have, this might still not be feasible, and in this case I also recommend Stirling's formula.

Answer 3

Here is a good writeup about implementing Stirling's approximation, along with a reference implementation:

http://threebrothers.org/brendan/blog/stirlings-approximation-formula-clojure/