Quel algorithme utilise Python dans fractions.gcd()?

Question

J'utilise le module fractions dans Python v3.1 pour calculer le plus grand commun diviseur. Je voudrais savoir quel algorithme est utilisé. Je devine la méthode euclidienne, mais je voudrais être sûr. Les docs (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) n'aident pas. Quelqu'un peut-il m'indiquer?

Answer 1

Selon the 3.1.2 source code online, voici gcd tel que défini dans 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 

Alors oui, il est l'algorithme d'Euclide, écrit en Python pur.