# Is there any better way to find n! without just multiplying all the numbers till n? [duplicate]

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?

• It's $((n+x)!)/((n-1)!)$ – Crostul Feb 10 '16 at 12:20
• ${n+x \choose n-1}(x+1)$ is also another one. – Valentin Feb 10 '16 at 12:22
• I do not think so. Any method will comprise of you multiplying something with something else. – SinTan1729 Feb 10 '16 at 12:24
• 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? – Farhan Fuad Feb 10 '16 at 12:26
• So there is no formula invented like n(n+1)/2 for this problem yet? that's odd – Farhan Fuad Feb 10 '16 at 12:30

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.

$$n(n+1)(n+2)(n+3)\cdot\dots\cdot(n+x)=$$ $$(n+0)(n+1)(n+2)(n+3)\cdot\dots\cdot(n+x)=$$ $$\prod_{m=0}^{x}(n+m)=n(n+1)_x=\frac{(n+x)!}{(n-1)!}$$

With $(a)_n$ is the Pochhammer symbol (rising factorial).

• I actually wanted to avoid factorial. Because if someone tells you to find the factorial of 187, it is really time wasting to just multiply all those numbers. So I thought tgere might be a better way. I think I should edit the question – Farhan Fuad Feb 10 '16 at 12:33
• @Farhan Fuad: See here for better ways luschny.de/math/factorial/FastFactorialFunctions.htm, this is especially needed for larger values like $1000000!$ – gammatester Feb 10 '16 at 12:39