Why does this 'optimized' prime checker run at the same speed as the regular version?

Viewed 127

Given this plain is_prime1 function which checks all the divisors from 1 to sqrt(p) with some bit-playing in order to avoid even numbers which are of-course not primes.

import time
def is_prime1(p):
    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for k in range(2, int(p ** 0.5) + 1):
        if p % k == 0:
            return False
    return True

Versus this "optimized" version. The idea is to save all the primes we have found until a certain number p, then we iterate on the primes (using this basic arithmetic rule that every number is a product of primes) so we don't iterate through the numbers until sqrt(p) but over the primes we found which supposed to be a tiny bit compared to sqrt(p). We also iterate only on half the elements, because then the largest prime would most certainly won't "fit" in the number p.

import time
global mem
global lenMem
mem = [2]
lenMem = 1

def is_prime2(p):
    global mem
    global lenMem
    # if p is even then the LSD is off

    if p & 1 == 0:
        return False
    # if the LSD is 5 then it is divisible by 5 (i.e. not a prime)
    elif p % 10 == 5:
        return False

    for div in mem[0: int(p ** 0.5) + 1]:
        if p % div == 0:
            return False
    mem.append(p)
    lenMem += 1
    return True

The only idea I have in mind is that "global variables are expensive and time consuming" but I don't know if there is another way, and if there is, will it really help?

On average, when running this same program:

start = time.perf_counter()
for p in range(2, 100000):
    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
end = time.perf_counter()

I get that for is_prime1 the average time for checking the numbers 1-100K is ~0.99 seconds and so is_prime2 (maybe a difference of +0.01s on average, maybe as I said the usage of global variables ruin some performance?)

3 Answers

The difference is a combination of three things:

  1. You're just not doing that much less work. Your test case includes testing a ton of small numbers, where the distinction between testing "all numbers from 2 to square root" and testing "all primes from 2 to square root" just isn't that much of a difference. Your "average case" is roughly the midpoint of the range, 50,000, square root of 223.6, which means testing 48 primes, or testing 222 numbers if the number is prime, but most numbers aren't prime, and most numbers have at least one small factor (proof left as exercise), so you short-circuit and don't actually test most of the numbers in either set (if there's a factor below 8, which applies to ~77% of all numbers, you've saved maybe two tests by limiting yourself to primes)

  2. You're slicing mem every time, which is performed eagerly, and completely, even if you don't use all the values (and as noted, you almost never do for the non-primes). This isn't a huge cost, but then, you weren't getting huge savings from skipping non-primes, so it likely eats what little savings you got from the other optimization.

  3. (You found this one, good show) Your slice of primes took a number of primes to test equal to the square root of number to test, not all primes less than the square root of the number to test. So you actually performed the same number of tests, just with different numbers (many of them primes larger than the square root that definitely don't need to be tested).

A side-note:

Your up-front tests aren't actually saving you much work; you redo both tests in the loop, so they're wasted effort when the number is prime (you test them both twice). And your test for divisibility by five is pointless; % 10 is no faster than % 5 (computers don't operate in base-10 anyway), and if not p % 5: is a slightly faster, more direct, and more complete (your test doesn't recognize multiples of 10, just multiples of 5 that aren't multiples of 10) way to test for divisibility.

The tests are also wrong, because they don't exclude the base case (they say 2 and 5 are not prime, because they're divisible by 2 and 5 respectively).

First of all, you should remove the print call, it is very time consuming. You should just time your function, not the print function, so you could do it like this:

start = time.perf_counter()
for p in range(2, 100000):
##    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
    is_prime1(p)
end = time.perf_counter()

print ("prime1", end-start)


start = time.perf_counter()
for p in range(2, 100000):
##    print(f'{p} is a prime? {is_prime2(p)}') # change to is_prime1 or is_prime2
    is_prime2(p)
end = time.perf_counter()

print ("prime2", end-start)

is_prime1 is still faster for me.

If you want to hold primes in global memory to accelerate multiple calls, you need to ensure that the primes list is properly populated even when the function is called with numbers in random order. The way is_prime2() stores and uses the primes assumes that, for example, it is called with 7 before being called with 343. If not, 343 will be treated as a prime because 7 is not yet in the primes list.

So the function must compute and store all primes up to √49 before it can respond to the is_prime(343) call.

In order to quickly build a primes list, the Sieve of Eratosthenes is one of the fastest method. But, since you don't know in advance how many primes you need, you can't allocate the sieve's bit flags in advance. What you can do is use a rolling window of the sieve to move forward by chunks (of let"s say 1000000 bits at a time). When a number beyond your maximum prime is requested, you just generate more primes chunk by chunk until you have enough to respond.

Also, since you're going to build a list of primes, you might as well make it a set and check if the requested number is in it to respond to the function call. This will require generating more primes than needed for divisions but, in the spirit of accelerating subsequent calls, that should not be an issue.

Here's an example of an isPrime() function that uses that approach:

primes      = {3}
sieveMax    = 3
sieveChunk  = 1000000 # must be an even number
def isPrime(n):
    if not n&1: return n==2
    global primes,sieveMax, sieveChunk
    while n>sieveMax:
        base,sieveMax = sieveMax, sieveMax + sieveChunk
        sieve = [True]* sieveChunk
        for p in primes:
            i = (p - base%p)%p
            sieve[i::p]=[False]*len(sieve[i::p])
        for i in range(0, sieveChunk,2):
            if not sieve[i]: continue
            p = i + base
            primes.add(p)
            sieve[i::p] = [False]*len(sieve[i::p])
    return n in primes    

On the first call to an unknown prime, it will perform slower than the divisions approach but as the prime list builds up, it will provide much better response time.

Related