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（）を使用してください。」

アルゴリズムも探していました。お役に立てば幸いです。