Factorial of a Number

[legend986]

I have seen the iterative and recursive ways of calculating the factorial of a number but is there an efficient of way of doing it say in a log-time or something?

[marceln]

See http://en.wikipedia.org/wiki/Factorial, (http://en.wikipedia.org/wiki/Factorial) the chapter about computation and also the one about the gamma function.
Also, this is an introductory article about Stirling's formula: http://en.wikipedia.org/wiki/Stirling%27s_formula

[legend986]

That was very helpful. Thank You... The Gamma function looks interesting... However, the complexity was not mentioned in the wiki page. It looks like implementable but how much better is it than the normal factorial function? Can you shed some light on this please?

[marceln]

The gamma function as well as Striling's formula are simple formula's.
It is just a matter of raising two numbers(n and e) to the power of n. If the result fits on 32 bits(or 64, for 64bit architectures) then the time is O(1).

Otherwise the time is directly proportional with the complexity of computing the n^n and e^n bignums.

However, I was hoping you would also notice in the wiki article this paragraph:
The asymptotically-best efficiency is obtained by computing n! from its prime factorization. As documented by Peter Borwein (http://en.wikipedia.org/wiki/Peter_Borwein), prime factorization allows n! to be computed in time O (http://en.wikipedia.org/wiki/Big_O_notation)(n(log n log log n)2), provided that a fast multiplication algorithm (http://en.wikipedia.org/wiki/Multiplication_algorithm) is used (for example, the Schönhage-Strassen algorithm (http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm)).[1] (http://en.wikipedia.org/wiki/Factorial#_note-0) Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve (http://en.wikipedia.org/wiki/Prime_sieve).[2] (http://en.wikipedia.org/wiki/Factorial#_note-1)


Regards