Euclidean Algorithm (subtraction) in python

Question

In "Great Mathematical problems -- Vision of infinity", page 18 Ian Stewart referred Euclid's proposition 2, Book VII of Element which is a very elementary method of finding Greatest common divisor. I quote "It works by repeatedly subtracting the smaller number from the larger one, then applying a similar process to the resulting remainder and the smaller number, and continuing until there is no remainder." The example is with 630 and 135. 135 is repeadedly "subtracted"from 630 (495, 360, 225) and finally obtain 90 which is less than 135. So the numbers are inverted and 90 is repeatedly subtracted from 135 to have finally, 45. Then 45 is subtracted from 90 and finally obtain 0 yielding 45 the gcd. This is sometimes called Euclidean Algorithm of finding gcd.

To teach a beginner (a child of 10) I need to write the code in python. There should not be any function definition, neither it should use any other mathematical operation than subtraction. I want to use if/while/else/elif/continue/break. There should be provision that if three numbers (or more) are given, the whole program must be repeated deciding the smaller one. Earlier chain on gcd does not look the algorithm from this perspective.

Answer 1

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