Быстрые алгоритмы вычисления факториала

Я нашел эту страницу, описывая ряд алгоритмов вычисления факториала. К сожалению, объяснения являются краткими, и я не чувствую, что просеиваю линию после строки исходного кода, чтобы понять основные принципы, лежащие в основе алгоритмов.

Может ли кто-нибудь указать мне более подробное описание этих (или других быстрых) алгоритмов для вычисления факториала?

Изменить: Эта страница описывает метод простой факторизации, метод, общий для всех наиболее эффективных факториальные алгоритмы. Он также содержит хороший код примера в Python. Автор ссылается на описание бинарного разбиения и ссылается на статью в "Журнале алгоритмов" ( "Об сложности вычислений факториалов" ), которая выглядит многообещающей, если бы я мог только взять его в руки.

Ответ 1

Ознакомьтесь с этой статьей (PDF-ссылка) от Ричарда Фатемана. Образцы кода находятся в Lisp, но, в любом случае, большая часть тайны сводится к минимизации числа вычислений bignum (произвольной точности), которые вы должны выполнить.

Естественно, если вам не нужно/иметь bignums, это тривиально; либо таблица поиска, либо простой цикл будут в порядке.

EDIT:. Если вы можете использовать приблизительный ответ, вы можете либо вычислить логарифм факториала напрямую, суммируя log(k) для k = 2 ... n, либо используя почтенный приближение Стирлинга. Вы хотите работать с логарифмом, где это возможно, чтобы избежать переполнения; в частности, наивное применение приближения Стирлинга будет переполняться во многих местах, где это не обязательно.

Ответ 2

Существует и другой метод. Этот метод подробно описан здесь, который уменьшает количество умножений за небольшую добавку и вычитание. Вероятно, вам нужен первый показанный метод, и второй показанный метод интересен, если вы его понимаете.