# 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.

• 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. – Snowbody Jan 16 '18 at 15:00

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.)

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.

• If $\log$ is $\log_2$, then you can use $\log_2n! \lt b$. Which is really fast and simple. – Peilonrayz Jan 16 '18 at 15:13
• Yes, but n! get really bit really fast, so need to find something smarter there yet. Probably log ab = log a + log b ;) – RobAu Jan 16 '18 at 15:16
• Do you realise that what you've done here is propose that OP make no changes to his code? – Peter Taylor Jan 16 '18 at 15:23
• I believe it is not, as I will never calculate the powers of 2 and get into the big numbers? – RobAu Jan 16 '18 at 15:26
• 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$). – Peter Taylor Jan 16 '18 at 15:56