3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Snowbody
    Jan 16 '18 at 15:00
6
\$\begingroup\$
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.)

\$\endgroup\$
2
\$\begingroup\$

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.

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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .