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.

---

Request for Question Clarification by richard-ga on 15 Apr 2005 09:32 PDT

Hello

It's difficult to show work in answering a question like this, because
one million factorial is a number with 5.5 million digits.
http://media.wolfram.com/tsn/esn.issue1.2003.pdf

Ben Bradley provides C source code to calculate One Million Factorial,
which he credits in part to Bill Little.  He describes the program
here:
http://www.mindspring.com/~benbradley/number_theory.html
and he posts the source code here:
http://www.mindspring.com/~benbradley/bigfact.cpp


Regards,
Google Answers Researcher
Richard-ga

---

Clarification of Question by star13-ga on 15 Apr 2005 23:17 PDT

Scientific notation to about 6 significant figures of
accuracy is fine for the answer.  But I'm looking for
more than the answer.  I really need to understand the process of
obtaining the answer.  That's why I requested showing the work step by
step.  I'm not familiar with all the math particulars of this problem
and have only recently been introduced to factorials.  Explaining each
step will enable me to perform the same operations on other large
factorials.

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

---

Clarification of Answer by mathtalk-ga on 16 Apr 2005 19:20 PDT

Unfortunately the apostrophe in the Wikipedia article seems to break
the Google Answers URL "wrapper".  This should work instead:

[[Stirling's approximation -- Wikipedia]
http://en.wikipedia.org/wiki/Stirling%27s_approximation

regards, mathtalk-ga

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.

There, I told you it had 5.5 million digits.