2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:16 


13/05/14
476
Здравствуйте. Мой вопрос(ы): "Существуют ли быстрые алгоритмы получения факториала?
Если таковые существуют, то какие именно? И где об этом можно прочитать?"
Прошу дать ссылку.
На этот вопрос натолкнул опыт практически «молниеносного» вычисления факториала в Wolfram Mathematika. Ниже привожу пример.
Код:
Timing[Factorial[10]]
{0. Second,3628800}
Timing[Factorial[100];]
{0. Second,Null}
Timing[Factorial[1000];]
{0. Second,Null}
Timing[Factorial[10000];]
{0.015 Second,Null}
Timing[Factorial[50000];]
{0.125 Second,Null}
Timing[Factorial[100000];]
{0.329 Second,Null}
Timing[Factorial[200000];]
{0.953 Second,Null}
Timing[Factorial[300000];]
{1.609 Second,Null}
Timing[Factorial[400000];]
{2.36 Second,Null}
Timing[Factorial[1000000];]
{8.141 Second,Null}

Получается, что для любого $n \leqslant 1000$ факториал вычисляется за 0 сек?
Факториал $n = 10000$ вычисляется за 0,015сек, факториал $n = 100000$ - за 0,329сек, а факториал $n = 1000000$ - за 8,141сек. (При этом естественно сами значения факториалов – огромные числа, все цифры которых невозможно даже увидеть).
Интересно, а какой алгоритм вычисления факториала используется в Mathematika?
P.S. Просьба модераторам. Долго сомневался в какую тему разместить - вроде в программирование, или в около научный софт. Прошу модераторов поправить если что не так.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:19 


07/08/14
4231
Подозреваю - рекурсия. Очень быстрая штука.
Еще быстрее - готовая база ответов.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:25 


13/05/14
476
upgrade
Конечно Вам спасибо за ответ. Но мне хотелось бы точно знать. Ведь даже для рекурсии это-ж какую прорву операций надо выполнить, что рассчитать хотя бы факториал $100000$! :-(
Что-то тут не так. Подождем, может еще кто-то просветит. :idea:

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:27 


07/08/14
4231
sqribner48 в сообщении #1126513 писал(а):
upgrade
Конечно Вам спасибо за ответ. Но мне хотелось бы точно знать. Ведь даже для рекурсии это-ж какую прорву операций надо выполнить, что рассчитать хотя бы факториал $100000$! :-(
Что-то тут не так. Подождем, может еще кто-то просветит. :idea:

Какую прорву. Сто тысяч умножений - это не прорва, лишь бы памяти хватило.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:32 
Аватара пользователя


18/06/12

499
планета Земля
sqribner48 в сообщении #1126513 писал(а):
Подождем, может еще кто-то просветит. :idea:
http://lmgtfy.com/?q=fast+factorial+algorithm


upgrade в сообщении #1126511 писал(а):
Подозреваю - рекурсия. Очень быстрая штука.
Бред.

upgrade в сообщении #1126511 писал(а):
Еще быстрее - готовая база ответов.
Время растёт слишком явно как для кэширования

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:37 
Заслуженный участник


16/02/13
4105
Владивосток
upgrade в сообщении #1126511 писал(а):
рекурсия. Очень быстрая штука
Почему бы благородному дону не говорить странных вещей?
Люди целые умные книги, ну, по крайней мере, статьи пишут о преобразовании рекурсии в итерацию — видимо, чтоб замедлить работу.
Что касается факториала — что-то кроме честного перемножения ничего в голову не идёт. Ну разве что хранить таблицу простых и посчитать по формуле разложения факториала на простые делители — не уверен, вдруг для больших быстрее выйдет.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:38 


07/08/14
4231
Так нельзя?
$\Lg abcd...=10^{\lg a+\lg b + \lg c+...}$

-- 27.05.2016, 17:40 --

iifat в сообщении #1126516 писал(а):
upgrade в сообщении #1126511 писал(а):
рекурсия. Очень быстрая штука
Почему бы благородному дону не говорить странных вещей?
Люди целые умные книги, ну, по крайней мере, статьи пишут о преобразовании рекурсии в итерацию — видимо, чтоб замедлить работу.

Тут я извиняюсь, все верно - итерация.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 17:51 
Аватара пользователя


18/06/12

499
планета Земля
upgrade в сообщении #1126517 писал(а):
Тут я извиняюсь, все верно - итерация.
Аккумуляторная рекурсия может быть почти такой же быстрой, как и итерация, а на многоядерных машинах ещё даже быстрее, если только даный алгоритм хорошо паралелится. Но всё равно это бред, потому что в общем случае нет разницы, на какой парадигме реализовывать алгоритм - на уровне кремниевого процессора рекурсивный алгоритм всё равно развернётся в итеративный во время compile-time.

upgrade в сообщении #1126517 писал(а):
Так нельзя?
$\Lg abcd...=10^{\lg a+\lg b + \lg c+...}$
Кажется, умножение должно работать быстрее, чем степень и логарифмы.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 18:51 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Eimrine в сообщении #1126520 писал(а):
upgrade в сообщении #1126517 писал(а):
Так нельзя?
$\Lg abcd...=10^{\lg a+\lg b + \lg c+...}$
Кажется, умножение должно работать быстрее, чем степень и логарифмы.
Ну так и место для оптимизации тоже есть: $\lg 20 = 1 + \lg 2$
Я, правда, не пробовал. А умножение на 2 можно заменить на битовый сдвиг.
Но и погуглить самый быстрый алгоритм - тоже хорошее решение.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 18:52 
Заслуженный участник


27/04/09
28128
Выше, я уверен, имелась в виду целочисленная длинная арифметика. Возня с логарифмами там ни к чему хорошему не приведёт.

P. S. Так и есть.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 19:03 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Eimrine в сообщении #1126515 писал(а):
upgrade в сообщении #1126511 писал(а):
Еще быстрее - готовая база ответов.
Время растёт слишком явно как для кэширования
Всего лишь как логарифм от количества хранящихся значений.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 19:06 


07/08/14
4231
Видимо имеется ввиду время считывания из памяти точного значения $10^{2000}$ если это вообще возможно

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 19:11 
Заслуженный участник


27/04/09
28128
У Mathematica есть часть справки, посвящённая реализации. Может, там и про факториал написано.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 19:14 
Заслуженный участник


20/08/14
11063
Россия, Москва
Уж точно не рекурсия и не итерации, PARI/GP любые факториалы до $10^{16}$ вычисляет мгновенно, вот пример:
Код:
? factorial(7*10^15)
%1 = 2.2032641378037977189841339740418128347 E107875624906777043
  ***   last result computed in 0 ms.

 Профиль  
                  
 
 Re: Существуют ли быстрые алгоритмы получения факториала?
Сообщение27.05.2016, 19:22 
Аватара пользователя


18/06/12

499
планета Земля

(Оффтоп)

rockclimber в сообщении #1126530 писал(а):
умножение на 2 можно заменить на битовый сдвиг.
Луддизм 21-го столетия - соревноваться с компилятором в оптимизации.


rockclimber в сообщении #1126534 писал(а):
Eimrine в сообщении #1126515 писал(а):
Время растёт слишком явно как для кэширования
Всего лишь как логарифм от количества хранящихся значений.
Как раз это и значит, что там не кэширование, а полиномиальный алгоритм. Поправьте, если я ошибаюсь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group