wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Bits in Factorial N
        
(Message started by: johny_cage on Nov 26^th, 2007, 5:30am)

Title: Bits in Factorial N
Post by johny_cage on Nov 26^th, 2007, 5:30am

Consider the problem of computing N! = 1 . 2 . 3 ... . N
If N is an n-bit number, how many bits long is N!, approximately in terms of theta.

Title: Re: Bits in Factorial N
Post by Grimbal on Nov 26^th, 2007, 8:10am

If N is a n-bit number, N! is a log₂(2^n-1!) to log₂(2ⁿ!) bits long number. 8)

More seriously, what is theta? (besides the greek letter)

Title: Re: Bits in Factorial N
Post by pex on Nov 26^th, 2007, 8:42am

Theta is pretty much the same as Big O. (See the introduction here (http://en.wikipedia.org/wiki/Big_O_notation).)

Of course, as log(N!) is O(N logN), we have that log(2ⁿ!) = O(2ⁿlog(2ⁿ)) = O(2ⁿ n log2) = O(n 2ⁿ).

Title: Re: Bits in Factorial N
Post by wanderer on Nov 26^th, 2007, 12:15pm

Or can we analyze like this ?
O(N!) = O(N^N)
and O(N^N) has O(n^2) bits where n is the number of bits in N

Title: Re: Bits in Factorial N
Post by SMQ on Nov 26^th, 2007, 12:42pm

Using Stirling's approximation (http://en.wikipedia.org/wiki/Stirling%27s_approximation) to the factorial, N! http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifN) N^N/e^N, so:
log₂(N!) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif log₂((2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gifN)^1/2N^N/e^N)
= (1 + log₂ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif + log₂ N)/2 + N log₂ N - N log₂ e
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/approx.gif 1.326 + n/2 + (n - 1.443)N where n = log₂ N.

--SMQ

Title: Re: Bits in Factorial N
Post by johny_cage on Nov 27^th, 2007, 6:23am

@All

Plz explain how you are getting this bound????