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

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 utiliza. 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. ¿Alguien puede darme una pista?

De acuerdo con el código fuente 3.1.2 en línea , 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 euclidiano, escrito en Python puro.

De las fracciones de python

“En desuso desde la versión 3.5: use math.gcd () en su lugar.”

También estaba buscando el algoritmo. Espero que haya ayudado.