13
$\begingroup$

I'm wondering if people had a recommendation for approximating $\log(n!)$. I've been using Stirlings formula,

$ (n + \frac{1}{2})\log(n) - n + \frac{1}{2}\log(2\pi) $

but it is not so great for smaller values of $n$. Is there something better? If not, should I calculate the exact value and switch to the approximation for larger values? If so, what would be a good value of $n$ for making the switch?

UPDATE: Thanks for all the replies! I did a calculation of the choices presented (see Python code at the bottom of this message). Results below. And the winner is... Ramanujan, with the supernatural ability of being within $10^{-4}$ of the correct answer for all values of $n$, or at least it seems so - I did not experiment extensively. Assuming this is the case, approximations are hardly needed, though I might use exact values up to n=10 or so.

I came across Ramanujan's formula yesterday at the bottom of the Wikipedia page for Stirlings formula yesterday, where it was chacterized as "apparently superior". :-) I initially did not take it seriously, but then saw it again here. Does anyone know of a derivation?

*************
value to take the log factorial of is 1
Exact value is 0.0
Small value approximation (K.V. Raman) is -1.0
Stirling is -0.0810614667953
Stirling with extra term is -0.00101875912179
Ramanujan is -0.000143497498377
*************
*************
value to take the log factorial of is 2
Exact value is 0.69314718056
Small value approximation (K.V. Raman) is 0.0794415416798
Stirling is 0.651806484605
Stirling with extra term is 0.805957164432
Ramanujan is 0.693112511922
*************
*************
value to take the log factorial of is 5
Exact value is 4.78749174278
Small value approximation (K.V. Raman) is 4.6566274746
Stirling is 4.77084705159
Stirling with extra term is 5.11915374586
Ramanujan is 4.78748794075
*************
*************
value to take the log factorial of is 10
Exact value is 15.1044125731
Small value approximation (K.V. Raman) is 15.3284360229
Stirling is 15.0960820096
Stirling with extra term is 15.7022178132
Ramanujan is 15.1044119984
*************
*************
value to take the log factorial of is 20
Exact value is 42.3356164608
Small value approximation (K.V. Raman) is 42.9103777446
Stirling is 42.3314501411
Stirling with extra term is 43.3122793941
Ramanujan is 42.3356163818
*************
*************
value to take the log factorial of is 1000
Exact value is 5912.12817849
Small value approximation (K.V. Raman) is 5914.66303426
Stirling is 5912.12809515
Stirling with extra term is 5916.56287235
Ramanujan is 5912.12817849
*************

def logfact(n):
    from math import log
    sum = 0
    for i in range(1, n+1):
        sum = sum + log(i)
    return sum

def smallvalapprox(n):
    from math import log, pi
    return (n+1)*log(n) - n

def stirling(n):
    from math import log, pi
    return n*log(n) - n + 0.5*log(n) + 0.5*log(2*pi)

def stirlinge(n):
    from math import log, pi
    return n*log(n) - n + 0.5*log(n) + 0.5*log(2*pi) + log(1+(1.0/12*n))

def r(n):
    from math import log, exp, sqrt, pi
    #return sqrt((2*x + (1.0/3))*pi) * (x**pi)*(exp(-x))                                                                                                           
    return n*log(n) - n + (log(n*(1+4*n*(1+2*n))))/6 + log(pi)/2


def logfactapprox(x):
    print "*************"
    print "value to take the log factorial of is", x
    print "Exact value is", logfact(x)
    print "Small value approximation (K.V. Raman) is", smallvalapprox(x)
    print "Stirling is", stirling(x)
    print "Stirling with extra term is", stirlinge(x)
    print "Ramanujan is", r(x)
    print "*************"

logfactapprox(1)
logfactapprox(2)
logfactapprox(5)
logfactapprox(10)
logfactapprox(20)
logfactapprox(1000)
$\endgroup$
  • $\begingroup$ Use Euler-Maclaurin formula with $ f(x)=logx $ it can be found here en.wikipedia.org/wiki/Euler_Maclaurin $\endgroup$ – Jose Garcia Apr 28 '12 at 21:00
  • 1
    $\begingroup$ More terms are available using Stirling's approximation (with links at the end for other approximations). $\endgroup$ – Raymond Manzoni Apr 28 '12 at 21:39
  • $\begingroup$ Stirling really is only good for large $n$ Just sum up logarithms for small $n$. When to switch depends a lot on your computing environment, so you will have to experiment. $\endgroup$ – J. M. is a poor mathematician Apr 29 '12 at 1:23
  • 1
    $\begingroup$ You might want to look at the pile of approximations here. $\endgroup$ – J. M. is a poor mathematician Apr 29 '12 at 8:24
  • $\begingroup$ @J.M.: Wow, someone sure went to a lot of trouble on that page. Thanks. $\endgroup$ – Faheem Mitha Apr 29 '12 at 8:39
14
$\begingroup$

Approximation for $\log n!$ given by Srinivasa Ramanujan :

$$\log n! \approx n\log n-n+\frac{\log(n(1+4n(1+2n)))}{6}+\frac{\log(\pi)}{2}$$

$\endgroup$
  • $\begingroup$ I was looking into this because I was reading a post comparing various languages' speed in solving the 8 queens puzzle, and I was curious as to why logging the Y-axis of the graph of their performance as board size increased would not result in a decent-looking graph. Thanks to Ramanujan, this is pretty obvious. $\endgroup$ – jm324354 May 10 '18 at 17:52
4
$\begingroup$

For smaller values of $n$

$$ \log n! \approx (n+1) \log n - n$$

Assuming $\log = \log_e$ (In other words, $\log$ is to the base $e$)

$\endgroup$
4
$\begingroup$

Stirling's approximation gets better as $n$ gets higher, so storing a table of small values and switching over for large $n$ is quite viable. It's a trade between size of the table and accuracy. You could also use more terms in the approximation. The next is $\ln(1+\frac 1{12n})$. For $n$ in the 20's or 30's that decreases the error from a few thousandths to a few millionths. That will replace many entries in your table. The fact that the error in Stirling's approximation is bounded by the first neglected term gives you an easy way to find the best number of terms as a function of $n$ if you want.

$\endgroup$
2
$\begingroup$

According to an answer in this post (i.e. a possible duplicate), there exists a better approximation for $\log(n!)$ as opposed to what the accepted answer asserts.

Let $m=n\big(1+4n(1+2n)\big)$, then

$$\log(n!)\approx n\big(\log_e(n)-1\big)+\frac12\Bigg(\frac 13\log_e\left(\dfrac{1}{30}+m\right)+\log_e(\pi)\Bigg)$$

such that $e$ is, by definition, Euler's Constant.

The accepted answer has the exact same approximation, except it excludes $1/30$.

$\endgroup$

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.