pode-se saber o quão grande esquema fatorial seria antes de calcular isso?

Question

Eu estou usando GMP para calcular muito grandes fatoriais (por exemplo, 234234!). Existe alguma maneira de saber, antes que se faz o cálculo, quantos dígitos o resultado será (ou pode) ser?

Answer 1

O logaritmo da factorial pode ser usado para calcular o número de dígitos que o número factorial terá:

Isto pode ser facilmente traduzida para uma forma algorítmica:

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

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

  return result;

Answer 2

Você pode transformar Stirling usando matemática logarítmica simples para que você obtenha o 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ática Hardware flutuador é suficiente para isso, o que o torna muito rápido.

Answer 3

Aproximação de Stirling dá uma aproximação do tamanho do n!

Veja a página do Wikipedia para a derivação.

Answer 4

seria

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

consulte o tópico "taxa de crescimento" @ http://en.wikipedia.org/wiki/Factorial método Srinivasa Ramanujan

Answer 5

Sim, veja Stirling aproximação

Ele diz que n! ~ = Sqrt (2 * pi n) (n / e) ^ n. Para obter o número de dígitos, tome 1 + log (n!) / Log (10).

Answer 6

Bem cerca de quatro pessoas mencionaram Stirling então ... outra opção é um LUT armazenar o número de dígitos para cada um dos primeiros fatoriais N. Assumindo 4 bytes para o número inteiro e 4 bytes para o número de dígitos, você pode armazenar os primeiros 1.000.000 fatoriais em torno de 8MB.