Se puede saber qué tan grande sería un factorial antes de calcular que?

Question

Estoy usando GMP para calcular factoriales muy grandes (por ejemplo, 234234). ¿Hay alguna manera de saber, antes de que se hace el cálculo, el número de dígitos de largo el resultado (o podría) ser?

Answer 1

La logaritmo del factorial se puede utilizar para calcular el número de dígitos que el número factorial se llevará a:

Esto puede ser fácilmente traducido a una forma algorítmica:

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

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

  return result;

Answer 2

Puede transformar de Stirling fórmula usando matemáticas simples logarítmica para conseguir que el número de dígitos:

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

matemáticas flotador hardware es suficiente para esto, lo que hace que la velocidad del rayo.

Answer 3

aproximación de Stirling da una aproximación del tamaño de la de n!

Consulte la página del Wikipedia para la derivación.

Answer 4

sería

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

ver tema "tasa de crecimiento" @ http://en.wikipedia.org/wiki/Factorial método Srinivasa Ramanujan

Answer 5

Sí, consulte Stirling aproximación

Se dice n! ~ = Sqrt (2 * pi n) (N / E) ^ n. Para obtener el número de dígitos, tomar 1 + log (n!) / Log (10).

Answer 6

Bien sobre cuatro personas han mencionado Stirling así que ... otra opción es una LUT que almacena el número de dígitos para cada uno de los primeros N factoriales. Suponiendo 4 bytes para el número entero y 4 bytes para el número de dígitos, podría almacenar los primeros 1.000.000 de los factoriales de 8 MB alrededor.