Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have verified that both of my following functions successfully find prime numbers. I was pretty sure the function called is_prime_new would be faster than is_prime_old; however, after benchmarking (mainly consisting of generating huge lists of primes), I found this to be significantly false and I'm wondering why this may be.

I had two main reasons for thinking that is_prime_new would be a better algorithm than its counterpart:

  • is_prime_new does more checks for non-primailty early, thus eliminating numbers before iteration

  • It iterates in steps of 6, whereas its counterpart iterates in steps of 2, both to the same value sqrt(n)+1

Could anyone explain to me why the newer function is less optimized, and possibly debunk my above assumptions? Thank you.

def is_prime_new(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqr = math.sqrt(n)
    if sqr == int(sqr): return False

    i = 1
    while i*6 < sqr+1:
        if n % (i*6-1) == 0 or n % (i*6+1) == 0: return False
        i += 1

    return True

def is_prime_old(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False

    for i in xrange(3, int(math.sqrt(n)+1), 2):
        if not n%i: return False

    return True
share|improve this question

3 Answers 3

up vote 3 down vote accepted

Duncan's explanation is incorrect. This isn't my best piece of writing - bear with me.


First lets deal with n < 2 and n == 2 or n == 3:

It is true that they let a lot more input go past them than they stop. But they don't account for the difference in time.

  1. Even the old definition has n < 2 and n == 2.
  2. The time spent on this part of the function is very insignificant compared to that spent in the rest of the function.

Next n%2 == 0 or n%3 == 0:

  1. Again n%2 == 0 is in the old definition also.
  2. n%3 == 0 is the first check in old's for loop
  3. The time spent on this part of the function is also insignificant compared to that spent in the rest of the function.

I could've clubbed this with the previous section but didn't for the following reason:

These checks work on 4 out of every 6 input numbers. And 4 > 6-4. But is that the way to look at it? If say they'd worked on 3/6 [As in the case of old] are these checks useless? If say they'd worked on 2/6 should they be avoided? No.

By doing one(or two) comparison(s) on 6 inputs, they stop 2 from reaching the work horse of the code - the loop - that does most of the work. That's not to be avoided!

Also, by imposing additional constraints on the input that reaches the loop, the loop itself has been made faster! Knowing that no multiple of 3 enters the loop, you don't test divisibility of n by any other multiple of 3. Don't forget your main idea behind moving from old to new!

Faster loop + lesser numbers reaching loop should make new faster than old.


How much faster exactly?

  1. I mentioned "lesser numbers reaching loop" being good only as a general guideline. It doesn't help much here because : In old 3,5,7,9... enter the loop, and in new 5,7,11,13... enter the loop. But in old 3,9... get stopped at the first check of the for loop. So only faster loop is important.

  2. new's loop jumps in steps of 6 but old's jumps in steps of 2. So is new 3 times faster than old? No. At every step new does 3 comparisons - one for the while loop condition and two inside the loop. old does 2 - one at for loop condition and one inside the loop. So, new is (6/3) * (2/2) = 2 times faster than old.


So far I've only been explaining why new should be faster. Finally I'll address your question of why this isn't observed:

for loops are much faster than while loops. python doesn't know how i is going to change inside while. So the while loop's condition check is like any other comparison. On the other hand for loop's condition check is highly optimised. Henceforth lets assume that for loop's condition check doesn't count as a comparison.

Then old's time/new's time will be

  1. 6/3 * 2/2 = 2 if both use while
  2. 6/2 * 1/2 = 1.5 if both use for
  3. 6/2 * 2/2 = 3 if old used while and new used for
  4. 6/3 * 1/2 = 1 if old used for and new used while

That still means that old and new should be (at least approximately) equally fast. This is where I was stumped. I had to resort to experimenting to figure this out. The reasons for this not occurring, as it turns out, are

  1. All the unnecessary arithmetic (*6) in the while loop
  2. while i*6 < sqr+1: Here sqrt is a floating point number. As it turns out float comparison is costlier than int comparison. while i*6 < int(sqr+1) isn't good either. You should use sqrp1 = int(sqr+1); while i*6 < sqrp1

Note that the ratios provided are from rough calculations and far from being accurate - there are so many more things to consider. One major assumption is that time spent in the loops is much larger than time spent at base case checks - not true if all your input are multiples of 2.


To summarise, the reasons for new being slower, despite being expected to be faster, are:

  1. Usage of while instead of for (this is not as important as the other two)
  2. Unnecessary arithmetic inside while
  3. Usage of float comparison instead of int comparison in while condition check.

The code given below illustrates some of the points made here.

import math, timeit

def is_prime_new_slowest(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqr = math.sqrt(n) #This is insignificant as it is outside the loop
    if sqr == int(sqr): return False
    sqrtp1 = sqr + 1 #Note that sqrtp1 is a float
    i = 1
    while i*6 < sqrtp1: # Comparison of floats adds some time
        if n % (i*6-1) == 0 or n % (i*6+1) == 0: return False #Unnecessary arithmetic
        i += 1
    return True

def is_prime_new_slow(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqrtp1 = int(math.sqrt(n) + 1)
    i = 6
    while i < sqrtp1:
        if n % (i-1) == 0 or n % (i+1) == 0: return False
        i += 6
    return True

def is_prime_new_fast(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqrtp1 = int(math.sqrt(n)+1)
    for i in xrange(6, sqrtp1, 6):
        if n % (i-1) == 0 or n % (i+1) == 0: return False
    return True

def is_prime_old_slow(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False
    sqrtp1 = int(math.sqrt(n) + 1)
    i = 3
    while i < sqrtp1:
        if not n%i: return False
        i += 2
    return True

def is_prime_old_fast(n):
    if n < 2: return False
    if n == 2: return True
    if n%2 == 0: return False
    sqrtp1 = int(math.sqrt(n)+1)
    for i in xrange(3, sqrtp1, 2):
        if not n%i: return False
    return True

def sundaram3(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4
    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)
        if initial > half:
            return [2] + filter(None, numbers)

i = sundaram3(10**6)[-1]

print "Input: largest prime less than 10^6, No. of runs: 25000"
print "new slowest:", timeit.timeit('is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest, i; import math", number=25000)
print "new slow:", timeit.timeit('is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow, i; import math", number=25000)
print "new fast:", timeit.timeit('is_prime_new_fast(i)', setup="from __main__ import is_prime_new_fast, i; import math", number=25000)
print "old slow:", timeit.timeit('is_prime_old_slow(i)', setup="from __main__ import is_prime_old_slow, i; import math", number=25000)
print "old fast:", timeit.timeit('is_prime_old_fast(i)', setup="from __main__ import is_prime_old_fast, i; import math", number=25000)

print "\nInput: range(1000000), No. of runs = 1"
print "new slowest:", timeit.timeit('for i in xrange(1000000): is_prime_new_slowest(i)', setup="from __main__ import is_prime_new_slowest; import math", number=1)
print "new slow:", timeit.timeit('for i in xrange(1000000): is_prime_new_slow(i)', setup="from __main__ import is_prime_new_slow; import math", number=1)
print "new fast:", timeit.timeit('for i in xrange(1000000): is_prime_new_fast(i)', setup="from __main__ import is_prime_new_fast; import math", number=1)
print "old slow:", timeit.timeit('for i in xrange(1000000): is_prime_old_slow(i)', setup="from __main__ import is_prime_old_slow; import math", number=1)
print "old fast:", timeit.timeit('for i in xrange(1000000): is_prime_old_fast(i)', setup="from __main__ import is_prime_old_fast; import math", number=1)

Output on my machine:

Input: largest prime less than 10^6, No. of runs = 25000
new slowest: 7.37190294266
new slow: 4.19636297226
new fast: 3.49502682686
old slow: 6.08556985855
old fast: 4.03657603264

Input: range(1000000), No. of runs = 1
new slowest: 21.5607540607
new slow: 13.8396618366
new fast: 12.3734707832
old slow: 20.0376861095
old fast: 14.1358599663

Note that for - while deterioration becomes less important as the number of comparisons inside the loop reduces [old - one comparison - time goes from 14 to 20, new - two comparisons - 12.3 to 13.83]. This is expected because 1 comparison becoming 2 has a greater effect on final time than 10 comparisons becoming 11. This is why while-for performance difference generally doesn't matter in real life.

share|improve this answer

can you test the following (slightly optimized) version?

def is_prime_new(n):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n%2 == 0 or n%3 == 0: return False
    sqr = math.sqrt(n)
    if sqr == int(sqr): return False
    sqr = int(sqr) + 1

    i = 6
    while i < sqr:
        if n % (i-1) == 0 or n % (i+1) == 0: return False
        i += 6

    return True
share|improve this answer
    
+1 for getting rid of the useless multiplications and of the addition :) –  Morwenn Dec 4 '12 at 23:48
    
@almaz, Thank you. These suggestions did speed up my new function, but the old one is still faster! And my question (in its two parts) was "why is the old one faster?", "and are my 2 assumptions invalid?" Do you have anything to say about either of these questions? –  mjgpy3 Dec 5 '12 at 19:15
    
Please post the test code you're running –  almaz Dec 5 '12 at 19:27
    
You didn't post how you measure performance, so the first thing I assumed was that you introduced unnecessary calculations, so I suggested you the variant where these calculations were stripped –  almaz Dec 5 '12 at 21:32

The statement 'does more checks for non-primailty early, thus eliminating numbers before iteration' bears looking at. You only eliminate numbers on your list early if they were on the list. So if you test set has range(1,100), the statement

if n < 2: return False

only saves time on two numbers and costs time on 98 of them. Similarly

if n == 2 or n == 3: return True

However

if n%2 == 0 or n%3 == 0: return False

saves time on 50 and 33 respectively - albeit at a cost for 50 and 67 respectively. But if you only test with odd numbers that aren't divisible by 3 (eg a list you already know are primes), then it saves you nothing.

The performance test is dependent on your test input so be careful both in choosing the test input and in optimizing for that particular set of data (ie optimize to real world use, not a constrained set of test data).

share|improve this answer
    
Excellent answer. Your reasoning is clear and you pointed out that the data set makes a difference. Thank you! –  mjgpy3 Dec 5 '12 at 19:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.