Nate Nate - 1 month ago 27
Python Question

iteration counter for GCD

I have the following code for calulating the GCD of two numbers:

def gcd(m, n):
r = m % n
while r != 0:
m = n
n = r
r = m % n
return n

print ("\n", "gcd (10, 35) = ", gcd(10, 35))

print ("\n", "gcd (735, 175) = ", gcd(735, 175))

print ("\n", "gcd (735, 350) = ", gcd(735, 350))


I would like to count the number of iterations that the algorithm has to go through before finding the GCD. I am having trouble making a for loop to determine the number of iterations.

Answer
def gcd(m, n):
   r = m % n
   counter = 0
   while r != 0:
      m = n
      n = r
      r = m % n
      counter += 1
   return n, counter