Python hangi algoritmayı fractions.gcd() içinde kullanıyor?

Question

En yaygın ortak ayırıcıyı hesaplamak için Python v3.1'deki kesir modülünü kullanıyorum. Hangi algoritmanın kullanıldığını bilmek isterim. Ben Euclidean yöntemini tahmin ediyorum ama emin olmak isterim. Dokümanlar (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) yardımcı olmuyor. Beni kimseye bağlayabilir mi?

Answer 1

the 3.1.2 source code online göre, burada Python-3.1.2/Lib/fractions.py tanımlanan gcd var:

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 

Yani evet, saf Python ile yazılmış Öklit algoritması, bu.