Можно ли узнать, насколько большим будет факториал, прежде чем его вычислять?

Question

Я использую GMP для расчета очень больших факториалов (например, 234234!). Есть ли какой-нибудь способ узнать, до какого вычисления будет сколько цифр будет (или может быть) результат?

Answer 1

Вы можете преобразовать аппроксимацию Стирлинга формулу, используя простую логарифмическую математику, чтобы получить количество цифр:

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

Для этого достаточно математики с плавающей запятой, что делает его молниеносным.

Answer 2

Логарифм факториала можно использовать для вычисления количества цифр, которое примет число факториала:

Это можно легко перевести в алгоритмическую форму:

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

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

  return result;

Answer 3

Приближение Стирлинга дает приближение размера n!

См. Страницу Википедии для деривации.

Answer 4

это будет

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

см. Тему "Темпы роста" @ http://en.wikipedia.org/wiki/Factorial Шриниваса Рамануджан метод

Answer 5

Около четырех человек упомянули о Стирлинге, так что ... другой вариант - это LUT, хранящий количество цифр для каждого из первых N факториалов. Предполагая 4 байта для целого числа и 4 байта для количества цифр, вы можете хранить первые 1 000 000 факториалов примерно в 8 МБ.

Answer 6

Да, см. Приближение Стирлинга

Это говорит п! ~ = sqrt (2 * Pi n) (n / e) ^ n. Чтобы получить количество цифр, возьмите 1 + log (n!) / Log (10).