2
$\begingroup$

I was solving some permutation, combination problems where we know that we are to use factorial. So I was thinking if there was any shorter way, maybe a formula, than multiplying all the numbers till $n$ to find $n$!

I know how to add series like $1+2+3+4+…+n$ which is $\frac{n(n+1)}{2}$ but I didn't find much on how to multiply. So... how to do it then?

$\endgroup$
11
  • 1
    $\begingroup$ It's $((n+x)!)/((n-1)!)$ $\endgroup$
    – Crostul
    Feb 10, 2016 at 12:20
  • $\begingroup$ ${n+x \choose n-1}(x+1)$ is also another one. $\endgroup$ Feb 10, 2016 at 12:22
  • $\begingroup$ I do not think so. Any method will comprise of you multiplying something with something else. $\endgroup$ Feb 10, 2016 at 12:24
  • $\begingroup$ I mean what if you are asked the answer of "194!" Is there any alternative way to fond out the ans without just multiplying from 1 to 194? $\endgroup$ Feb 10, 2016 at 12:26
  • $\begingroup$ So there is no formula invented like n(n+1)/2 for this problem yet? that's odd $\endgroup$ Feb 10, 2016 at 12:30

1 Answer 1

0
$\begingroup$

After your editing of the original question:

You will not find an easy formula for the exact evaluation of factorials, except using $n! = \Gamma(n+1)$. If you want to compute faster than just multiply the numbers, use e.g. the prime power table approch.

A basic fast algorithm is described in P.B. Borwein, On the complexity of calculating factorials, Journal of Algorithms, Vol.6, pp. 376-380, 1985. Available as http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P29.pdf

Here the four steps of Borwein's algorithm for $n!$:

  1. Construct the prime table $2 \le p_k \le n\;$ (e.g. using a sieve method)

  2. Compute the exponents of the $p_k$ in $n!\;$ (e.g. Legendre's formula)

  3. Compute $O(\log n)$ numbers $\alpha_i$ (for details see the paper)

  4. Compute $n! = \prod \alpha_i$

For actual implementations see e.g. the mentioned FastFactorial Functions page.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .