Posted by Math-averse readers! Do not be scared off! You can enjoy this entry even if as far as you’re concerned the equations are pretty pictures of Cypriot syllabary.
Not long ago we looked at adding up lots of consecutive integers. Multiplying consecutive integers is also interesting, and not only that it has a tremendous number of uses all throughout physics and pure mathematics. The function that multiplies the integers from 1 to n is called the factorial function, and rather unusually it’s denoted with an exclamation point, like this:
Here I’m using dots to denote multiplication, as is pretty common in physics. Now the factorial function gets tremendously huge tremendously fast. The factorial of one hundred is almost 10158, which is just mind-bogglingly enormous. Now if you want to find the factorial of one million, you’re absolutely hosed. Your calculator will choke, and I’m pretty sure even sophisticated systems like Mathematica will start to smoke and sputter before finally giving you an “out of memory” error. There’s just no good way to multiply a million integers together, let alone finding the factorial of the much larger numbers in physics that crop up all the time. Maybe we can find a clean approximation which is good for large n? We can.
Since n! is so unwieldy by virtue of its size, let’s chop it down a notch by finding its natural logarithm. We’ll use this old fact from high school algebra:
Knowing that, we can write the log of n!
That’s not an approximation, so far it’s exact. But exact though it is, it’s not very useful. There’s a trick you can use in calculus to approximate a sum with an integral, so we’ll go ahead and use it.
Now evaluate the integral:
Now the number 1 is pretty much by definition negligible in comparison to large n, so we can drop it from the above equation. From there, take the exponential of both sides to recover an expression for the factorial instead of the logarithm of the factorial.
It’s just an approximation, but it’s a good one. Now it turns out that some careful finagling with the limits of integration in the integral (or alternately an entirely different argument involving the gamma function) can improve our estimate. I’ll skip the derivation and present the final result. It’s called Stirling’s approximation, and it’s our Sunday Function:
You might think that since the root n term grows without limit, our original approximation can’t be right. But that’s not the case. The nn term is so much more quickly growing that for many practical purposes it still works fine. After all, really this is an approximation of the logarithm of n factorial anyway. Neither our rough approximation nor the better one actually converges on n!, instead the absolute error merely grows more slowly than n!. That said, the relative error goes to zero using the root n term. It doesn’t if you leave out the root n term.
Those slightly technical matters aside, both expressions are very useful. How about finding that factorial of one million using it? Let’s do it:
Evaluating the first term is easy; the second will make your calculator choke. Some simple tricks involving logarithms will make it very easy though. I’ll save those as an exercise for the alert reader and present the result:
Whew! Now that is a large number, containing more than five and a half million digits. Readers who have done the calculation themselves will have noticed that as we mentioned before the square root term affects the result in this stacked exponential notation not in the slightest. To get that answer took me about 60 seconds worth of writing down a couple lines to keep track of the logarithms and typing the figures into the calculator. To find the answer without Stirling’s approximation would have been utterly beyond my grasp. Thanks, Stirling!
November 9, 2008
November 9, 2008
November 9, 2008
November 9, 2008
November 9, 2008
November 10, 2008
November 10, 2008