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.
- Even the
old definition has n < 2 and n == 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:
- Again
n%2 == 0 is in the old definition also.
n%3 == 0 is the first check in old's for loop- 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?
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.
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
- 6/3 * 2/2 = 2 if both use
while
- 6/2 * 1/2 = 1.5 if both use
for
- 6/2 * 2/2 = 3 if
old used while and new used for
- 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
- All the unnecessary arithmetic (*6) in the while loop
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:
- Usage of
while instead of for (this is not as important as the other two)
- Unnecessary arithmetic inside
while
- 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.
