Python在fractions.gcd()中采用了什么算法？

Question

我使用Pythonv3.1中的分数模块来计算最大公约数。我想知道使用的是什么算法。我猜是欧几里得方法，但我想确认一下。文档(http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd)帮不上忙。有人能给我提供线索吗？

Answer 1

根据the 3.1.2 source code online的说法，下面是在Python-3.1.2/Lib/fractions.py中定义的gcd

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编写的。

Answer 2

来自fractions python

“自3.5版起不推荐使用:请改用math.gcd()。”

我也在寻找算法。我希望它能帮上忙。