1

Update: Once I don't know 3 %4 =0 ...

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

I think it works like this:

gcd(3,4) => while 4: => 3,4 = 4, 3%4 =>
David Greydanus
  • 2,551
  • 1
  • 23
  • 42
iljyya
  • 451
  • 1
  • 5
  • 8
  • 10
    That is an implementation of [Euclid's Algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm). Are you unclear on the Python code's details, or the algorithm itself? – Blckknght Feb 21 '13 at 04:01
  • *Extended* Euclidean Algorithm - best algorithm ever! (Yes, it does have a practical application within the context of RSA encryption.) – xxmbabanexx Feb 21 '13 at 04:19

2 Answers2

6

Let's walk through this step-by-step.

def gcd(a, b):

This defines a new function gcd which uses the variables a and b in its calculations. These values must be set before the function begins.

while b:

Unless a number is equivalent to 0, it is thought of as true. So, if b = 0, then this part of the code will not execute.

 a, b = b, a%b

For clarity, I am going to expand this to two lines.

a = b
b = a%b

The first part is rather self explanatory - the second is decidedly not. a%b is a python expression for a (mod b) Modulo's are mathematical functions which, at their most basic state, return the remainder of two numbers. For instance, 12%5 = 2; the remainder of 12/5is 2.

When writing the actual code though, make sure to keep them on the same line. "In one line the assignments happen at the same time (courtesy of tuple packing and unpacking). In two lines the assignments happen one after the other, which gives an incorrect answer (b will always be 0)" - Tim

Those lines repeat indefinitely until the variable b is equivalent to 0. After that, the code executes this:

return a

That returns the value a to the rest of the program, so that it can be used later on. It also ends the function.

To read more about Euclid's Equation (And... since I love cryptography and math, the 'Extended' edition) go to this Wikipedia page.

I hope that this was helpful!

Community
  • 1
  • 1
xxmbabanexx
  • 8,256
  • 16
  • 40
  • 60
  • 4
    Just as a note, in practice you can't split `a, b = b, a%b` into two lines like that. – Tim Feb 21 '13 at 04:57
  • I appreciate your help so much! – iljyya Feb 21 '13 at 15:35
  • @tim Why are you not able to do that? Aren't they fundamentally the same thing? – xxmbabanexx Feb 22 '13 at 00:46
  • @xxmbabanexx: They are not the same thing. In one line the assignments happen at the same time (courtesy of tuple packing and unpacking). In two lines the assignments happen one after the other, which gives an incorrect answer (`b` will always be `0`). – Tim Feb 22 '13 at 21:06
  • @tim great - thanks for the help. I quoted that comment in my answer - I hope that that is ok with you. – xxmbabanexx Feb 22 '13 at 21:46
1

Here is a recursive version of the gcd function.

def gcd(a, b):
    c = a%b
    if c == 0:
        return b
    return gcd(b, c)
David Greydanus
  • 2,551
  • 1
  • 23
  • 42