¿Qué algoritmo emplea Python en fractions.gcd()?

Question

Estoy usando el módulo de fracciones en Python v3.1 para calcular el mayor divisor común. Me gustaría saber qué algoritmo se usa. Estoy adivinando el método euclidiano, pero me gustaría estar seguro. Los documentos (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) no ayudan. ¿Puede alguien darme alguna pista?

Answer 1

Según the 3.1.2 source code online, aquí está gcd como se define en 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 

Así que sí, es el algoritmo de Euclides, escrito en Python puro.