Точность подсчета факториала через формулу Стирлинга

[Sonic86]

Цитата:

Это же Гамма-функция, а она отличается от факториала: $n!=\Gamma (n+1), n! \neq \Gamma (n)$

Но Вы же сами пишете: $n!=\Gamma (n+1)$ используйте это.

[mcfly]

В википедии нашел такую формулу:

$$\Gamma(z)=\lim\limits_{n\to\infty}\frac{n!n^z}{(z+1)\dots (z+n)}=\frac{1}{z}\prod\limits_{n=1}^{\infty}\frac{\left(1+\frac{1}{n}\right)^z}{1+\frac{z}{n}}$$

Попробую подобрать кол-во итераций в вычислении произведения, чтобы был удовлетворяющий ответ.

[Sonic86]

Я Вам все-таки советую с Фихтенгольца начать

[mcfly]

Sonic86 в сообщении #418976 писал(а):

Я Вам все-таки советую с Фихтенгольца начать

Спасибо за ссылку, буду курить мануал :)

[Евгений Машеров]

Формула Стирлинга - приближённая. При этом обычно ограничиваются ещё более приближённым выражение для неё
$ n! = \sqrt{2\pi n} n^n/e^n$
пренебрегая поправками вида $(1+\frac{1}{12n}+\frac{1}{288n^2}-\frac{139}{51840n^3}+O(n^{-4}))$
При этом точного значения она не даёт никогда. Её ценность в том, что при больших n она даёт малую относительную ошибку. Но, поскольку $n!$ растёт куда быстрее $(1+\frac{1}{12n}+...)$ абсолютная ошибка очень быстро возрастает.
Для большинства приложений, в которых востребована замена факториала Стирлингом, величина факториала "сокращается" (как, скажем, при выведении нормального распределения через биномиальное), так что результат имеет не только малую относительную, но и малую абсолютную ошибку.
Если же нужно точное целочисленное значение факториала (зачем?!), то остаётся только перемножать числа непосредственно.

-- Ср мар 02, 2011 16:34:01 --

Что до предлагаемой идеи вычислять, скажем, $5.54!$ через $0.54!$ по формуле Стирлинга и приведение через $n!=n\cdot (n-1)!$, то она даст большую ошибку, чем непосредственно $5.54!$ по Стирлингу. Поскольку чем меньше аргумент, тем больше относительная ошибка Стирлинга, а большая относительная ошибка, умноженная на значение факториала, даст большую абсолютную ошибку, чем непосредтвенный расчёт по Стирлингу.
Не представляется также осмысленной идея вычислять через бесконечное произведение.
Вот некоторые алгоритмы для гамма-функции:
http://www.rskey.org/gamma.htm
http://mathworld.wolfram.com/GammaFunction.html
http://functions.wolfram.com/GammaBetaErf/Gamma/06/

[worm2]

А нет ли настолько точной быстрой формулы, чтобы можно было (теоретически) для любого натурального числа прикинуть число нулей (ну, или в какой-нибудь другой системе счисления посчитать делимость), округлить и получить точный результат?

[Sonic86]

Ну число цифр-то $\sim K \ln n! \sim K n (\ln n - 1) +C + \varepsilon _n$. Быть может погрешность $\varepsilon _n = O(n^{-1})$ не дает весомого вклада... Хотя если $\varepsilon _n = O(n^{-1})$, то $\sum \varepsilon _ n \sim \ln n$, а значит иногда (но очень редко), формула будет ошибочна

Число нулей $\sim \frac{n}{5}$, ессно.

[venco]

Sonic86 в сообщении #419572 писал(а):

Число нулей $\sim \frac{n}{5}$, ессно.

$\sim \frac n 4$, точнее $\sum\limits_{k=1}^{\infty}\left\lfloor\dfrac n {5^k}\right\rfloor$.

[Sonic86]

(Оффтоп)

да, наврал, хотел написать $\frac{n}{5-1}$

[Евгений Машеров]

Знание числа нулей $M$ поможет при округлении, если абсолютная ошибка окажется меньше, чем $10^M$
Однако число разрядов в факториале числа $N$ растёт, как $O(N \ln N)$, тогда как число нулей приблизительно равно $N/4$, то есть даже при очень малой относительной ошибке абсолютная ошибка будет расти куда быстрее, чем $10^M$
Так, $1000!$ приблизительно равно $4.02387260077093773543702433923*10^2567$, тогда как нулей в нём лишь $249$, то есть относительная ошибка должна быть меньше $10^{-2328}$, что, видимо, потребует нахождения поправочных членов порядка эдак до восьмисотого.
Ну и праздный вопрос - зачем? Зачем такие калькуляции? Если чисто спортивный результат - умножайте непосредственно. Может, даже безо всякого Шёнхаге. Длинное накопительное произведение на короткий сомножитель.

[feliks]

Можно легко вычислять через Логарифм Факториалов очень больших чисел. Относительная точность зависит от точности расчетов в компьютере.

[feliks]

Попробуйте использовать формулу ln(n!) а потом потенциировать результат.

[Евгений Машеров]

"Спасибо, кэп!"
Автор начинает с того, что применяет некий вариант этого подхода (а считать степени $n^n$ без логарифмов как-то затруднительно) и неудовлетворён нарастанием абсолютной ошибки.

[Portnov]

Ну вот как раз «количество нулей», точнее, количество знаков в десятичном разложении, вполне можно прикинуть по формуле Стирлинга. Считаем $\ln n!$ и делим на $\ln 10$.

[Sidle]

Есть еще вариант вычисления больших факториалов в Matlab :) точность можно задать самому :) хотите сказать, что matlab более 170! не вычислит? Соглашусь, однако можно пойти другим путем :) вот пример вычисления факториала 1000000 с точностью 1000 знаков в matlab:
vpa(solve('x=factorial(1000000)'),1000)