How Do You Predict A Non-Linear Script's Run Time?

Question

I wrote this simple code in python to calculate a given number of primes.

The question I want to ask is whether or not it's possible for me to write a script that calculates how long it will take, in terms of processor cycles, to execute this? If yes then how?

primes = [2]
pstep = 3
count = 1

def ifprime (a):

""" Checking if the passed number is prime or not"""
global primes

for check in primes:
    if (a%check) == 0:
            return False
return True

while 1000000000>= count:

if ifprime(pstep):
    primes.append (pstep)
    print pstep
    count += 1
pstep += 1

The interesting thing about this problem is that whether or not I find primes after x cycles of incrementation is something nearly impossible to predict. Moreover, there's recursion happening in this scenario since the larger 'prime' list grow the longer it will take to execute this function.

Any tips?

Answer 1

Well, if you are on linux you can use 'time' command and then parse it's result.

For your problem I would do the timing for 1000s of large primes of different size and would draw a chart, so it would be easy to analize.

Answer 2

I think you would have to use an approximation of the distribution of primes, a la PNT which (I think) states that between 1 and x you'll have approximately x/ln(x) primes (ln being natural log). So given rough estimates of the time taken for a single iteration, you should be able to create an estimate.

You have approximately x/ln(x) primes in your list. Your main code block (inside the while loop) has constant time (effectively)...so:

t(x) ~ x/ln(x) * a + b + t(x-1)

where t(x) is the time taken up to and including iteration x, a is the time taken to check each prime in the list (modulous operation), and b is the 'constant' time of the main loop. I faintly remember there is a way to convert such recursive functions to linear ones ;)

Answer 3

If you want to predict the time an arbitrary process needs until it is finished, you can't do that, as that is basically the problem behind the Halting Problem. In special cases you can estimate the time your script will take, for example if you know that it is generated in a way that doesn't allow loops.

In your special case of finding primes, it is even harder to guess the time it will take before running the process, as there is only a lower bound for the number of primes within an intervall, but that doesn't help finding them.

Answer 4

Well, there is a large branch of theoretical computer science -- complexity theory -- dedicated to just this sort of problem. The general problem (of deciding on whether a code will finish for arbitrary input) you have here is what is called "NP-complete" and is therefore very hard.

But in this case you probably have two options.

The first is to use brute force. Run timeit for isprime(a) for a=1, 2, 3, 4, ..., plot the graph of the times, and try to see if it looks like something obvious: a^2, a log a, whatever.

The right -- but harder -- answer is to analyze your algorithm and see if you can work out how many operations it takes for a "typical case".

Answer 5

When you call isprime(pstep) you are looping pstep * ln(pstep) times, if you have a prime, of which the probability is 1/ln(pstep). So the cost of testing the primes is proportional to step. Unknown is the cost of testing the composites, because we don't know the average lowest factor of the composites between 2 and N. If we ignore it, assuming it is dominated by the cost for the primes, we get a total cost of SUM(pstep) for pstep = 3 to N+3, which is about proportional to N**2.

You can reduce this to N**1.5 by cutting off the loop in isprime() when checked > sqrt(a).