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.

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.