Python: break out of multiple levels of loop

Question

I have this pseudocode for a Miller-Rabin primality tester:

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

But translating that to Python is hard because of the next i statement in the inner for loop, which must break two loops. There is no goto in Python. Other questioners who have asked this question on Stack Overflow have been told to use a local function with a return, or a try/except condition, or an additional boolean flag, but those solutions either don't apply here or would greatly uglify this lovely pseudocode.

What is the Pythonic approach to this problem?

@Christian "I have this pseudocode" This is not supposed to be valid python. — SethMMorton
– SethMMorton, Commented Jun 11, 2014 at 18:15
Are you against the for: else paradigm? That might work for you, but if "not ugly" is your criteria you might not want that either. — SethMMorton
– SethMMorton, Commented Jun 11, 2014 at 18:16
You might want to clarify that you don't want to break out of two loops, but to break out of the first one and continue the second one. (For breaking out of both, the mentioned return trick would do it) — Aleksi Torhamo
– Aleksi Torhamo, Commented Jun 11, 2014 at 18:23

tktk · Accepted Answer · 2014-06-11 18:32:56Z

3

I think the pythonic approach would be try/except, readability would prefer a method or a boolean, but I think that this is solvable by adding a single line:

    for i in xrange(k):
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in xrange(1,s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break #*
        if x != n-1: #added line
            return False
    return True

breaking on the line marked with #* is problematic because it returns false, but if we fix that it's just like "next i".

Another solution, suggested by tobias_k, is to use for/else:

    for i in xrange(k):
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in xrange(1,s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break 
        else: #added line
            return False
    return True

return False statement would not be called if the loop was break-ed - only if it was exhausted.

edited Jun 11, 2014 at 18:32

answered Jun 11, 2014 at 18:25

tktk

11.8k8 gold badges61 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

tobias_k Over a year ago

I think this is one of those cases where you can use for/else instead of that new if

tobias_k Over a year ago

Not at all! That's why I posted that comment! ;-) BTW, I think powerMod is just pow in Python (with optional third parameter. At least the test seems to work that way.

tktk Over a year ago

I went with minor formatting, so left it as is. Personally I think that if xxx: yyyy lines are less readable, so I wouldn't use that as well, but I wanted to change the original code as little as possible.

user448810 Over a year ago

I don't like the first approach, because of the duplicate test. I do like the second approach, which is very idiomatic. Thanks Tal and Tobias!

SethMMorton · Accepted Answer · 2014-06-11 18:25:22Z

1

You can use break and continue witn a for: else.

for i from 0 to k
    x = powerMod(randint(2, n-1), d, n)
    # Use 'continue' to go to next i (skip inner loop).
    if x == 1 or x == n-1 then next i
    for r from 1 to s
        x = (x * x) % n
        if x == 1 then return False
        # Use 'break' to exit this loop and go to next i
        # since this loop is at the end of the i loop.
        if x == n-1 then next i
    else:
        # This is only reached if no `break` occurred
        return False
return True

answered Jun 11, 2014 at 18:25

SethMMorton

49.5k13 gold badges72 silver badges90 bronze badges

3 Comments

tktk Over a year ago

if you break on the second next i you return False when you shouldn't.

SethMMorton Over a year ago

@TalKremerman How is that? The return statement will break out of the loop if it is reached, so that won't matter.

tktk Over a year ago

if x == n-1 you're supposed to go to the next i. If you simply break, you reach return False and you're not supposed to.

Collectives™ on Stack Overflow

Python: break out of multiple levels of loop

2 Answers 2

4 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related