Category: Business and Money
Asked by: star13-ga
List Price: $25.00
15 Apr 2005 08:52 PDT
Expires: 15 May 2005 08:52 PDT
Question ID: 509662
What is 1000000! That is, what is one million factorial? Please show work. I need to see the steps on how to get there too, so please include each step with explanations. Using log, scientific notation, etc.
Re: Large Factorial
Answered By: mathtalk-ga on 16 Apr 2005 19:04 PDT
Hi, star13-ga: From the Clarification you posted above, an approximation of six or more significant figures would be satisfactory. The simplest approach in that case is known as Stirling's approximation: [Stirling's approximation] http://en.wikipedia.org/wiki/Stirling's_approximation [Stirling's Approximation] http://hyperphysics.phy-astr.gsu.edu/hbase/math/stirling.html [Stirling's Approximation (with error terms)] http://ece.colorado.edu/~bart/book/stirling.htm Before we go there, let's review first principles. As the site Richard-ga pointed out to you shows, it is possible to compute the exact multi-million digit integer result 1000000! by carrying out repeated extended precision multiplications. There are many "big number" arithmetic packages available in C or Python or Cobol, so this project could be carried out in a language of your choosing! But what might make sense in terms of a 6-digit accurate approximation is to add the logarithms of 1 through 1000000, rather than doing multiplications. For one thing the resulting logarithm of 1000000! would avoid any difficulty of overflow in floating point computations. If we did it correctly in double-precision, we should be able to squeeze out the leading 6 or 7 decimal digits. If log(x) denote the common (base ten) logarithm, then by a basic "rule of logarithms" that the log of the product is the sum of the logs: log(N!) = SUM log(k) FOR k = 1 to N Of course the same thing holds for another logarithmic base, but if decimal digits are what we want, then the common logarithm is the easiest choice. For if we have log(N!), then we can split it up into the whole integer and fractional parts: log(N!) = floor(log(N!)) + (log(N!) - floor(log(N!))) which you may remember from high school math are referred to as the characteristic (whole integer part) and mantissa (fractional part). C = floor(log(N!)) M = log(N!) - floor(log(N!)) Then N! = (10^M) * 10^C is the "scientific notation" for the result. Here the mantissa, being a positive value between 0 and 1, gives 10^M as a value between 1 and 10 (with roughly the same number of digits of accuracy as M has). The (whole integer) power of 10 needed for this number is simply C. Having said this, however, adding a million logarithms together is still a bit of effort (not for us, of course, but pity the poor PC!), and the rounding errors could be expected to lose us 3 to 4 digits (~10 bits) of precision. If we want to do this more expeditiously and with better control over the precision, then Stirling's approximation is attractive. However let's review the relationship between the common logarithm (base ten) which we denote by log(x) and the natural logarithm (base e = 2.718281828459...) which we denote by ln(x): log(x) = ln(x)/ln(10) So, if we have the natural logarithm ln(1000000!), this may be converted to the common logarithm log(1000000!) with a single constant division (or multiplication). Then we are back in the situation described above, splitting our value into whole integer/characteristic and fractional part/mantissa. What is most often referred to as Stirling's approximation is actually the first one or two terms in an "asymptotic" expansion of n!: n+½ -n n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) - ... ) This is an asymptotic expansion in that while it does not converge as more and more terms are added for fixed n, it does for any fixed number of terms prove to be a better and better approximation (relatively) as n grows without bound. For our purposes, six significant digits, we scarcely need to retain the term involving 1/(12n). One rather clever way to work this term into a formula was suggested by Gosper: n -n n! ~ n e SQRT(2pi*n + 1/3) See these Mathworld pages for further details: [Stirling's Series -- MathWorld/A Wolfram Web Resource] http://mathworld.wolfram.com/StirlingsSeries.html [Stirling's Approximation -- MathWorld/A Wolfram Web Resource] http://mathworld.wolfram.com/StirlingsApproximation.html Now taking the natural logarithm of both sides gives: ln(n!) ~ n ln(n) - n + ½ ln(2pi*n + 1/3) This is the sort of thing we can actually tap out on the Windows calculator applet: for n = 1000000: n( ln(n) - 1 ) = 12815510.557964274104107948728106... ½ ln(2pi*n + 1/3) = 7.826693838712632938864221... -------------------------------------- 12815518.384658112816740887592327... Now to convert this to the common logarithm of n!, divide by ln(10): log(1000000!) ~ 5565708.9171866938714250156916406... Thus the scientific notation for 1000000! will depend on: characteristic C = 5565708 , and mantissa M = 0.9171866938714250156916406... Since 10^M = 8.2639312188778698163179091185559... , our approximation works out to: 1000000! ~ 8.2639312188778698163179091185559E+5565708 which agrees sufficiently with the exact leading digits posted at Ben Bradley's page linked above: 1000000! = 8.263931688331240062376646103172666291...E+5565708 * * * * * * * * * * * * * * * * * * * * * As an experiment to see if more accuracy can be obtained by retaining one more term, let's use the approximation: n+½ -n n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) ) ln(n!) ~ n*(ln(n) - 1) + ½ ln(2pi*n) + ln( 1 + 1/(12n) + 1/(288n²) ) for n = 1000000: n( ln(n) - 1 ) = 12815510.557964274104107948728106... ½ ln(2pi*n) = 7.826693812186809793834304... ln(1+1/(12n))+...) = 0.000000083333371527777970... -------------------------------------- 12815518.384658169624289270340375... Dividing once again by ln(10), we get: log(n!) ~ 5565708.9171867185426298087711153 and once again breaking the parts into the base 10 characteristic and mantissa: 1000000! ~ 8.2639316883315556986809062972533E+5565708 which does give several more digits correctly. regards, mathtalk-ga
Re: Large Factorial
From: elwtee-ga on 16 Apr 2005 11:11 PDT
if that's all you wanted, you should have spoken up sooner. in it's simplist form the concept of factorial isn't particularly daunting. although you will realize why nobody took you up on your offer to show all the work for 1,000,000!. neither will i. the factorial notation is a method of summarizing the number of permutations possible given a specific set of objects. for example if we have three items and let's call them 1,2, and 3 for right now, they can arranged in the following permutations: (1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2) and (3,2,1). six permutations. there is no other possible arrangement of our items. so if we have defined 3! as the number of possible permutations one way to establish the total is to do what we just did, write them all down and count them. clearly that method works much better if our inquiry is about 2! or 3! than it does is the question involves say 194! or worse yet 1,000,000!. you could be writing and counting for a while. the shortcut sophisticated mathematical solution involves nothing more than multiplication. just a bunch of it. the factorial of number n, where n is a positive interger is defined as n(n-1)...2,1 or in plain english, if you are calculating the value of 3! start with the 3 and multiply it by every interger counting down to 1. so 3! equals 3x2x1 which equals 6. but then we knew that already cause we wrote them all down before. 4! to be repetitive would then equal 4x3x2x1 equals 24. there are 24 permutations of four items. at this point if you aren't a believer yet, go ahead and write them all down and count them up. when you are convinced that n!= n(n-1)...2,1 you now see why nobody nor you is going to do that and show all the work. 1,000,000 x 999,999 x 999,998 x i don't think so. when the n in n! gets large the number of trailing zeros in the result grows right along with it. there is a method of calculating the number of zeros in bignumber! but that value, let's call it z, is beyond the scope of your question. i'm sure your stats prof will get to it eventually anyway. hope that helped you a bit.
Re: Large Factorial
From: richard-ga on 17 Apr 2005 06:01 PDT
There, I told you it had 5.5 million digits.
If you feel that you have found inappropriate content, please let us know by emailing us at firstname.lastname@example.org with the question ID listed above. Thank you.
|Search Google Answers for|