find 2 largest equal numbers

[Gribouillis]

@deanhystad More interesting is the extended Euclide algorithm which produces two integers u and v such that a * u + b * v = gcd(a, b)

[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.

[ibreeden]

As Deanhystad already said, for large numbers lack of efficiency can become a problem of this algorithm and he showed some enhancements. And Gribouillis already hinted to the extended Euclide algorithm.

I found an enhancement that is quite easy to explain. It is based on the fact that when you find that 42 is divisible by 2, you also know 42 is divisible by (42 / 2 =) 21. You have so to say two answers in one strike: one to add to the head of the result set and one to the tail.
And thinking this over there is no need to test all numbers in range(1, 42+1). Because: when you found that 21 is the first denominator below 42, then you do not have to test the range(22, 42+1).
Looking careful at this, you will notice you can stop checking numbers as soon as the head (low number) passes the tail (high number).

def denominators(x: int) -> set:
    """ Returns set of denominators for x . """
    result = set()
    for low_value in range(1, x):
        high_value = x // low_value
        # If the low_value exceeds the high_value there is no need to continue.
        if low_value > high_value:
            print("DEBUG finishing at: ", low_value)
            break
        else:
            if x % low_value == 0:
                result.add(low_value)
                result.add(high_value)
                print("DEBUG add: ", low_value, high_value)
    print("DEBUG return: ", result)
    return result

When testing this with 42 and a somewat larger number (10.003) you can see how it works.

a = 42
b = 10003
denom_a = denominators(a)
denom_b = denominators(b)
print(a, denom_a)
print(b, denom_b)
print("Common: ", denom_a & denom_b)

Output:
DEBUG add:  1 42
DEBUG add:  2 21
DEBUG add:  3 14
DEBUG add:  6 7
DEBUG finished at:  7
DEBUG return:  {1, 2, 3, 6, 7, 42, 14, 21}

DEBUG add:  1 10003
DEBUG add:  7 1429
DEBUG finished at:  101
DEBUG return:  {1, 10003, 1429, 7}

42 {1, 2, 3, 6, 7, 42, 14, 21}
10003 {1, 10003, 1429, 7}

Common:  {1, 7}

Here you can see the analysis of the first number finishes at 7 because this would result in the pair {7, (42/7=)6} but we already had that pair when the loop variable was 6: {6, (42/6=)7}.

In the second example you can see the numbers to be inspected is dramatically decreased, it finishes when the loop variable reaches 101, long before the end (10.003) is reached.

By the way @Frankduc , I am still curious about your C# program.

[Frankduc]

As Deanhystad already said, for large numbers lack of efficiency can become a problem of this algorithm and he showed some enhancements. And Gribouillis already hinted to the extended Euclide algorithm.

I found an enhancement that is quite easy to explain. It is based on the fact that when you find that 42 is divisible by 2, you also know 42 is divisible by (42 / 2 =) 21. You have so to say two answers in one strike: one to add to the head of the result set and one to the tail.
And thinking this over there is no need to test all numbers in range(1, 42+1). Because: when you found that 21 is the first denominator below 42, then you do not have to test the range(22, 42+1).
Looking careful at this, you will notice you can stop checking numbers as soon as the head (low number) passes the tail (high number).

def denominators(x: int) -> set:
    """ Returns set of denominators for x . """
    result = set()
    for low_value in range(1, x):
        high_value = x // low_value
        # If the low_value exceeds the high_value there is no need to continue.
        if low_value > high_value:
            print("DEBUG finishing at: ", low_value)
            break
        else:
            if x % low_value == 0:
                result.add(low_value)
                result.add(high_value)
                print("DEBUG add: ", low_value, high_value)
    print("DEBUG return: ", result)
    return result

When testing this with 42 and a somewat larger number (10.003) you can see how it works.

a = 42
b = 10003
denom_a = denominators(a)
denom_b = denominators(b)
print(a, denom_a)
print(b, denom_b)
print("Common: ", denom_a & denom_b)

Output:
DEBUG add:  1 42
DEBUG add:  2 21
DEBUG add:  3 14
DEBUG add:  6 7
DEBUG finished at:  7
DEBUG return:  {1, 2, 3, 6, 7, 42, 14, 21}

DEBUG add:  1 10003
DEBUG add:  7 1429
DEBUG finished at:  101
DEBUG return:  {1, 10003, 1429, 7}

42 {1, 2, 3, 6, 7, 42, 14, 21}
10003 {1, 10003, 1429, 7}

Common:  {1, 7}

Here you can see the analysis of the first number finishes at 7 because this would result in the pair {7, (42/7=)6} but we already had that pair when the loop variable was 6: {6, (42/6=)7}.

In the second example you can see the numbers to be inspected is dramatically decreased, it finishes when the loop variable reaches 101, long before the end (10.003) is reached.

By the way @Frankduc , I am still curious about your C# program.

Your suggestion is not very far from my first attempt. You can see the same principal applied here with 2 while loop (less efficent):

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])
print("1NUM",num1_list)
print("2Num",num2_list)
print("xy",xy)
print("GCD",max(xy))

But considering the number of lines it still better than GFG solution:

def gcd(a, b):
  
    # Everything divides 0
    if (a == 0):
        return b
    if (b == 0):
        return a
  
    # base case
    if (a == b):
        return a
  
    # a is greater
    if (a > b):
        return gcd(a-b, b)
    return gcd(a, b-a)
  
# Driver program to test above function
a = 156
b = 56
if(gcd(a, b)):
    print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
    print('not found')

You wonder why so many if and else just to end up with:

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

In the end its how the coder see the problem that dictate the approach.

For the C# its the same code as above, i was just trying to find a way to cross the list with : list(set(num1_list).intersection(num2_list)) i just did not know how. Amusing thing by searching i have found so many ways to intersect the lists.

Right now i am analyzing adding fraction from GFG and their solution make my head spin:

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


def lowest(den3, num3): 

   
    common_factor = gcd(num3, den3); 

  
    den3 = int(den3 / common_factor); 
    num3 = int(num3 / common_factor);
    print(num3, "/", den3);


def addFraction(num1, den1, num2, den2): 

   
    den3 = gcd(den1, den2); 

    den3 = (den1 * den2) / den3; 
    num3 = ((num1) * (den3 / den1) + 
            (num2) * (den3 / den2)); 

    
    lowest(den3, num3); 

num1 = 1; den1 = 500; 
num2 = 2; den2 = 1500; 

print(num1, "/", den1, " + ", num2, "/", 
      den2, " is equal to ", end = ""); 
addFraction(num1, den1, num2, den2);

I mean in my head it is more simple to just use the den and num multiplication and then reduce the fraction:

from fractions import Fraction

f1_nume = int(input('Enter the numerator for 1st fraction :'))
f1_deno = int(input('Enter the denominator for the 1st fraction :'))
f2_nume = int(input('Enter the numerator for 2nd fraction :'))
f2_deno = int(input('Enter the denominator for the 2nd fraction :'))

if(f1_deno == f2_deno):
  
    fraction = f1_nume + f2_nume
  
    print('Addition of two fractions are :' + str(Fraction) + '/' + str(f1_deno))

else:
   
    fraction = (f1_nume * f2_deno) + (f2_nume * f1_deno)
    print('Addition of fractions are :' + str(fraction) + '/' + str(f1_deno * f2_deno))
    
    print(Fraction(fraction, (f1_deno * f2_deno)))

Anyway the better you master python the more efficient is your code. Since i am as competent in C# than Python, i still got a lot of learning to do.