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

Question

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

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

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

Answer 1

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

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

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

Answer 2

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