> This is why mathematical libraries will have not only gamma functions but also loggamma functions.
This is super useful for combinatorial problems too, because gamma(N+1) = N!. Some examples where I've used it include:
- Erasure code durability math. The standard approximation has a N!/k! factor (see [1], equation 2.3), which gets out of hand numerically as N gets large. gamma(20) is 1.2e17, while lgamma(20) is only 39.3.
- Hash code collision math. The standard solution (see [2], for example) includes a factor of N!, which is an alarmingly big number when N is 2**128. In these cases, even the lgamma often doesn't fit into a 'double', and you need both logs and arbitrary precision to find exact solutions (better behaved approximations exist).
I work on numerical evaluation of special functions. Fyi, typically a better way to evaluate Gamma ratios is to use the Lanczos approximation. See the Boost math documentation [0] for good explanation of the problems with calculating n! / k! as
exp(lgamma(n+1) - lgamma(k+1)).
The form I use for the approximation is:
gamma(x) = factor(x) * lanczos_sum_expg_scaled(x)
where
factor(x) = ((x + lanczos_g - 0.5)/e)*(x - 0.5)
and lanczos_g is a constant.
When dealing with Gamma ratios, you can often cancel the factors nicely, giving a highly accurate approximation which doesn't overflow. It's curious I saw your comment when I did. I was just tinkering with the Lanczos approximation earlier today.
If you use Python, the Lanczos approximation is available in SciPy using
from scipy.special._ufuncs import _lanczos_sum_expg_scaled
and you can use lanczos_g = 6.024680040776729583740234375
Take your desired probability, say one-in-a-million
prob = 0.999999
And calculate the bitspace. In this case, 12 base-62 digits
space = 62 ** 12
Take the natural log of the probability, times -2, times the bitspace. The sqrt of that is approximately the number of items that can be shoved into the bitspace before there is a one-in-a-million chance of collision.
A decent approximation to n! is sqrt(2pi n) * (n/e)^n. A worse approximation is that n! is about (n/e)^n.
So, if b(n) is the base in b^n=n!, then b(n) is about (n/e). [I see this as the key observation of the article.]
Keeping in mind that (n/e)^n is a bit smaller than n!, a more accurate value for b(n) is a little higher than n/e.
So it makes sense that 25! ~= 10^25 because 25/e is a bit below 10, and the adjusted value for b(n) ought to be a little higher than 25/e; 10 will do in this case.
You're going to need some kind of result on the occurence of primes at least, because if you remove all factors greater than some prime you trivially get perfect powers (e.g. 6! ≈ 12² if you ignore the factor 5).
(After thinking about it some more, perhaps not trivially.)
It's an approximation. The sentence is perhaps confusing since it might imply that n! ≈ 10^n but that's not the case, the article uses 24 and 25 as the cut point where the approximation is true.
A simpler way to think of the approximation is that 24! multiples together all fifteen numbers from 10 to 24, all of which add at least another power of 10, and you get approximately another nine powers of ten from multiplying in 1 through 9. You end up around 6.2e23 which rounds up to the approximation.
Going up to the next factorial bumps it up (approximately) another power of ten since you are multiplying by 2.5 and 10. In reality it’s around 1.5e25 which is also a reasonable approximation.
Over simplification: a number times 25 is closer to the number times 10 than it is to the number times 100.
Because 25! = 25*(24!), and 25 itself is 100/4. So 25! = 10*(10/4)*24! Now since we are given 24! ~10^24, it follows that 25! ~ (10/4)*10^25. But 10/4 is just a bit over 2, not a strong enough multiplicative factor to break the "approximately equals relationship". Therefore 25! ~ 10^25.
QED
They are not equal, nor approximate either. In this text they kinda use the approximation sign (≈) more like "same order of magnitude". Because if you do a comparison you find out that it's a 60% error between those numbers.
The basic approximation I use is
n! ~ (n/e)^n so ln(n!) ~ n(ln(n)-1).
The basic inequality is
(n/e)^n < n! < (n/e)^{n+1}.
When considering convergence of series using the n-th root test,
(n!)^{1/n} ~ n/e so
((an)!)^{1/n} = (((an)!)^{1/(an)})^a ~(an/e)^a = a^an^a/e^a.
Saying (2n)! ≈ 2^(2n)*(n!)^2 means he's approximating the central binomial coefficient (2n choose n) as 2^(2n). In reality, 2^(2n) is really the sum of all binomial coefficients (2n choose k) for k=0..2n. So clearly this is going to be an underestimate, as we're approximating the sum of 2n terms by only one of them.
However, since the biggest term in the sum of 2n positive numbers is clearly within a factor 2n of the entire sum, the ratio of the logarithms is at least log(2^(2n) / 2n) / log(2^(2n)) = 1-log(2n)/(2n) which converges to one pretty quickly.
And, in fact, a tighter analysis would show that the error decreases faster than what I outlined.
If you are allowed to use R for base and exponent then this is tautological because Z is a tiny subset of R. And factorials are by definition in Z, which is closed under multiplication.
If the linear relationship is the interesting part then lead with that.
I think missing here is that "=" should be a "≈", and that "b" should be an integer. Otherwise this is trivially false (consider 2!=b^2 if b must be integer) or true (if b need not be integer).
It's leading on to the next part: "What’s interesting is that b is very nearly a linear function of n. In hindsight it’s clear that this should be the case—it follows easily from Stirling’s approximation—but I didn’t anticipate this before I plotted it."
Am I misreading the article, or is it actually saying that every factorial is approximately a power? The title makes it sound like it's exactly a power.
Every number is a power if you allow non-integers. But it seems indeed like it means _near_ an integer power in this case. The factorial of 3 is 6 but 6 is not a non-trivial integer power of anything. I don't like the title either.
The article also says, you can find a base b such that n! = b^n for any factorial. Guess what, you can do this for any number x and any n to find b such that x = b^n, whether x is a factorial or not: b is x ^ (1/n). Not sure what Stirling's approximation should have to do with this, and why = and ≈ are being used inconsistently in this post.
Ignoring my complaints of this particular post, this is a pretty great blog though, and I remember being helped by the linked older blog post article about log1p and expm1 before!
The Stirling's approximation part of it is about why exp(log(n!)/n) is nearly linear. I think what he's saying is basically: if you take the log version of Stirling's approximation, ln(n!) = n*ln(n) - n + O(ln(n)), ignore the big O term, then divide both sides by n and take e to the power of each side, you get the formula for the `b` from the article on the left, and n/e on the right, which is linear.
I've never actually worked with Stirling's approximation, but I guess if you have a certain set of context, this fact would be obvious?
The Stirling's approximation is a good way to implement an accurate gamma function approximation on PC/calculators/..., but it's just a formula to implement, it doesn't necessarily mean you think about fun facts like this while implementing it...
> My colleagues and I have decades of consulting experience helping companies solve complex problems involving data privacy, math, statistics, and computing.
> Let’s talk. We look forward to exploring the opportunity to help your company too.
Getting more attention then clarifying the intent in the body is sometimes mischievous (read: every tabloid newspaper), but it nonetheless brings more good attention that it would have without the click bait. If that leads to more consulting work for the author, good for him.
(it kind of feels weird calling a high-number approximation “clickbait” but, in some circles…)
It's either inaccurate or trivial depending on how you interpret it:
- If you only allow the base to be an integer, then it's inaccurate.
- If you allow the base to be a real number, then you're really just saying "every factorial is a positive number", which is a trivial fact if you know what a factorial is.
And he really doesn't give a very nice formula for it.
Numerically, the point of the article is the fact that
n! \approx (0.826523 + n*0.373522)^n
For n in the range from 10 to 50, this is within 5% of the right answer.
But I really don't see that this is all that much simpler than Stirling's approximation and it is considerably less accurate and not asymptotically very good. Stirling's formula is within about 1% for all n>10 and within 0.1% for n>90.
Actually computing gamma(n) or lgamma(n) to high precision requires a bit more effort than this, but as an approximation, Stirling's formula is really pretty good.
This is super useful for combinatorial problems too, because gamma(N+1) = N!. Some examples where I've used it include:
- Erasure code durability math. The standard approximation has a N!/k! factor (see [1], equation 2.3), which gets out of hand numerically as N gets large. gamma(20) is 1.2e17, while lgamma(20) is only 39.3.
- Hash code collision math. The standard solution (see [2], for example) includes a factor of N!, which is an alarmingly big number when N is 2**128. In these cases, even the lgamma often doesn't fit into a 'double', and you need both logs and arbitrary precision to find exact solutions (better behaved approximations exist).
[1] "Notes on Reliability Models for Non-MDS Erasure Codes" https://dominoweb.draco.res.ibm.com/reports/rj10391.pdf [2] https://en.wikipedia.org/wiki/Birthday_problem