What algorithm does Python employ in fractions.gcd()?
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.
From fractions python
"Deprecated since version 3.5: Use math.gcd() instead."
I was looking for the algorithm as well. I hope it helped.