Python在fractions.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。