3

Euclid's Algorithm for GCF of two numbers is: GCF(a, b)=GCF(b, a mod b). I have seen this implemented in Python as follows: 

def gcf(a, b):
    return b and gcf(b, a%b) or a

I don't understand how to parse this function or specifically how boolean logic is applied to integers. For example, gcf(42, 56) = 14. When I walk through it, I see that eventually the recursive part returns zero. I follow that 0 or n == n and 0 and n == 0. However, once I have a pair of non-zero integers being compared with and/or logic, I don't understand what happens and why.

Can someone walk me through this function?

Matthew Lundberg
  • 42,009
  • 6
  • 90
  • 112
Matt
  • 33
  • 3
  • 3
    possible duplicate of [How do "and" and "or" work when combined in one statement?](http://stackoverflow.com/questions/2579959/how-do-and-and-or-work-when-combined-in-one-statement) – Ignacio Vazquez-Abrams Dec 19 '10 at 02:36

4 Answers4

2

Python boolean operators 'or' and 'and' don't return boolean values. They return one of the values they are comparing.

0 or n - returns n

0 and n - returns 0

a and b or c is just a trick to implement the (a ? b : c) syntax in C.

Read section 4.6 of Dive into Python for a great description of python's boolean operations and this trick.

Sonny Saluja
  • 7,193
  • 2
  • 25
  • 39
  • 1
    @Matt - The section is not very long and definitely worth a read as this is a pretty common trick used in python. – Sonny Saluja Dec 19 '10 at 02:41
  • 1
    @Sanjit In earlier versions, anyway - in 2.5 and later, Python implements the ternary operator in the form 'b if a else c'. – Nick Johnson Dec 19 '10 at 03:25
  • @Nick: It's too bad they used such a horrible ternary syntax; it encourages people to keep using the error-prone boolean hack. It's by far the most nonsensical syntax in Python, shuffling the arguments around seemingly randomly and evaluating its arguments out-of-order. – Glenn Maynard Dec 19 '10 at 03:52
  • @Glenn I consider the form they decided upon to be eminently readable and unambiguous. Clauses coming out of order like that is common in English (and not even unprecedented in Python, either - when you see `[`, you don't know whether it will be a plain list or a comprehension until you get to either `]` or `for`), and nothing else really reads better except the if-then-else order, which breaks flow with the surrounding code. Anyway, anyone who wants to nerd out about this is hereby referred to http://www.python.org/dev/peps/pep-0308/ wherein the decision process is recorded. – Karl Knechtel Dec 19 '10 at 05:07
  • @Karl: I don't know what "breaks flow with surrounding code" means: `cars = traffic()? 100:10;` flows naturally, where in Python the results are put as far apart as possible instead of right next to each other, and I invariably have to read the expression twice, essentially backtracking my mental parser. (Thankfully, Python doesn't have anything like the `y if x;` atrocity found in some languages, which unlike ternary expressions end up being used a lot.) – Glenn Maynard Dec 19 '10 at 06:34
  • @Glenn the simplest argument I can think of here: beginners who mean `[f(x) for x in y if g(x)]`, and don't know the syntax for it, mistakenly write `[f(x) if g(x) for x in y]` all the time, but write `[if g(x) f(x) for x in y]` or `[if g(x) then f(x) for x in y]` approximately never. The idea of writing a conditional result before the condition is actually quite normal in English, if perhaps more common in legalese. – Karl Knechtel Dec 20 '10 at 12:02
  • @Karl: English is hardly a model for designing a consistent, logical programming language. – Glenn Maynard Dec 20 '10 at 17:05
1

In your case, the call stack will look like this:

gcf(42, 56)
gcf(56, 42) // since b was non-zero, will recurse and pass 42 % 56 (=42) as second arg
gcf(42, 14) // since b was non-zero, will recurse and pass 56 % 42 (=14) as second arg
gcf(14, 0) // since b was non-zero, will recurse and pass 42 % 14 (=0) as second arg
return a // since b was zero, will just return a (14)

This will pop all the way to the top. In python, the and will return the number and not a boolean, which is why popping up returns the result and not a 1/true.

Mike V.
  • 11
  • 2
1

However, once I have a pair of non-zero integers being compared with and/or logic, I don't understand what happens and why.

What happens is that the first value that affects the result is returned.

x or y -> evaluates to x whenever code in an if x: block would run, and otherwise evaluates to y.

x and y -> evaluates to x whenever code in an if x: block would not run, and otherwise evaluates to y.

Why that happens is because GvR said so. It might, possibly, have been precisely to make this trick work, back before the x if C else y construct was added to the language.

But, you know... you could have just tested it for yourself. That's what the REPL is for :)

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
  • The problem with self-testing is that without an understanding of the underlying reasoning, there's a risk that things still don't work out as desired. Granted, enough testing can shrink that probability to something very small, but it's still there. Also, to use this kind of construct in my own code, I wanted to understand it. Thanks! – Matt Dec 19 '10 at 15:38
0

If b is not equal to zero then the result is gcf(b, a%b) (recurse). If b is equal to zero then the result is a.

President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
  • OP understands perfectly well how the GCF algorithm works and is seeking an understanding of how the `and` and `or` keywords work in Python when applied to non-booleans. – Karl Knechtel Dec 19 '10 at 05:08