Quickest way of finding the largest integer n such that n! has length of m bits

Question

Factstone Benchmark

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.)

Amtel will use a new benchmark – the Factstone – to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integer \$n\$ such that \$n!\$ can be represented as an unsigned integer in a computer word.

Given a year \1960ドル\le y\le 2160\,ドル what will be the Factstone rating of Amtel's most recently released chip?

Input

There are several test cases. For each test case, there is one line of input containing \$y\$. A line containing \0ドル\$ follows the last test case.>

Output

For each test case, output a line giving the Factstone rating.

Sample Input 1

1960
1981
0

Sample Output 1

3
8

import math
n = int(input())
while n != 0:
 n = (n - 1960) / 10 + 2
 m = pow(2,n)
 i = 1
 while m > 0:
 m -= math.log(i,2)
 i += 1
 print(i - 2)
 n = int(input())

Can someone please help me time optimize this code? I'm doing it for a site that checks my code but I always fail at the time check.

• Snowbody: You'd get better results by doing a binary search for the answer rather than by searching linearly. Use memoization or some lookup tables to avoid recalculating things that were already calculated.

Answer 1

import math
n = int(input())
while n != 0:
 n = (n - 1960) / 10 + 2

What does n represent now? n as a name for the value which is called y in the task description is already unnecessarily obscure, but aliasing it really confuses things.

In addition, note that in Python / does floating point division. If the output for 1969 should be the same as the output for 1960 (and I'm pretty sure the spec requires that) then there's a bug here.

 m = pow(2,n)

What does m represent? If you want people to review your code, use descriptive names!

 while m > 0:
 m -= math.log(i,2)
 i += 1

How many times does this loop execute for the largest possible input? How can you avoid a linear loop? (Hint: a certain Stirling analysed \$\log n!\$ ...)

(Or, arguably cheating, there are only 21 decades in view, so you could hard-code a lookup.)

Answer 2

You need to use some maths.

You want to know whether

\$n! < 2^b\$ (where \$b\$ is the number of bits)

This is equivalent of:

\$\log n! \lt \log 2^b\$
\$\log n! \lt b\log 2\$

Then we need efficient \$\log n!\$ calculation..

\$\log n!\$ = \$\log (n(n-1)!)\$ = \$\log n + \log (n-1)!\$

We can pre-compute the log n! for the first some n

The maximum year = 2160, with equals a 4194304 bits computer.

As I'm trying I see you need way to much pre-computed log n!, so we need a better way of calculating log n!. There exists an solution when log is chosen to be the natural logarithm ln: http://mathworld.wolfram.com/StirlingsApproximation.html

It states:

\$ \ln n! ≈ n \ln n-n+1\$ (for big n)

so we need to solve:

\$ n \ln n-n+1 < b \ln 2\$

For small n we can still use a lookup table. You can determine where the error gets small enough to stop using the lookup-table.

• Peilonrayz: If \$\log\$ is \$\log_2\,ドル then you can use \$\log_2n! \lt b\$. Which is really fast and simple.
• Rob Audenaerde: Yes, but n! get really bit really fast, so need to find something smarter there yet. Probably log ab = log a + log b ;)
• Peter Taylor: Do you realise that what you've done here is propose that OP make no changes to his code?
• Rob Audenaerde: I believe it is not, as I will never calculate the powers of 2 and get into the big numbers?
• Peter Taylor: Nor does OP's code. (I agree that m = pow(2,n) looks like it's doing that, but it turns out to be calculating \$b\$).