Гамма-функция и факториал: вычислительные вопросы

Тема в разделе "Кухня", создана пользователем Pia, 19 окт 2008.

  1. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.709
    Симпатии:
    50
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
    кстати, Аксиомы Пеано, как пишут, в оригинале определялись начиная с 0 а не с 1.
  2. Муркенштейн Гастролёр

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    1.794
    Симпатии:
    15
    Репутация:
    2
    Адрес:
    Nowhere
    Оффлайн
    krey, drowsy, а как по мне, так в данном случае абсолютно непринципиально, какое натуральное число наименьшее.
    Ляпсус Pia, как Вы представляете себе C(r,k)? Не надо приводить цитаты из англоязычных википедий, опишите своими словами.
  3. gennah Учаcтник

    • Участник
    Рег.:
    04.10.2007
    Сообщения:
    474
    Симпатии:
    1
    Репутация:
    1
    Оффлайн
    Ох уж эти числа натуральные... В принципе, на англиццкой вики есть небольшой обзор "статуса нуля". Порой приятнее иметь нуль среди натуральных чисел, чем не иметь нуля. Порой - наоборот. :) В любом разе, дискуссия о том, является ли нуль натуральным числом, - не многим важнее программки Pia.

    krey, про Фихтенгольца я как бы пошутить пытался... В этой теме, по-моему, серьёзно говорить вообще невозможно - остаётся лишь шутить. :)
  4. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    drowsy
    Конечно, я читал файл товарища под именем GLENDON RALPH PUGH, ещё когда Вы впервые дали ссылку.
    Он просто сравнивает различные методы приближённого вычисления Гамма-функции.
    Получить точность больше, чем 32 знака он не пытался.
    Я сейчас в своей лаборатории получил точность 63 знака^^
  5. EgisLT Учаcтник

    • Участник
    Рег.:
    14.12.2007
    Сообщения:
    431
    Симпатии:
    12
    Репутация:
    0
    Оффлайн
    А как вы проверяете точность?
  6. gennah Учаcтник

    • Участник
    Рег.:
    04.10.2007
    Сообщения:
    474
    Симпатии:
    1
    Репутация:
    1
    Оффлайн
    Дабы поддержать энтузиастов и приблизить научный прорыв в деле вычисления гамма-функции (пусть даже и под названием "факториал") рискну дать сцылку на относительно свеженькую статью в SIAM Journal on Numerical Analysis:

    http://www.comlab.ox.ac.uk/people/nick.trefethen/publication/PDF/2007_122.pdf

    Ну и ждём статьи от Pia. :) Или хотя бы доклада о своих computational results, в кои, помимо безусловно важенейшего калькулятора Windows, было бы неплохо включить всякие мелочи вроде MatLab, Mathematica, Maple, библиотеки GSL, NAG и IMSL (кстати, IMSL комплексные "факториалы" считает... нельзя это так оставлять!)

    В общем, большая работа предстоит...
  7. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Вбил функцию в PowerToy Calculator. Проверил Онлайн Калькулятором Факториалов.
    Ряд был до x^16, но можно больше, точнее.
  8. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.709
    Симпатии:
    50
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
  9. Муркенштейн Гастролёр

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    1.794
    Симпатии:
    15
    Репутация:
    2
    Адрес:
    Nowhere
    Оффлайн
    Повторю вопрос:
    Pia, как Вы представляете себе C(r,k)?
    Хотелось бы увидеть ответ.
  10. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    У нас есть программа, что представил Mustitz. В принципе, позволяет находить факториалы примерно до 265 000 000. Но не в этой жизни. Такая программа найдёт все 265 000 000 факториалов вместо одного единственного. Я её скомпилировал, но пока она там найдёт 71352! не дождался.
    Может, ещё ответить, зачем вообще возводить 1+x в нецелую степень r?
    То, что Муркенштейн не может себе представить, того быть не может и всё.
  11. Муркенштейн Гастролёр

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    1.794
    Симпатии:
    15
    Репутация:
    2
    Адрес:
    Nowhere
    Оффлайн
    Ляпсус Pia, не передёргивайте. Речь не о том, могу ли я что-либо себе представить.
    C(n,k) - это количество возможностей выбрать k элементов из n-элементного множества. А что такое C(r,k)? Опишите своими словами.
  12. gennah Учаcтник

    • Участник
    Рег.:
    04.10.2007
    Сообщения:
    474
    Симпатии:
    1
    Репутация:
    1
    Оффлайн
  13. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Для меня это было последней каплей :rolleyes:
  14. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Напоролись? Ну что тогда глазки делаем?
    Да, Муркенщтейн, что мне Вас ещё считать учить?
  15. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Pia, Вы что, до сих пор не понимаете, какую бредятину написали?
    Я же сказал, сил моих больше нет :)
    Все - опять ушел :)
  16. E-not Он видел динозавров

    • Ветеран
    Рег.:
    03.10.2007
    Сообщения:
    6.730
    Симпатии:
    163
    Репутация:
    31
    Адрес:
    Москва,
    Оффлайн
    Ничего, завтра с утречка ... 15 пробежки, турничек, гантельки и силы вновь появятся ... :)
  17. E-not Он видел динозавров

    • Ветеран
    Рег.:
    03.10.2007
    Сообщения:
    6.730
    Симпатии:
    163
    Репутация:
    31
    Адрес:
    Москва,
    Оффлайн
    Можно ли описать своими словами корень из -1 ?

    Почему бы функцию C(n,k) - (это количество возможностей выбрать k элементов из n-элементного множества.) не распространить на нецелые или даже комплексные числа? Из того что мы не можем себе представить ведь не следует что этого нет... Тем более речь идет о математических построениях ...
  18. Муркенштейн Гастролёр

    • Участник
    Рег.:
    20.02.2006
    Сообщения:
    1.794
    Симпатии:
    15
    Репутация:
    2
    Адрес:
    Nowhere
    Оффлайн
    Конечно. Число, квадрат которого равен -1.

    Дык, про это Pia говорит, ему и карты в руки. Пусть попробует распространить, а мы посмеёмся послушаем.

    Ещё один туда же...
  19. Mustitz Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    30.09.2006
    Сообщения:
    3.546
    Симпатии:
    1.265
    Репутация:
    36
    Адрес:
    Киев
    Оффлайн
    Не число, а числа.
  20. gennah Учаcтник

    • Участник
    Рег.:
    04.10.2007
    Сообщения:
    474
    Симпатии:
    1
    Репутация:
    1
    Оффлайн
    Я вот что подумал, Pia. Раз уж с факториалами мы почти разобрались... да и, как оказалось, факториалы все кто ни попадя считать умеют... В общем, а не посчитать ли вам функцию Акерманна? С достойной, так сказать, точностью и для солидных, так сказать, аргументов? И не обобщить ли её на действительные числа? Думаю, проект в самый раз для вашей лаборатории.

    Куда "туда же"?
  21. gennah Учаcтник

    • Участник
    Рег.:
    04.10.2007
    Сообщения:
    474
    Симпатии:
    1
    Репутация:
    1
    Оффлайн
    Прошу простить меня за, быть может, излишне весёлое настроение, но не могу удержаться. :)

    k^n - это количество возможностей раскидать n-элементное множество на k частей. А что такое k^e? Опишите своими словами. :)
  22. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Да кто из нас бредит, интересно! В моей формуле две операции, у Вас - бесконечность.
  23. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    "Ладно. Пойдем более длинным путем. Привези мне, батюшка, цветочек аленький!"

    1. Мы имеем два разложения в ряд функции (1+x)^r
    Оба разложения суть бесконечные ряды.
    2. Вопрос - что мы хотим посчитать?
    Варианты ответа
    a. значение (1+x)^r при данных x и r. Использование данных рядов для данной задачи - это удаление гланд нетрадиционным способом. Закончили дискуссию. goto end.
    б. Конкретный биномиальный коэффициент при x^к. Назовем его поморщившись C(r,k).

    Я так понимаю, именно это и было целью Pia - продемонстрировать миру мощь программы считающей факториалы, входящие в выражение для C(r,k)
    Едем дальше.

    3. Обращаем внимание Pia на.
    а. Выражения для C(r, к) в обоих рядах тождественны друг другу. В этой связи выражение от Pia
    уже приобретает интерес :)
    Разумеется с точки зрения вычислительной разница может быть.
    б. Напоминаем, что мы считаем конкретный C(r, к) и для этого конкретного C(r, к) к имеет совершенно конкретное фиксированное значение.
    в. Выражение C(r, k) для второго ряда НЕ является бесконечным рядом
    [​IMG]

    О чем недвусмысленно указывают буковки и цифирьки (k-1) над произведением П

    Нет Pia - это всего лишь конечное произведение к сомножителей.

    Причем конечное, как Вы теперь начинаете понимать, не требует аппроксимации куском ряда, а посему точнее.

    Вот теперь мы подошли близко к вопросу что проще считать - конечное произведение, или три факториала ( или три Гамма функции )?

    Оставляем этот вопрос Pia для домашнего задания, а пока в качестве примера приведем вариант
    Считаем C( 100, 3 )
    По первому варианту (Pia) надо посчитать 100! / ( 97! * 3! ). Вперед Pia. Флаг Вам в руки и барабан на шею.
    По второму - надо посчитать 100*99*98 / 6 . И все.

    Разумеется есть еще места для обсуждения, но до тех пор пока Pia не проникнется пониманием написанного выше, обсуждать тонкости бесполезно.

    Работайте, Pia.
    В качестве бонуса читайте анекдот от Lugan'a
    http://kasparovchess.crestbook.com/viewtopic.php?pid=203840#p203840
  24. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Vladimirovich
    Чтобы посчитать (1+x)^r нужно сложить ряд C(r,k)*x^k при k идёт к бесконечности. Что Вы показываете k = 3? Или у Вас число 3 - уже бесконечность? Я показал на примере k = 60 000. Уже здесь моя формула в десятки раз быстрей.
  25. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.709
    Симпатии:
    50
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
  26. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Pia, Вы что плохо прочитали ?

    Дискуссия же шла о том что первое выражение для C(r,k) эффективнее, как Вы думаете.

    В общем случае эффективность и выбор алгоритма зависят от r и к
    Я привел лишь пример для k=3. Тут надеюсь все понятно с Вашим алгоритмом.

    Для коэффициента же при к=60 000 нужно будет найти призведение всего 60000 сомножителей.
    Причем только перемножить, без экспонент, логарифмов и пр.
    Причем результат будет точнее.

    И знаете ли Вы, сколько перемножений на ассемблере выполняется для расчета одной экспоненты?
    Логарифма?

    Преимущество Вашего алгоритма для таких значений k далеко не очевидно.
    Причем я не буду отрицать, что начиная с некоторого к считать через приближенные значения Гамма-функций возможно быстрее. Но это требует конкретного исследования, а не голословного утверждения.
  27. E-not Он видел динозавров

    • Ветеран
    Рег.:
    03.10.2007
    Сообщения:
    6.730
    Симпатии:
    163
    Репутация:
    31
    Адрес:
    Москва,
    Оффлайн
    Попробую аналогично определить C(n,k) на комплексном множестве как функцию которая представляет количество возможностей выбрать k элементов из n-элементного множества при целых k n :)

    Ну вот теперь смейтесь :)
  28. E-not Он видел динозавров

    • Ветеран
    Рег.:
    03.10.2007
    Сообщения:
    6.730
    Симпатии:
    163
    Репутация:
    31
    Адрес:
    Москва,
    Оффлайн
    Блин!! А просто одобрить, поддержать человека, который по его мнению сделал нечто стоящее тяжело, не правда ли ?...

    Даже если это само по себе и не нужно, ясно что человек отточил свое мастерство ... и наверняка найдет сейф который вскроет своей "фомкой" как бык овцу (C-Ирина) :)
  29. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.491
    Симпатии:
    3.118
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Можно ещё sin (PI ^ 100) посчитать, тоже полезное занятие :)
  30. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Vladimirovich.
    Я же сказал: примерно в 34 раза быстрее уже при k = 60000. При равной точности в 17-18 знаков. Чё Вы бабку путаете: "неочевидно, возможно...". Возьмите и посчитайте, если Вам неочевидно. Вот при 60000 произведений будет точнось 13-14 знаков при фактических 17-18-и. И вообще, как вы собираетесь посчитать подобный бесконечный ряд не приближённо?
  31. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Pia, Вы определитесь, что Вы считаете.
    Если ряд для (1+x)^r то в этом случае мне нет НИКАКОЙ необходимости считать 1 800 000 000 произведений.

    потому что я посчитав произведение например от 1 до 59 НЕ буду ЗАНОВО пересчитывать произведение от 1 до 60. А то это глупо как-то ;)
    Я просто умножу предыдущее на 60 :). И так далее. Итого ~60000 произведений для k=60000
    Где Вы только взяли цифру 1 800 000 000 и 34 раза ....

    Ряд естественно будет обрублен при некотором k, но
    1. Я его не собираюсь считать :)
    2. Число членов ряда для (1+x)^r придется считать ОДИНАКОВО для обоих вариантов, что с Гаммами, что с произведениями, поскольку ряды математически идентичны.

    P.S Если же речь идет всего лишь о расчете C(r,k), то произведение там конечно для любого данного k
  32. Alexander Заслуженный

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    12.02.2006
    Сообщения:
    3.578
    Симпатии:
    1.567
    Репутация:
    43
    Оффлайн
    Если считать число сочетаний, то есть еще треугольник Паскаля; там вообще только складывать надо. А для сумм биномиальных вероятностей - интегральная предельная теорема Муавра-Лапласа. Ну и как апофеоз и обобщение - нормальное (в смысле неплохое :) ) распределение...
  33. krey Михаил Кройтор

    • Команда форума
    Рег.:
    10.04.2006
    Сообщения:
    3.709
    Симпатии:
    50
    Репутация:
    1
    Адрес:
    Кишинев
    Оффлайн
    не смешно :( потому что верно для подмножества множества комплексных чисел:'(
    надо так определять:
    :cool:
  34. TopicStarter Overlay

    Pia Учаcтник

    • Участник
    Рег.:
    11.06.2007
    Сообщения:
    537
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Я об этом говорил в посте 183.
    k = 60000. У Вас столько же произведений/операций против считанных десятков по моей формуле.
  35. Vladimirovich Консультант

    • Ветеран
    • Заблокирован
    • Старожил
    Рег.:
    27.09.2006
    Сообщения:
    6.007
    Симпатии:
    810
    Репутация:
    31
    Нарушения:
    31
    Адрес:
    https://quantoforum.ru/
    Оффлайн
    Если Вы считаете что, то что Вы насчитали с помощью виндового калькулятора и своей программулины паскальной, становится очевидным, то это :lol:

    Например

Поделиться этой страницей