Can one know how large a factorial would be before calculating it?

Question

I'm using GMP to calculate very large factorials (e.g. 234234!). Is there any way of knowing, before one does the calculation, how many digits long the result will (or might) be?

Answer 1

The logarithm of the factorial can be used to calculate the number of digits that the factorial number will take:

This can be easily translated to an algorithmic form:

//Pseudo-code
function factorialDigits (n) 
  var result = 0;

  for(i = 1; i<=n; i++)
    result += log10(n);

  return result;

Answer 2

You can transform Stirling's approximation formula using simple logarithmic math to get you the number of digits:

n!         ~ sqr(2*pi*n) * (n/e)^n
log10(n!)  ~ log10(2*pi*n)/2 + n*log10(n/e)

Hardware float math is sufficient for this, which makes it lightning fast.

Answer 3

Stirling's Approximation gives an approximation of of the size of n!

See the Wikipedia page for the derivation.

Answer 4

it would be

nlog(n) - n + log(n(1 + 4n(1 + 2n)))/6 + log(pi)/2

see topic "rate of growth" @ http://en.wikipedia.org/wiki/Factorial Srinivasa Ramanujan method

Answer 5

Yes, see Stirling approximation

It says n! ~= sqrt(2*Pin)(n/e)^n. To get the number of digits, take 1+log(n!)/log(10).

Answer 6

Well about four people have mentioned Stirling so... another option is a LUT storing the number of digits for each of the first N factorials. Assuming 4 bytes for the integer and 4 bytes for the number of digits, you could store the first 1,000,000 factorials in around 8MB.