[Guest]

How many bits are required to represent the result of the operations below on a positive integer 'm' that contains 'n' bits:

1) (Easy) 2*m

2) (Medium) m*m

3) (Hard) m^m

4) (Impossible?) m!

Good luck.

[Guest]

How many bits are required to represent the result of the operations below on a positive integer 'm' that contains 'n' bits:

1) (Easy) 2*m

2) (Medium) m*m

3) (Hard) m^m

4) (Impossible?) m!

Good luck.

I should add that I do not know the answer to #4, thus the (Impossible?) tag.

[Guest]

I'm not sure about this, but if the number of bits is the number of digits of the result in base 2, then it's just logarithms. 1st is n+1, 2nd is 2*logm (in base 2 and rounded) 3rd m*logm and last is logm + log(m-1)+ ... + log2 + log1. I guess I'm way off, but whatever.

[unreality]

How many bits are required to represent the result of the operations below on a positive integer 'm' that contains 'n' bits:

1) (Easy) 2*m

2) (Medium) m*m

3) (Hard) m^m

4) (Impossible?) m!

Good luck.

knowing that n = ceiling(log(m))

where log is in base 2

1) n+1 (at most; it could stay n)

2) 2n (at most)

3) m*n I think

4) log (m!) = log(m) + log(m-1) + ... + log(1) = approximate version of the definite integral of logx from 1 to m

assuming logx is in base two, then we use integration by parts

u = ln(x)/ln(2)

du = 1 / (x ln(2)) dx

dv = dx

v=x

uv = x*ln(x)/ln(2) = x*log(x) [where log is in base 2]

integral(v du) = integral(x / (x ln(2)) dx) = integral(dx / ln(2)) = x/ln(2)

so the indefinite integral is x*log(x) - x/ln(2) + C

so the definite integral from 1 to m is

m*log(m) - m/ln(2) - 1*log(1) + 1/ln(2)

= m*n + (1-m)/ln(2)

alternately:

m*n + 1.44269504 - m/ln(2)

Just an approximate but that could be it. Ceilinged of course, to be an integer

Edited August 17, 2010 by unreality

[Guest]

knowing that n = ceiling(log(m))

where log is in base 2

1) n+1 (at most; it could stay n)

2) 2n (at most)

3) m*n I think

4) log (m!) = log(m) + log(m-1) + ... + log(1) = approximate version of the definite integral of logx from 1 to m

assuming logx is in base two, then we use integration by parts

u = ln(x)/ln(2)

du = 1 / (x ln(2)) dx

dv = dx

v=x

uv = x*ln(x)/ln(2) = x*log(x) [where log is in base 2]

integral(v du) = integral(x / (x ln(2)) dx) = integral(dx / ln(2)) = x/ln(2)

so the indefinite integral is x*log(x) - x/ln(2) + C

so the definite integral from 1 to m is

m*log(m) - m/ln(2) - 1*log(1) + 1/ln(2)

= m*n + (1-m)/ln(2)

alternately:

m*n + 1.44269504 - m/ln(2)

Just an approximate but that could be it. Ceilinged of course, to be an integer

1) Yes

2) Yes

3) right thinking, however I think you may have made an assumption about n that doesn't always hold true. Try it with some real numbers (2^4 - 1 for example).

4) Wow! great job. I believe your thinking is correct, however it still doesn't quite always work out though:

Example with 2^5-1 (31)

ceil(Log2(31!)) = 113 (I believe this is the correct answer for the number of bits for 31!)

ceil(31*Log2(31) + (1-31)/ln(2)) = 111

I'm not sure where the break down is - I can't seem to figure it out.

[Guest]

1) log₂(m)+1

2) log₂(m²)/2+1

3) log₂(m^m)/m+1

4) ≈log₂((√(2πm))•(m/e)^m)+1

[Guest]

1) log₂(m)+1

2) log₂(m²)/2+1

3) log₂(m^m)/m+1

4) ≈log₂((√(2πm))•(m/e)^m)+1

I assume you are using the ceiling operation on all answers

1) Yes, this also works. but n+1 is the simplest answer

2) Log2(m^2)/2 + 1 simplifies to Log2(m)+1 which doesn't give the correct answer (gives same answer as #1)

3) Log2(m^m)/m + 1 also simplifies to Log2(m)+1 which doesn't give the correct answer (gives same answer as #1)

4) Not sure about this one - it doesn't seem to produce the correct answer. Try it with m = 31, it should produce 113

archlordbr has the best answer for #4 so far with ceil(log2(m) + log2(m-1)+ ... + log2(2) + log2(1)).

I'd really be interested to see if unreality answer to #4 could be modified to work - it definitely yields a much simpler formula.

[unreality]

littlej, it just takes the sum that both archlordbr and I came up with from the logarithm and just attempts to approximate the sum with integration. But because of that it can't be 100% exact

[Guest]

1. ⌈log₂(m)+1 ⌉

2. ⌈2•log₂(m)+1 ⌉

3. ⌈m•log₂(m)+1 ⌉

4. ⌈½•log₂(2πm) + m•log₂(m) – m•(log₂(e))+1 ⌉

(I've applied Stirling's approximation for m! in #4. It is not exact, but a close approximation.)