Peut-on savoir comment une grande factoriel serait avant le calculer?

Question

J'utilise GMP pour calculer très grandes factorielles (par exemple 234234!). Est-il possible de savoir, avant que l'on fait le calcul, combien de chiffres le résultat (ou pourraient) être?

Answer 1

logarithme du factoriel peut être utilisé pour calculer le nombre de chiffres que le nombre factoriel prendra:

Ceci peut être facilement traduit à une forme algorithmique:

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

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

  return result;

Answer 2

Vous pouvez transformer approximation de Stirling en utilisant la formule mathématique logarithmique simple pour vous obtenir le numéro de chiffres:

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

math float matériel suffit pour cela, ce qui le rend rapide comme l'éclair.

Answer 3

approximation de Stirling donne une approximation de la taille de n!

Voir la page Wikipédia de la dérivation.

Answer 4

il serait

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

voir la rubrique "taux de croissance" @ http://en.wikipedia.org/wiki/Factorial Procédé Srinivasa Ramanujan

Answer 5

Oui, voir approximation Stirling

Il dit n! ~ = Sqrt (2 * Pi n) (n / e) ^ n. Pour obtenir le nombre de chiffres, prendre 1 + log (n!) / Log (10).

Answer 6

Et bien sur les quatre personnes ont mentionné Stirling alors ... une autre option est une LUT mémoriser le nombre de chiffres pour chacun des premiers N factorielles. En supposant que 4 octets pour le nombre entier et 4 octets pour le nombre de chiffres, vous pouvez stocker les premiers 1.000.000 factorielles dans 8MB autour.