[Solved] Euclidean Algorithm (subtraction) in python

by


A typical fast solution to the gcd algorithm would be some iterative version like this one:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)

    return x

In fact, in python you’d just use directly the gcd function provided by fractions module.

And if you wanted such function to deal with multiple values you’d just use reduce:

reduce(gcd,your_array)

Now, it seems you want to constrain yourself to use only loops+substractions so one possible solution to deal with x,y positive integers would be this:

def gcd_unopt(x, y):
    print x,y

    while x!=y:
        while x>y:
            x -= y
            print x,y
        while y>x:
            y -= x
            print x,y

    return x

print reduce(gcd_unopt,[630,135])

Not sure why you wanted to avoid using functions, gcd is a function by definition, even so, that’s simple, just get rid of the function declaration and use the parameters as global variables, for instance:

x = 630
y = 135

print x,y

while x!=y:
    while x>y:
        x -= y
        print x,y
    while y>x:
        y -= x
        print x,y

4

solved Euclidean Algorithm (subtraction) in python