| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > агоритм n! |
| Автор: valdoo 28.10.2005, 18:02 |
| Помогите найти ефективмый алгоритм подсчота очень больших факториалов. заранее спасибо |
| Автор: podval 28.10.2005, 19:01 | ||
По теме, но не ответ на поставленный вопрос.  В советском калькуляторе "Электроника МК-35", видимо, был очень эффективный алгоритм. Считался практически мгновенно.
http://calculus.narod.ru/mircal/history/calc_hi.htm Вопрос - как именно? |
| Автор: esperant0 28.10.2005, 20:44 |
Может быть используя приближение Стирлинга  |
| Автор: yaja 28.10.2005, 21:13 | ||
НЕт, поскольку она имеет только теоретический интерес, там сходимость очень медленная  |
| Автор: esperant0 28.10.2005, 23:11 |
| В относительной ошибке - сходимость очень быстрая. |
| Автор: jxr 28.10.2005, 23:20 |
| Создай свой модул (class C++). Например , что бы работать с числами по 100 цирфам 0...000 ---- 9...999 (100 цифр ) Операции: +,-,* ... Входяшие и выхожяшие будет STRING тип !!! думаете может не правилно ...  |
| Автор: valdoo 29.10.2005, 13:05 |
| приближение Стирлинга мне неподходит. мне нужен точный пезультат. С длинной цыфр тоже проблем нет. единственная проблема заключается в том что подщёты праисходят очень медленно. |
| Автор: Stream 29.10.2005, 14:33 |
А если воспользоваться формулой Стирлинга и применить к ней логарифм по основанию 10?  |
| Автор: yaja 31.10.2005, 21:02 |
| Что-то я подумал и пришел к выводу, что факториал никак не посчитать, кроме n! = 1 * 2 * 3... * n Просто для большинства чисел, его факториал не влезет ни в одну из переменных, поэтому пользуются длинной арифметикой. Дык может существует способ, позволяющий минимизировать чило действий с длинными числами. И именно это спрашивает автор?? Мне сложно представить функцию, равную n! и позволяющую бысто высчитывать свои значени. Собственно мне такая функция известна, но имхо проще перемножить n - 1 чисел n! = Г(n + 1); Г(s) = интеграл от 0 до + бесконечности ((x^(s - 1)) * exp(-x) * dx) - гамма функция Эйлера (формула Стирлинга выводится из ней) |
| Автор: esperant0 1.11.2005, 21:04 |
| Если уж на то пошло, то есть бесканечное кол-во ф-й дающих факториал.\ Формулу Стирлинга нам доказали в школе, разумеется без Гамма и Бетта ф-й |
| Автор: Akina 1.11.2005, 21:33 | ||
каков верхний порог основания? |
| Автор: yaja 1.11.2005, 21:34 | ||
Вывод формулы Стирлинга без функций Эйлера возможен, но он очень искусственный и не имеет теоретического интереса. А зная функцию Эйлера, формула Стирлинга получается буквально за одну строчку |
| Автор: esperant0 1.11.2005, 21:55 | ||||
Термин исскуственное док-во плохо определен, но я с Вами не согласен |
| Автор: yaja 1.11.2005, 22:13 | ||
ээ ну мы уже при доказательстве знали формулу Стирлинга (как бы её из потолка взяли). Совсем непонятно кому она пришла в голову(это я шучу ) и как? А глядя на функции Эйлера немного все проясняется |
| Автор: Guest 2.11.2005, 13:59 | ||||
Мне нужны факториалы ~1.000.000 и больше. Пришлось всё делать попростому n!=1*2*...*(n-1)*n Занимает мноооого времени |
| Автор: valdoo 2.11.2005, 14:02 | ||||||
забыл прилогится |
| Автор: yaja 2.11.2005, 15:09 | ||
Подсчет таких чисел по любому будет занимать много времени |
| Автор: neutrino 2.11.2005, 19:11 |
| Знаете задачу о том как найти 4-ю цифру числа 23! ??? Может по такой логике можно сократить количество умножений... |
| Автор: SoWa 3.11.2005, 19:46 |
| Если пишешь на Дельфах, то в DRKB есть модуль для работы с ОЧЕНЬ большими числами, посмотри, как там реализовано. |