What algorithm does Python employ in fractions.gcd()?

According to the 3.1.2 source code online, here's gcd as defined in Python-3.1.2/Lib/fractions.py:

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

So yes, it's the Euclidean algorithm, written in pure Python.


From fractions python

"Deprecated since version 3.5: Use math.gcd() instead."

I was looking for the algorithm as well. I hope it helped.