क्या एल्गोरिदम phederon fractions.gcd() में नियोजित करता है?

Question

मैं सबसे बड़ा आम divisor गणना करने के लिए पायथन v3.1 में अंश मॉड्यूल का उपयोग कर रहा हूँ। मैं जानना चाहता हूं कि एल्गोरिदम का क्या उपयोग किया जाता है। मैं यूक्लिडियन विधि का अनुमान लगा रहा हूं, लेकिन यह सुनिश्चित करना चाहता हूं। दस्तावेज़ (http://docs.python.org/py3k/library/fractions.html?highlight=fractions.gcd#fractions.gcd) मदद नहीं करते हैं। क्या कोई मुझे अंदर जोड़ सकता है?

Answer 1

the 3.1.2 source code 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 

तो हाँ, यह इयूक्लिडियन एल्गोरिथ्म, शुद्ध पायथन में लिखा है।