Какой алгоритм Python использует в fractions.gcd ()?

Question

Какой алгоритм Python использует в fractions.gcd ()?

Я использую модуль частей в Python v3.1 для вычислений наибольшего общего делителя. Я хотел бы знать, какой алгоритм используется. Я предполагаю Евклидов метод, но хотел бы быть уверенным. Документы (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) не помогают. Может кто-либо подсказка меня в?

11

python fractions greatest-common-divisor

задан kennytm 25 November 2010 в 09:20

1 ответ

Другие вопросы по тегам:

python fractions greatest-common-divisor

Похожие вопросы:

score 20 · Accepted Answer

Согласно исходному коду 3.1.2 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.