Swift replacement for C's for-loop

Question

I recently wrote an entry on my blog regarding unit testing using prime numbers as an example.

When I wrote the entry, I wrote my code keeping in minding that proposal SE-0007 has been accepted for Swift 3.0. That is, C-style for loops will no longer be available in Swift as of 3.0, so I want to completely discontinue using them.

That is to say, where I might have written something like this:

for(int divisor = 7; divisor * divisor <= value; divisor += 30) {

I was instead stuck with some real ugliness in my prime loop.

func isPrime(value: Int) -> Bool {
 if value < 2 { return false }
 if value % 2 == 0 { return value == 2 }
 if value % 3 == 0 { return value == 3 }
 if value % 5 == 0 { return value == 5 }
 if value == 7 { return true }
 var divisor = 7
 while divisor * divisor <= value {
 if value % divisor == 0 { return false }
 if value % (divisor + 4) == 0 { return false }
 if value % (divisor + 6) == 0 { return false }
 if value % (divisor + 10) == 0 { return false }
 if value % (divisor + 12) == 0 { return false }
 if value % (divisor + 16) == 0 { return false }
 if value % (divisor + 22) == 0 { return false }
 if value % (divisor + 24) == 0 { return false }
 divisor += 30
 }
 return true
}

I am satisfied that this code works as I want. I am also satisfied that is runs extraordinarily fast.

What I do not like about this is the very round-about way I have to achieve the same behavior a C-style for loop would have given me. In particular, it is the termination point that concerns me. I could easily get the same loop steps with the stride function:

for divisor in 7.stride(through: value, by: 30) {

But this doesn't allow for the same early stopping point:

divisor * divisior <= value

And making the first line of the loop check this isn't much better:

for divisor in 7.stride(through: value, by: 30) {
 if divisor * divisor > value { break }

And the biggest problem with the while loop which I'd like reviewed is that the divisor variable has a scope larger than I'd like, and the update statement doesn't come until the very end of the while loop (a problem that becomes more complex if your loop has any continue statements in it anywhere that allow iterations to break out early and jump to the next iteration).

So, in the end, I want a very, very fast isPrime() checker (it should be at least as fast as the above code), but I'd like the ugliness of my while loop to be significantly cleaned up.

• Dair: I know this is a bit off-topic, but does swift not handle the loop unrolling you have done with the chain of if statements?
• nhgrif: @Dair Explain what you mean? Notice that we're incrementing by 30 and that the pattern for values we're checking isn't necessarily straight-forward. We're not checking every single odd number.
• Martin R: In this particular case you could just write for divisor in 7.stride(through: upperBound, by: 30) where upperBound is precomputed as the integer square root of value.

Answer 1

Python also has no C-style for-loop. A lot of Python novices write clumsy while-loops as a result. However, once you learn the Pythonic idioms for looping, you'll wonder why other languages aren't more like Python.

The trick is to get to know...

• the range() built-in function, which looks a lot like the stride(through: by:) that you suggested
• the enumerate() built-in function, for when you need to iterate over a list and also increment a counter at the same time
• the itertools library for more complex situations

If I had to translate your Swift code to Python, I would do it using itertools.count() to generate the infinite sequence [7, 37, 67, 97, ...], and itertools.takewhile() to terminate it.

from itertools import count, takewhile
def is_prime(value):
 if value < 2: return False
 if value % 2 == 0: return value == 2
 if value % 3 == 0: return value == 3
 if value % 5 == 0: return value == 5
 if value == 7: return True
 for divisor in takewhile(lambda d: d * d <= value, count(7, 30)):
 if value % divisor == 0: return False
 for offset in [4, 6, 10, 12, 16, 22, 24]:
 if value % (divisor + offset) == 0: return False
 return True

Kevin Ballard has posted a proposal on the swift-evolution mailing list to introduce a takeWhile() to the standard library. I think that a rich library for manipulating sequence types would make a good replacement for C-style for-loops.

• nhgrif: I'd probably drop 0 into the array of offsets here. Otherwise, it kind of looks suspicious. But I do like this takewhile and definitely like the nested inner loop of offsets. Now to just figure out implementing this in Swift...
• Flambino: I think that a rich library for manipulating sequence types would make a good replacement for C-style for-loops Agree. At first I thought "No for loop? Madness!" but then... I don't think I've ever used a for loop in Ruby (and it has one). Or if I have, I've thought the better of it

Answer 2

So, noting @Martin R's comment:

In this particular case you could just write for divisor in 7.stride(through: upperBound, by: 30) where upperBound is precomputed as the integer square root of value.

I wasn't sure how much I necessarily cared for this approach. And the fact that it's posted as a comment rather than an answer suggests that perhaps Martin R also agrees that this isn't necessarily super satisfying. And it's also only particularly useful in this specific case, and may not handle the full utility of conditional part of C-style for loops.

And then I realize I could just use a where clause.

The function now becomes:

func isPrime(value: Int) -> Bool {
 if value < 2 { return false }
 if value % 2 == 0 { return value == 2 }
 if value % 3 == 0 { return value == 3 }
 if value % 5 == 0 { return value == 5 }
 if value == 7 { return true }
 
 for divisor in 7.stride(through: value, by: 30) where divisor * divisor <= value {
 if value % divisor == 0 { return false }
 if value % (divisor + 4) == 0 { return false }
 if value % (divisor + 6) == 0 { return false }
 if value % (divisor + 10) == 0 { return false }
 if value % (divisor + 12) == 0 { return false }
 if value % (divisor + 16) == 0 { return false }
 if value % (divisor + 22) == 0 { return false }
 if value % (divisor + 24) == 0 { return false }
 }
 return true
}

In both my original while approach and the approach that Martin R's comment suggests, we have to create a variable that has a scope outside of the loop. Here, we don't have to do that. The divisor variable is the only variable we are creating and its scope is limited to the loop.

Importantly, this could be solved using Martin R's comment suggestion, and that is potentially more efficient for cases in which we have to go through several iterations of the loop. Multiplying two integers and comparing less than or equal to another integer is more probably more efficient than calculating the integer square root of a number, but only if we're doing both an equal number of times.

Calculating the integer square root would have the advantage of only having to be done once, so for a particularly large number that would require several loops, it might be quicker.

But perhaps most importantly, the where syntax is probably the most exact translation of the original C-style for loop mentioned:

C-Style

for(int divisor = 7; divisor * divisor <= value; divisor += 30) {

Swift

for divisor in 7.stride(through: value, by: 30) where divisor * divisor <= value {

---

And to take a hint from 200_success's answer, we can nest loops to condense the code a little bit:

func isPrime(value: Int) -> Bool {
 if value < 2 { return false }
 for baseDivisor in [2, 3, 5, 7] {
 if value % baseDivisor == 0 { return value == baseDivisor }
 }
 
 for divisor in 7.stride(through: value, by: 30) where divisor * divisor <= value {
 for offset in [0, 4, 6, 10, 12, 16, 22, 24] {
 if value % (divisor + offset) == 0 { return false }
 }
 }
 return true
}

• Martin R: Note that for divisor in 7.stride(through: value, by: 30) where divisor * divisor <= value { .. } does not terminate the loop when the where-condition is violated. It just skips the body for those cases. So it is not an exact translation of the C loop.
• nhgrif: Right. It's not quite exact
• Martin R: In your question you asked for a solution which is at least as fast as your original code. Did you check the performance of the for ... where solution? Since it actually loops until value I would expect it to be slower. – I made some tests when the first answer was posted, and the for offset in [ ... ] turned out to be much slower than 8 if statements.
• nhgrif: For this particular answer, I did not check performance. I'm never going to mark this answer as accepted (unless I did go check performance and found out this one is faster also). This answer has some readability advantages, but of course, yes, my original question stated a preference for performance.