pythonfractionsgreatest-common-divisor

What algorithm does Python employ in fractions.gcd()?


I'm using the fractions module in Python v3.1 to compute the greatest common divisor. I would like to know what algorithm is used. I'm guessing the Euclidean method, but would like to be sure. The docs (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) don't help. Can anybody clue me in?


Solution

  • According to the 3.1.2 source code online, here's gcd as defined in 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
    

    So yes, it's the Euclidean algorithm, written in pure Python.