find 2 largest equal numbers

[Frankduc]

Though short my solution is far from efficient. Given my two numbers 42 and 154 I know for sure that there will not be any common denominators in the range 22 to 41 or the range 15 to 20 or... My quick and dirty works fine if one of the numbers if fairly small, but there is a lot of needless division going on and this could result in long delays if both of your numbers are large.

Division is costly, so if you can do fewer divisions your algorithm is going to run faster. The 30 line GCD program you mention is probably using Stein's algorithm. Steins algorithm replaces division with shifts and subtraction. This requires a lot of testing to determine the next step in the algorithm, but you can do a lot of if statements in the time it takes to do 1 division.

Or maybe you saw Euclid's algorithm. Euclid's algorithm still does division, but is more efficient because it does less of it. But I don't think I've ever seen an implementation of Euclid's algorithm that is 30 lines long. Normally the code is pretty short.

def gcd(a, b):
  if b == 0:
    return a:
  else:
    return gcd(b, (a % b))

Or even shorter

def gcd(a, b):
    return a if b == 0 else gcd(b, (a % b))

Though this does less division than my example it does use recursion, so some of the performance gains are lost. It also doesn't generate a list or common denominators, just the greatest common denominator.

Hello deanhystad,

I think you meant:

def gcd(a, b):
  if b == 0:
    return a     //instead of return a:
  else:
    return gcd(b, (a % b))
    
print(gcd(12, 4))

There is many ways to get the gcd in math, at least 3 ways. I am practicing on GFG https://www.geeksforgeeks.org/practice-f...w/?ref=grb
Trying to find the most efficient way to code these problems. I am starting a one year program in AI in february and even if they will teach us python i am trying to get ahead. I dont want to struggle when they will be teaching us the A*, Min/Max, Greedy and all the rest.

Reading on teaching website does not give you all the details of how the arguments are processed in the code. For example, in return gcd(b, (a % b)) you can calculate by yourself a%b using a calculator with modulo. No where it tells you what b, (a%b) returns.

Anyway thanks for the explanation.