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

[mcfly]

Доброе время суток, товарищи математики.

Решил апгрейдить свой калькулятор (oncalc.net) добавить возможность вычисления факториала вещественных чисел. Вычислять решил при помощи формулы Стирлинга. Написал функционал, начал тестить. Проверял я следующим образом, подсчитывал факториалы целых чисел через формулу стирлинга и простым методом (1*2*...*n) и сравнивал результаты. И что у меня получилось (результаты округляю):

До факториала 17 идет ровно, а потом расхождение начинает рости:

15!
(1*2*...*15) = Ф.Стирлинга = 1307674368000

16!
(1*2*...*16) = Ф.Стирлинга = 20922789888000

17!
(1*2*...*17): 355687428096000
Ф.Стирлинга: 355687428096045

18!
(1*2*...*18): 6402373705728000
Ф.Стирлинга: 6402373705727531

.. .. ..

25!
(1*2*...*25): 15511210043330985984000000
Ф.Стирлинга: 15511210043334063846443075

А для больших результатов, больше 1000! там вообще все "страшно" :)

Формула Стирлинга реально такую погрешность дает? Есть ли более точный алгоритм подсчета факториала с вещественным аргументом?

[gris]

А разве относительная погрешность, которая только и важна, растёт?

[mcfly]

gris в сообщении #418920 писал(а):

А разве относительная погрешность, которая только и важна, растёт?

эм.. не понял, почему тут только важна относительная погрешность? Абсолютная погрешность растет и это плохо. Когда человек захочет подсчитать факториал, а ему выдаст результат гораздо меньше, чем должно быть - это разве не важно?

Когда вы считаете, например, 5! и вам возвращает результат 110 - это важно и пофиг какая это погрешность, относительная или абсолютная. Главное погрешность есть и это плохо :)

[gris]

Это, конечно, может быть важно при решении каких-то целочисленных задач, там ошибка в 1 может быть критичной, но формула Стирлинга, как и большинство других приближённых формул, обеспечивает лишь определённую относительную погрешность.

[mcfly]

gris в сообщении #418926 писал(а):

Это, конечно, может быть важно при решении каких-то целочисленных задач, там ошибка в 1 может быть критичной, но формула Стирлинга, как и большинство других приближённых формул, обеспечивает лишь определённую относительную погрешность.

То есть через формулу стирлинга факториал целых чисел считается с погрешностью, а факториал вещественных чисел считается с несущественной погрешностью? Я сравнил с результатом в винодовом калькуляторе, там расхождения:

19.65! = 847813787623647996,02308585917195 (В виндовом)
19.65! = 847813787623740168,52222585840589 (В моем)

Есть ли более точные алгоритмы подсчета факториала вещественного числа?

[Ales]

mcfly в сообщении #418929 писал(а):

факториал вещественных чисел

Гамма-функция Эйлера?

mcfly в сообщении #418929 писал(а):

Есть ли более точные алгоритмы подсчтета факториала вещественного числа?

Все нормальные люди просто перемножают числа. Это очень просто.
Из-за быстрого роста величины факториала эта операция лишена смысла для больших чисел .

Никто не использует формулу Стирлинга для вычисления факториала.
Формула Стирлинга полезна в анализе - там, где можно заменить выражение факториала на более удобное.

[mcfly]

Ales в сообщении #418934 писал(а):

Все нормальные люди просто перемножают числа. Это очень просто.

А что "все нормальные люди" используют для факториала не целого числа? Перемножение, как для целых чисел?

[Руст]

Лучше воспользуйтесь более точной формулой:

$$n!=\sqrt{2\pi n}(\frac ne)^nexp[\sum_{k=1}^m\frac{B_{2k}}{2k(2k-1)n^{2k-1}}+\theta_{m,n}\frac{B_{2m+2}}{(2m+2)(2m+1)n^{2m+1}}].$$

Здесь $|\theta_{m,n}|<1$ и наиболее точная формула получается когда $m=[\pi n+\frac 12]$ (целая часть). Если при вычислении (без $\theta$ и $m=[\pi n+0.5]$) взять ближайщее целое, то формула даст точное значение для $n$ примерно до 1500 (когда то вычислял, точное значение не помню где то 1462).

[Ales]

mcfly в сообщении #418936 писал(а):

А что "все нормальные люди" используют для факториала не целого числа? Перемножение, как для целых чисел?

Понятие факториала применяется к натуральным числам.
Что Вы имеете в виду, когда пишите "факториал не целого числа"?

-- Ср мар 02, 2011 12:25:17 --

Формула Стирлинга имеет относительную погрешность порядка $\frac 1 n$,
значит абсолютная погрешность будет порядка $(n-1)!$.

[mcfly]

Руст в сообщении #418939 писал(а):

Лучше воспользуйтесь более точной формулой:

$$n!=\sqrt{2\pi n}(\frac ne)^nexp[\sum_{k=1}^m\frac{B_{2k}}{2k(2k-1)n^{2k-1}}+\theta_{m,n}\frac{B_{2m+2}}{(2m+2)(2m+1)n^{2m+1}}].$$

Здесь $|\theta_{m,n}|<1$ и наиболее точная формула получается когда $m=[\pi n+\frac 12]$ (целая часть). Если при вычислении (без $\theta$ и $m=[\pi n+0.5]$) взять ближайщее целое, то формула даст точное значение для $n$ примерно до 1500 (когда то вычислял, точное значение не помню где то 1462).

Спасибо за конкретный ответ без "воды"! :)

[Ales]

Но судя по проделанному автором темы эксперименту, для относительно малых $n$ формула Стирлинга более точна.

[Sonic86]

mcfly
Имейте ввиду, что приведенная формула (кстати, это формула суммирования Эйлера-Маклорена, Фихтенгольц, 3-й том) верна только асимптотически, т.е. абсолютная погрешность будет стремиться к бесконечности при $n \to + \infty$

[mcfly]

Ales в сообщении #418948 писал(а):

Но судя по проделанному автором темы эксперименту, для относительно малых $n$ формула Стирлинга более точна.

Да этот подход удовлетворителен для чисел типа Int. Но мой калькулятор считает даже 25000!, а для больших чисел результат, подсчитанный при помощи формулы Стирлинга, будет неверный. Вот и решил спросить у знающих людей, самый точный метод подсчета $n!$, где $n$-вещественное число.

Верно ли такое:
Если $n! = n(n-1)!$, то мы, например, $5.54!$ сможем разложить как:

5.54! = 5.54*4.54*3.54*2.54*1.54*0.54!

Где $0.54!$ вычислить по формуле Стирлинга, так как оно малое число, то оно правильно подсчитается.

[Sonic86]

mcfly писал(а):

Да этот подход удовлетворителен для чисел типа Int. Но мой калькулятор считает даже $25000!$, а для больших чисел результат, подсчитанный при помощи формулы Стирлинга, будет неверный. Вот и решил спросить у знающих людей, самый точный метод подсчета $n!$, где $n$-вещественное число.

Самый точный - это все-таки по определению.

mcfly писал(а):

Верно ли такое:
Если $n! = n(n-1)!$, то мы, например, $5.54!$ сможем разложить как:

5.54! = 5.54*4.54*3.54*2.54*1.54*0.54!

Где $0.54!$ вычислить по формуле Стирлинга, так как оно малое число, то оно правильно подсчитается.

Да, только для нецелых чисел факториал обозначается функцией $\Gamma$. О ней Вы также можете прочесть в Фихтенгольце.

[mcfly]

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

Да, только для нецелых чисел факториал обозначается функцией $\Gamma$. О ней Вы также можете прочесть в Фихтенгольце.

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