Factorial algorithm more efficient than naive multiplication

Question Detail: 

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further explanations) that there is an even more efficient way of coding for factorials by dividing them in half recursively.

I understand why that may be the case. However I wanted to try coding it on my own, and I don't think I know where to start though. A friend suggested I write base cases first. and I was thinking of using arrays so that I can keep track of the numbers... but I really can't see any way out to designing such a code.

What kind of techniques should I be researching?

Asked By : user65165

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14456

Answered By : András Salamon

The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the Complexity of Calculating Factorials, Journal of Algorithms 6 376–380, 1985. (PDF) In short, $n!$ can be computed in $O(n(\log n)^3\log \log n)$ time, compared to the $\Omega(n^2 \log n)$ time required when using the definition.

What the textbook perhaps meant was the divide-and-conquer method. One can reduce the $n-1$ multiplications by using the regular pattern of the product.

Let $n?$ denote $1 \cdot 3 \cdot 5 \dotsm (2n-1)$ as a convenient notation. Rearrange the factors of $(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ as $$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$ Now suppose $n = 2^k$ for some integer $k>0$. (This is a useful assumption to avoid complications in the following discussion, and the idea can be extended to general $n$.) Then $(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ and by expanding this recurrence, $$(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)?.$$ Computing $(2^{k-1})?$ and multiplying the partial products at each stage takes $(k-2) + 2^{k-1} - 2$ multiplications. This is an improvement of a factor of nearly $2$ from $2^k-2$ multiplications just using the definition. Some additional operations are required to compute the power of $2$, but in binary arithmetic this can be done cheaply (depending on what precisely is required, it may just require adding a suffix of $2^k-1$ zeroes).

The following Ruby code implements a simplified version of this. This does not avoid recomputing $n?$ even where it could do so:

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) 

Even this first-pass code improves on the trivial

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

by about 20% in my testing.

With a bit of work, this can be improved further, also removing the requirement that $n$ be a power of $2$ (see the extensive discussion).