How does a calculator calculate binomial coefficients for large $n$?

325 Views Asked by At

I've got an interesting puzzle. I'm playing around on a Casio fx-991EX and I notice it has a binomial distribution function. Trying to see how large of a value of $n$ it could take, thinking that in the guts of the computer it was translating my query into factorials and calculating it that way, I put in values of $n$ such that $n>1000$. To my surprise, the binomial function has no issues taking these extremely large values of $n$ (way larger than the factorial or $^n C_r$ functions can take).

I imagine within the calculator is some in built condition that forces it to instead calculate an approximation using the normal function. Does anybody know if this is true/if not, how it calculates it?

1

There are 1 best solutions below

1
On

Even by hand, you can have good approximations $$\binom{n}{m}=\frac{\Gamma (n+1)}{\Gamma (m+1)\,\,\Gamma (n+1-m)}$$ Let $m=kn$ ($k\leq \frac 12$), take logarithms, use three times Stirling approximation for large $n$ and finish using Taylor series to obtain $$\log \left(\binom{n}{k n}\right)=\left((k-1)\log(1-k)-k\log(k)\right)\,n+$$ $$-\frac 12 \log (2 \pi (1-k) k\, n)+\frac{k^2-k+1}{12 (k-1) k\,n}+\frac{-k^6+3 k^5-3 k^4+k^3-3 k^2+3 k-1}{360 (k-1)^3 k^3\,n^3}+O\left(\frac{1}{n^5}\right)$$ and exponentiate the result.

Trying for $n=123456$ and $m=7890$ this would give $$\color{red}{2.7434922768176718837476}817\times 10^{12736}$$ instead of $$2.7434922768176718837476105\times 10^{12736}$$