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

StackOverflow https://stackoverflow.com/questions/1113167

Вопрос

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

Это было полезно?

Решение

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

logn!

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

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

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

  return result;

Другие советы

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

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

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

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

alt text

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

это было бы 

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

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

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

Там написано н!~= sqrt(2*Пип)(н/д)^n.Чтобы получить количество цифр, возьмите 1+log(n!)/log(10).

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top