Si può sapere quanto è grande un fattoriale sarebbe prima di calcolare esso?
-
12-09-2019 - |
Domanda
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?
Soluzione
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;
Altri suggerimenti
È 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.
approssimazione di Stirling dà un'approssimazione delle dimensioni di n!
Si veda la pagina del Wikipedia per la derivazione.
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
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).
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.