Can't understand codes for "def gcd()"

Question

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 => 

Answer 1

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!

Answer 2

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)