Существуют ли быстрые алгоритмы получения факториала?

[sqribner48]

Здравствуйте. Мой вопрос(ы): "Существуют ли быстрые алгоритмы получения факториала?
Если таковые существуют, то какие именно? И где об этом можно прочитать?"
Прошу дать ссылку.
На этот вопрос натолкнул опыт практически «молниеносного» вычисления факториала в 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. Просьба модераторам. Долго сомневался в какую тему разместить - вроде в программирование, или в около научный софт. Прошу модераторов поправить если что не так.

[upgrade]

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

[sqribner48]

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

[upgrade]

sqribner48 в сообщении #1126513 писал(а):

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

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

[Eimrine]

sqribner48 в сообщении #1126513 писал(а):

Подождем, может еще кто-то просветит.

http://lmgtfy.com/?q=fast+factorial+algorithm

upgrade в сообщении #1126511 писал(а):

Подозреваю - рекурсия. Очень быстрая штука.

Бред.

upgrade в сообщении #1126511 писал(а):

Еще быстрее - готовая база ответов.

Время растёт слишком явно как для кэширования

[iifat]

upgrade в сообщении #1126511 писал(а):

рекурсия. Очень быстрая штука

Почему бы благородному дону не говорить странных вещей?
Люди целые умные книги, ну, по крайней мере, статьи пишут о преобразовании рекурсии в итерацию — видимо, чтоб замедлить работу.
Что касается факториала — что-то кроме честного перемножения ничего в голову не идёт. Ну разве что хранить таблицу простых и посчитать по формуле разложения факториала на простые делители — не уверен, вдруг для больших быстрее выйдет.

[upgrade]

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

-- 27.05.2016, 17:40 --

iifat в сообщении #1126516 писал(а):

upgrade в сообщении #1126511 писал(а):

рекурсия. Очень быстрая штука

Почему бы благородному дону не говорить странных вещей?
Люди целые умные книги, ну, по крайней мере, статьи пишут о преобразовании рекурсии в итерацию — видимо, чтоб замедлить работу.

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

[Eimrine]

upgrade в сообщении #1126517 писал(а):

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

Аккумуляторная рекурсия может быть почти такой же быстрой, как и итерация, а на многоядерных машинах ещё даже быстрее, если только даный алгоритм хорошо паралелится. Но всё равно это бред, потому что в общем случае нет разницы, на какой парадигме реализовывать алгоритм - на уровне кремниевого процессора рекурсивный алгоритм всё равно развернётся в итеративный во время compile-time.

upgrade в сообщении #1126517 писал(а):

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

Кажется, умножение должно работать быстрее, чем степень и логарифмы.

[rockclimber]

Eimrine в сообщении #1126520 писал(а):

upgrade в сообщении #1126517 писал(а):

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

Кажется, умножение должно работать быстрее, чем степень и логарифмы.

Ну так и место для оптимизации тоже есть: $\lg 20 = 1 + \lg 2$
Я, правда, не пробовал. А умножение на 2 можно заменить на битовый сдвиг.
Но и погуглить самый быстрый алгоритм - тоже хорошее решение.

[arseniiv]

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

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

[rockclimber]

Eimrine в сообщении #1126515 писал(а):

upgrade в сообщении #1126511 писал(а):

Еще быстрее - готовая база ответов.

Время растёт слишком явно как для кэширования

Всего лишь как логарифм от количества хранящихся значений.

[upgrade]

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

[arseniiv]

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

[Dmitriy40]

Уж точно не рекурсия и не итерации, PARI/GP любые факториалы до $10^{16}$ вычисляет мгновенно, вот пример:

? factorial(7*10^15)
%1 = 2.2032641378037977189841339740418128347 E107875624906777043
  ***   last result computed in 0 ms.

[Eimrine]

(Оффтоп)

rockclimber в сообщении #1126530 писал(а):

умножение на 2 можно заменить на битовый сдвиг.

Луддизм 21-го столетия - соревноваться с компилятором в оптимизации.

rockclimber в сообщении #1126534 писал(а):

Eimrine в сообщении #1126515 писал(а):

Время растёт слишком явно как для кэширования

Всего лишь как логарифм от количества хранящихся значений.

Как раз это и значит, что там не кэширование, а полиномиальный алгоритм. Поправьте, если я ошибаюсь.