python - Python 在 fractions.gcd() 中使用了什么算法？

Question

我正在使用 Python v3.1 中的分数模块来计算最大公约数。我想知道使用什么算法。我猜是欧几里得方法，但想确定一下。文档（http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd）没有帮助。任何人都可以提示我吗？

Answer 1

根据网上的3.1.2源码，这里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 编写的欧几里得算法。

Answer 2

从分数 python

“自 3.5 版起已弃用：改用 math.gcd()。”

我也在寻找算法。我希望它有所帮助。