Si può sapere quanto è grande un fattoriale sarebbe prima di calcolare esso?

Question

sto usando GMP per calcolare molto grandi fattoriali (ad esempio 234234!). C'è un modo di conoscere, prima che si fa il calcolo, il numero di cifre a lungo il risultato sarà (o potrebbe) essere?

Answer 1

Il logaritmo del fattoriale può essere usato per calcolare il numero di cifre che il numero fattoriale prenderà:

Questo può essere facilmente tradotta in una forma algoritmica:

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

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

  return result;

Answer 2

È possibile trasformare di Stirling formula utilizzando la matematica semplice logaritmica per ottenere il numero di di cifre:

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

float Hardware matematica è sufficiente per questo, che lo rende estremamente veloce.

Answer 3

approssimazione di Stirling dà un'approssimazione delle dimensioni di n!

Si veda la pagina del Wikipedia per la derivazione.

Answer 4

sarebbe

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

vedere l'argomento "tasso di crescita" @ http://en.wikipedia.org/wiki/Factorial Metodo di Srinivasa Ramanujan

Answer 5

Si, vedi Stirling approssimazione

Si dice n! ~ = Sqrt (2 * Pi n) (n / e) ^ n. Per ottenere il numero di cifre, prendere 1 + log (n!) / Log (10).

Answer 6

Bene circa quattro persone hanno detto Stirling così ... Un'altra opzione è un LUT memorizzare il numero di cifre per ciascuno dei primi N fattoriali. Supponendo 4 byte per il numero intero e 4 byte per il numero di cifre, è possibile memorizzare i primi 1.000.000 fattoriali in circa 8 MB.