Какой алгоритм использует Python во фракциях.gcd()?

Question

Я использую модуль фракций в Python v3.1 для вычисления наибольшего общего делителя. Я хотел бы знать, какой алгоритм используется. Я догадываюсь об эвклидовом методе, но хочу быть уверенным. Документы (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) не помогают. Может кто-нибудь подскажет мне?

Answer 1

Согласно the 3.1.2 source code online, вот gcd, как определено в 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 

Так что да, это алгоритм Евклида, написанный на чистом Python.