Факторный алгоритм более эффективен, чем наивное умножение

Я знаю, как кодировать для факториалов, используя итеративные и рекурсивные (например, n * factorial(n-1)например). Я прочитал в учебнике (без каких-либо дальнейших объяснений), что существует еще более эффективный способ кодирования для факториалов, разделив их пополам рекурсивно.

Я понимаю, почему это может иметь место. Однако я хотел попробовать написать код самостоятельно, и я не думаю, что знаю, с чего начать. Друг предложил мне сначала написать базовые случаи. и я думал об использовании массивов, чтобы я мог отслеживать числа ... но я действительно не вижу никакого выхода для разработки такого кода.

Какие методы я должен исследовать?

Лучший известный алгоритм состоит в том, чтобы выразить факториал как произведение простых степеней. Можно быстро определить простые числа, а также правильную мощность для каждого простого числа, используя метод сита. Вычисление каждой мощности может быть эффективно выполнено с использованием повторного возведения в квадрат, а затем коэффициенты умножаются вместе. Это было описано Питером Б. Borwein, О сложности вычисления факториалов , журнал алгоритмов 6 376-380, 1985. ( PDF ) Короче говоря, можно вычислить за время O ( n ( log n ) 3 log log n ) по сравнению с Ω ( $n!$$O(n(\log n)^3\log \log n)$ время, необходимое при использовании определения.$\Omega(n^2 \log n)$

Возможно, учебник имел в виду метод «разделяй и властвуй». Можно уменьшить умножения, используя регулярный образец продукта.$n-1$

Пусть обозначают 1 ⋅ 3 ⋅ 5 ⋯ ( 2 п - 1 ) в качестве удобного обозначения. Переставь множители ( 2 n ) ! = 1 ⋅ 2 ⋅ 3 ⋯ ( 2 n ) при ( 2 n ) ! = п ! ⋅ 2 н ⋅ 3 ⋅ 5 ⋅ 7 ⋯ ( 2 н $n?$$1 \cdot 3 \cdot 5 \dotsm (2n-1)$$(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ Теперь предположим, что n = 2 k для некоторого целого числа k > 0 . (Это полезное предположение, чтобы избежать осложнений в следующем обсуждении, и эту идею можно распространить на общее п .) Тогда ( 2 k ) ! = ( 2 k - 1 ) ! 2 2 k - 1 ( 2 k - 1 ) ? и расширив это повторение, ( 2 k ) !

$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$ $n = 2^k$$k>0$$n$$(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ Вычислительный( 2 к - 1 ) $$(2^k)! = \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$ $(2^{k-1})?$$(k-2) + 2^{k-1} - 2$$2$$2^k-2$$2$$2^k-1$

$n?$

def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

Даже этот код первого прохода улучшает тривиальный

f = 1; (1..32768).map{ |i| f *= i }; print f

примерно на 20% в моем тестировании.

Если немного поработать, это можно еще улучшить, также устраняя требование $n$ быть силой $2$(см. обширное обсуждение ).

Имейте в виду, что функция факториала растет настолько быстро, что вам понадобятся целые числа произвольного размера, чтобы получить какую-либо выгоду от более эффективных методов, чем наивный подход. Факториал 21 уже слишком велик для 64-битной unsigned long long int.

Насколько я знаю, нет алгоритма для вычисления $n!$ (факториал $n$) что быстрее, чем делать умножения.

However, the order in which you do the multiplications matter. Multiplication on a machine integer is a basic operation that takes the same time no matter what the value of the integer is. But for arbitrary-sized integers, the time it takes to multiply a and b depends on the size of a and b: a naive algorithm operates in time $\Theta(|a| \cdot |b|)$ (where $|x|$ is the number of digits of $x$ — in whatever base you like, as the result is the same up to a multiplicative constant). There are faster multiplication algorithms, but there is an obvious lower bound of $\Omega(|a| + |b|)$ since multiplication has to at least read all the digits. All known multiplication algorithms grow faster than linearly in $\max(|a|,|b|)$.

Armed with this background, the Wikipedia article should make sense.

Since the complexity of multiplications depend on the size of the integers that are being multiplied, you can save time by arranging multiplications in an order that keeps the numbers being multiplied small. It works out better if you arrange for the numbers to be of roughly the same size. The “division in half” that your textbook refers to consists of the following divide-and-conquer approach to multiply a (multi)set of integers:

1. Arrange the numbers to be multiplied (initially, all the integers from $1$ to $n$) in two sets whose product is roughly the same size. This is a lot less expensive than doing the multiplication: $|a \cdot b| \approx |a| + |b|$ (one machine addition).
2. Apply the algorithm recursively on each of the two subsets.
3. Multiply the two intermediate results.

See the GMP manual for more specifics.

There are even faster methods that not only rearrange the factors $1$ to $n$ but split the numbers by decomposing them into their prime factorization and rearranging the resulting very long product of mostly-small integers. I'll just cite the references from the Wikipedia article: “On the Complexity of Calculating Factorials” by Peter Borwein and implementations by Peter Luschny.

¹ _{There are faster ways of computing approximations of $n!$, but that's not computing the factorial any more, it's computing an approximation of it.}

Since the factorial function grows so fast, your computer can only store $n!$ for relatively small $n$. For example, a double can store values up to $171!$. So if you want a really fast algorithm for computing $n!$, just use a table of size $171$.

The question becomes more interesting if you're interested in $\log(n!)$ or in the $\Gamma$ function (or in $\log \Gamma$). In all these cases (including $n!$), I don't really understand the comment in your textbook.

As an aside, your iterative and recursive algorithms are equivalent (up to floating point errors), since you are using tail recursion.