Is there a quicker way to calculate factorials?

[Aladin]

Hello.

Do anyone know the shortcut or trick of taking factorial directly?
for example : 9! = 9*8*7*6*5*4*3*2*1.
it is very time consuming method to multiply all these terms to get answer.
please tell me easy mathod.
thank you

 

[Data]

In what context? Do you mean that you want to write the fastest algorithm possible in some program that you're doing? There isn't a "simpler" formula as far as I know.

If you have a program that does integrals and you're too lazy to code a loop, then you can use that n! = \Gamma(n+1) = \int_0^\infty t^n e^{-t} dt (or, if you're really bored, you can use integration by parts to do that integral in your head when you want to calculate factorials. That's strictly harder than just multiplying the numbers though!). Of course, all of the common software packages that do integrals also have a built in factorial function (in maple you just use n!, and in mathematica it's Factorial[n]).

If you want to code something to calculate factorials, then just use a loop, or recursion if you want to be more exciting! The mathworld page has other formulas, but I don't consider any of them simpler (read: none of them require less computation).

I suggest avoiding arithmetic whenever possible, as most problems can be made arbitrarily computationally difficult by choosing sufficiently inconvenient numbers

 

[uart]

Hello.

Do anyone know the shortcut or trick of taking factorial directly?
for example : 9! = 9*8*7*6*5*4*3*2*1.
thank you

Here's a shortcut for you, just drop the "*1",
for example : 9! = 9*8*7*6*5*4*3*2.

BTW, yes this was meant as a joke. :p

 

[shmoe]

If you have a program that does integrals and you're too lazy to code a loop, then you can use that n! = \Gamma(n+1) = \int_0^\infty t^n e^{-t} dt (or, if you're really bored, you can use integration by parts to do that integral in your head when you want to calculate factorials. That's strictly harder than just multiplying the numbers though!).

Integration by parts will just lead you back to n! if you are differentiating the t^n and integrating e^(-t). What did you have in mind for 'by parts' here (even if not efficient)? If you mean to approximate by a finite interval, you will then need some way of caclulating exp(-x) by hand for x larger than I'd like!



http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Has many different algorithms (and code for them) as well as approximations. I don't know what would be best to use by hand, I'd lean towards breaking it up into smaller products that I "know" off hand or are "easy" over directly multiplying in some arbitrary order.

 

[Data]

Integration by parts will just lead you back to n! if you are differentiating the t^n and integrating e^(-t).

That is what I meant (ie. you can choose that to be your definition and do it that way if you're bored - it's strictly harder because you still have to do all of the multiplication, and you also have to differentiate and integrate)! I wasn't being particularly serious

That page is pretty interesting. I definitely should have mentioned the Stirling approximation, at least!

 

[HallsofIvy]

There is no "shortcut" way of calculating n! (Before uart got in his jab, I was tempted to say "use a calculator".).

However, in more complicated, for example, calculating the Permuation of n things, taken m at at time, \frac{n!}{m!} with m< n, you can do a lot of cancelling: every factor from m down to 1 cancels:
\frac{n!}{m!}= n(n-1)(n-1)\cdot\cdot\cdot (m+1)
With the binomial coefficient, \frac{n!}{i!(n-i)!}, you can probably do a lot more cancelling.

 

[chroot]

I'm sure you could find a factorial table on the web somewhere. (Like http://membres.lycos.fr/rsirdey/facttabl.htm) Then you can just look up the answer on the table.

Or, if you're bored, make your own table. Each additional entry in the table requires just a single additional multiplication, after all, so it should proceed rather quickly.

- Warren

 

[buddyholly9999]

HOLY MOLY! would you check out that table...dang...

my calculator only calculates up to 69! ...so using a calculator has
it's limits...

 

[chroot]

My computer took a tiny fraction of a second to calculate the factorial of 1,000:

402387260077093773543702433923003985719374864210714632543799910429938512398629\
020592044208486969404800479988610197196058631666872994808558901323829669944590\
997424504087073759918823627727188732519779505950995276120874975462497043601418\
278094646496291056393887437886487337119181045825783647849977012476632889835955\
735432513185323958463075557409114262417474349347553428646576611667797396668820\
291207379143853719588249808126867838374559731746136085379534524221586593201928\
090878297308431392844403281231558611036976801357304216168747609675871348312025\
478589320767169132448426236131412508780208000261683151027341827977704784635868\
170164365024153691398281264810213092761244896359928705114964975419909342221566\
832572080821333186116811553615836546984046708975602900950537616475847728421889\
679646244945160765353408198901385442487984959953319101723355556602139450399736\
280750137837615307127761926849034352625200015888535147331611702103968175921510\
907788019393178114194545257223865541461062892187960223838971476088506276862967\
146674697562911234082439208160153780889893964518263243671616762179168909779911\
903754031274622289988005195444414282012187361745992642956581746628302955570299\
024324153181617210465832036786906117260158783520751516284225540265170483304226\
143974286933061690897968482590125458327168226458066526769958652682272807075781\
391858178889652208164348344825993266043367660176999612831860788386150279465955\
131156552036093988180612138558600301435694527224206344631797460594682573103790\
084024432438465657245014402821885252470935190620929023136493273497565513958720\
559654228749774011413346962715422845862377387538230483865688976461927383814900\
140767310446640259899490222221765904339901886018566526485061799702356193897017\
860040811889729918311021171229845901641921068884387121855646124960798722908519\
296819372388642614839657382291123125024186649353143970137428531926649875337218\
940694281434118520158014123344828015051399694290153483077644569099073152433278\
288269864602789864321139083506217095002597389863554277196742822248757586765752\
344220207573630569498825087968928162753848863396909959826280956121450994871701\
244516461260379029309120889086942028510640182154399457156805941872748998094254\
742173582401063677404595741785160829230135358081840096996372524230560855903700\
624271243416909004153690105933983835777939410970027753472000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000

The factorial of 100,000 took only about a second, but the number is far too long to post here (on the order of 40,000 digits).

- Warren

 

[Alkatran]

http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

has a lot of information on calculating n! exactly.

 

[Tide]

Does this help you?

9! = 2^7\times3^4\times5\times7

I do recommend getting a calculator. :)

 

[robert Ihnot]

I am surprised that no one mentions Sterling's Formula, named after James Stirling 1692-1770 (thus way before calculators).

N! approximately =(N/e)^N*[square root (2piN)]

 

[BoTemp]

I am surprised that no one mentions Sterling's Formula, named after James Stirling 1692-1770 (thus way before calculators).

N! approximately =(N/e)^N*[square root (2piN)]

It should be mentioned that this is only an approximation. It's a very accurate one, and becomes increasingly accurate for large N. I believe 10! is off by about 1%. But for an exact formula, I don't think there's a way to do it other than straight out multiplication.

 

[eljose]

I am surprised that no one mentions Sterling's Formula, named after James Stirling 1692-1770 (thus way before calculators).

N! approximately =(N/e)^N*[square root (2piN)]

the "Stirling-Formula" is just an asymptotic expansion...the error term increases madly...

n!\sim \sqrt 2\pi n^{n}e^{-n} meaning that...

\frac{n!}{\sqrt 2\pi n^{n}e^{-n}}\rightarrow 1 for n-->oo

 

[robert Ihnot]

Checking it out for 100!, using pari, I got (Sterling value)/100!=.999167; is that getting close or what?

For 1000!, ratio as above = .999916670.

 

[Data]

Yes, but what he means is that n! - \sqrt{2\pi n}n^n e^{-n} \rightarrow \infty for n \rightarrow \infty. So yes it's getting close fractionally but it's not getting close absolutely. Still, the Sterling approximation is useful almost everywhere when you deal with large factorials. Most macroscopic thermodynamics problems would be a whole lot more difficult to deal with analytically without it!

 

[shmoe]

Stirlings is in the 'approximations' section of the link I (and Alkatran) gave. There are also versions with more terms of the series to get better approximations. As already mentioned, the absolute error term gets attrocious using stirlings approximation for factorial, the factorial grows much more rapidly than the relative error is decreasing to make this simple approximation work. (note the relative error is something like 1+O(1/n), actually asymptotic to 1+1/(12n))

However, you can use more terms of the Stirling series, can't find any decent online references at the moment so wiki will have to do,

"[URL

see the "Derivation" section. The error term given for the approximation for log n! is a little misleading though, the constant does depend rather heavily on "m". For a fixed "m" and n-> infinity the absolute error of this approximation does go to zero, but for a fixed n and m->infinity it does not.

The consequence is for a fixed n, there is a limit to how small the absolute error can be from this approach. Not a big problem though, you can always use log(n!)=log(n+k)!-log(n+k)-...-log(n+1) and find a "k" where log(n+k)! can be found with an appropriate absolute error using stirlings. Approximate the other logs (to as small an absolute error as you need), then exponentiate and you can get n! to as small a relative error as you like to ensure an exact value of n!.

This is probably not the best way to find n! exactly, but more terms in stirlings will make the relative error plummet fairly fast (n! is still growing at an obscene rate though).

 

[robert Ihnot]

An interesting side point which I found from the references of Alkatran is the question of "Why is Gamma (n) = (n-l)! and not n!?"

Answer: The normalization of the gamma function to Gamma(n+1) instead of Gamma(n) is due to Legendre and void of any rationality.

That's good to know, 'cause I never understood that before!

 

[uart]

An interesting side point which I found from the references of Alkatran is the question of "Why is Gamma (n) = (n-l)! and not n!?"

Answer: The normalization of the gamma function to Gamma(n+1) instead of Gamma(n) is due to Legendre and void of any rationality.

That's good to know, 'cause I never understood that before!

I've never looked into the history but have always assumed that Gamma was defined with t^{x-1} in the integral instead of t^{x}, (which would of course have made Gamma(n) equal to n! instead of (n-1)! ), because the resulting integral is well defined for all x>0. With the alternate definition the integral would have been well defined for x>-1 which is not quite as neat.

 

[benorin]

Some arguments for the unit shift on gamma(n)=(n-1)

Historically the gamma function was defined as the limit of a finite product, namely

\Gamma (z) = \lim_{k\rightarrow \infty} \frac{k! k^{z-1}}{z(z+1)\cdots (z+k-1)}​

which converges for all complex z\neq 0, -1, -2,\ldots , but this still seems to have the form \Gamma (z) = f(z-1) where it seems that f(z) is somehow more simple.

Equivalently, the infiniite product form used by Euler was

\Gamma (z) = \frac{1}{z}\prod_{k=1}^{\infty} \left( 1+\frac{z}{k}\right) ^{-1}\left( 1+\frac{1}{k}\right) ^{z}​

also converging for all complex z\neq 0, -1, -2,\ldots , but this does have the look of a function that would not be any more attractive if it were shifted by a unit, and the same remarks hold for the Weierstrass product form of the gamma function, which is

\frac{1}{\Gamma (z)} = ze^{\gamma z}\prod_{k=1}^{\infty} \left( 1+\frac{z}{k}\right) ^{-1} e^{-\frac{z}{k}}​

where \gamma =0.577\ldots Euler's constant. Also of note is that the Eulerian integral of the second kind, which is that definition of recent conversation:

\Gamma (z) = \int_{0}^{\infty}e^{-t}t^{z-1} \, dt ,​

is notable in that it is the Mellin transform of e^{-t} since the Mellin transform of f(t) is

\mathcal{M} \left[ f(t) \right] = \int_{0}^{\infty}f(t) t^{z-1} \, dt .​

...but I think that the most complelling reason for the shift lies in that the functional equation for the Riemann zeta function, which has the nice symmetric form

\Gamma \left( \frac{s}{2}\right) \pi^{-\frac{s}{2}}\zeta (s) = \Gamma \left( \frac{1-s}{2}\right) \pi^{-\frac{1-s}{2}}\zeta (1-s)​

would look like this

\left( \frac{s-2}{2}\right) ! \pi^{-\frac{s}{2}}\zeta (s) = \left( \frac{-1-s}{2}\right) ! \pi^{-\frac{1-s}{2}}\zeta (1-s)​

without the shift .

 

[shmoe]

The functional equation looking 'nicer' is my usual argument that this choice is the 'natural' one. However, the version given by Riemann was actually in that last form you gave, though he used a \Pi(s) for the function \Pi(s)=\Gamma(s+1). I believe this \Pi notation was from Gauss.

I don't think that Legendre was aware of Gauss' notation when he introduced Gamma. I think the most compelling reason he could have had at the time was to define the integral in such a way that it was valid to the right of 0, or to make the poles start at 0 instead of -1, either could be considered more pleasing (very subjective of course).

 

[benorin]

My computer took a tiny fraction of a second to calculate the factorial of 1,000:

<OMITTED>

The factorial of 100,000 took only about a second, but the number is far too long to post here (on the order of 40,000 digits).

- Warren

I used maple to calculate 100,000! in less than 0.14 seconds, and the number has exactly 456,574 digits (so you were off by a factor of 10).

 

[shmoe]

Stirlings approximation for log(n!) will work great for finding the number of digits of n!. |log(n!)-(n*log(n)-n+log(2*Pi*n)/2|<=1/n, so you can easily find log(n!)/log(10) without having to find log(n!) or n! directly.

 

[Tide]

Schmoe,

There are also versions with more terms of the series to get better approximations.

That is only true up to a point. As is typical with asymptotic expansions there is an optimum number of terms to get the best approximation beyond which it gets worse. The "full" expansion is, in fact, divergent.

 

[shmoe]

That is only true up to a point. As is typical with asymptotic expansions there is an optimum number of terms to get the best approximation beyond which it gets worse. The "full" expansion is, in fact, divergent.

Yep, I went into some detail how to get around this problem in that same post. Maybe I wasn't clear? I can go into more detail...

 

[Tide]

Yep, I went into some detail how to get around this problem in that same post. Maybe I wasn't clear? I can go into more detail...

Hi, Shmoe --

I'm sorry. I must have read your original post a little too quickly and missed that point.

 

[Helbert]

With the alternate definition the integral would have been well defined for x>-1 which is not quite as neat.

However it is very neat that 0! = 1. This has a combinatorial interpretation extending the interpretation for n>0 in a natural way. This gets lost with Legendre's notation. And it is common that a mathematical function is defined on the largest domain possible. So what does 'not quite as neat' mean to you? A personal dislike of -1?

 

[Helbert]

...but I think that the most complelling reason for the shift lies in that the functional equation for the Riemann zeta function, which has the nice symmetric form

Hhm..., so do you think Legendre was motivated by Riemann's paper which was written some 30 years later?