Python Forum

Hello,

Here's a basic question.

a = 154
b = 42
d = 0
f = 0

for i in range(1,a):
    
   d =  round(a / i)
   
   print(d)
   
for s in range(1,b):
    
   f =  round(b / s)
   
   print("f",f)
 
if (d==f):

  print("D",f)

Common GCD is 14 but print "D" return only 1. I would of expect at least to list in output 14 , 8, 7, 6, 5, 4, 3 ,2 , 1 and then filter largest one 14.
But i only get 1?

Thank you

If you print "D" only once, it will be printed only once.

(Jan-10-2022, 03:22 PM)Gribouillis Wrote: [ -> ]If you print "D" only once, it will be printed only once.

That is not what i am asking. I want to know why Print("D", d) return only 1 when there is also 14 who are equals in F and D.

It prints only 1 because when you print("D", f) the value of the variable f is the last value that was assigned to f by a statement f = ..., and this last value turns out to be 1. Previous values of f are no longer available at that moment.

(Jan-10-2022, 04:09 PM)Gribouillis Wrote: [ -> ]It prints only 1 because when you print("D", f) the value of the variable f is the last value that was assigned to f by a statement f = ..., and this last value turns out to be 1. Previous values of f are no longer available at that moment.

My misunderstanding comes from the fact that if it was C#, thanks to the curly bracket both loops would be independant and print outside would return indenpendant numbers. I could use the if statement and C# would return 14 , 8, 7, 6, 5, 4, 3 ,2 , 1 .
But it does not seem to be the case with python. I tried a different approach and the same problem is coming back.

a = 154
b = 42
d = 0
f = 0

for (i,j) in zip(range(1,a),range(1,b)): 
    
  d =  round(a / i)
   
  print("d", d)
  
  f =  round(b / j)
   
  print("f", f)
  
if (f==d):

 print("GCD",f)

	

What am i suppose to do? Create a list of d and f and than filter the list to find GCD. Of course there are other way to get GCD but i always find solution with 30 lines. Is it me or Python consume a lot of lines?

Maybe you could show your working C# code. The problem you have above is that you are constantly setting d and f to different values. There is a time when d is 14 and when f is 14. But not at the same time. Since you don't store the values, you can't tell later that they were both present.

(Jan-10-2022, 04:31 PM)Frankduc Wrote: [ -> ]What am i suppose to do? /.../ Is it me or Python consume a lot of lines?

Python comes with battaries included so for GCD just:

+>>> import math
+>>> math.gcd(154, 42)
14

While using range keep in mind that in Python:

+>>> list(range(1, 4))
[1, 2, 3]

This test does not result in a denominator.

d =  round(a / i)

if a == 42, d will have values 1, 2, 3, 4, 5, 6, 7, 8, 10, 14, 21, 42. The problem is that 4, 5, 8 and 10 do not divide evenly into 42. The correct test is.

for i in range(1, a+1):
    if a % i == 0:
        d = i
        print(d)

This correctly prints 1, 2, 3, 6, 7, 14, 21, 42. But there is another problem.

Even if you correctly identified denominators your code has no way to test for commonality. After printing the denominators of 42 your code has d == 42 and after printing the denominators for 154 your code has f == 154. 42 does not equal 154, so GCD is never printed. This is not a problem caused by missing curly brackets or an ignorance of Python. This is a logic error.

If you were solving this problem with pencil and paper you might write down all the denominators for 42 and all the denominators for154 and look for numbers that appear in both lists. In Python this looks like this:

def denominators(x):
    """Returns list of denominators for x"""
    return [d for d in range(1, x+1) if x % d == 0]

def common_denominators(x, y):
    """Returns list of values appearing in both lists x and y"""
    return [d for d in x if d in y]

d42 = denominators(42)
d154 = denominators(154)
common = common_denominators(d42, d154)

print("42", d42)
print("154", d154)
print("common", common[-1], common)

Output:
42 [1, 2, 3, 6, 7, 14, 21, 42]
154 [1, 2, 7, 11, 14, 22, 77, 154]
common 14 [1, 2, 7, 14]

There are other ways to find what numbers are common to two lists using Python set operations. Set operations are a bit faster but as with most programming tasks the real speed improvement results from thinking about the problem and optimizing the procedure.

If you have two numbers 42 and 154 you know there are no common denominators greater than 42 and that computing denominators for numbers in the range 43 to 154 is a waste of time. It is also a waste of time testing if a number divides evenly into 154 if we know it does not divide evenly into 42. Putting some smart into the algorithm gives us this:

def common_denominators(x, y):
    if x > y:
        x, y = y, x  # Make x the smaller of the two numbers
    return [d for d in range(x, 0, -1) if x % d == 0 and y % d == 0]

print(common_denominators(42, 154))

Output:
[14, 7, 2, 1]

(Jan-10-2022, 06:55 PM)deanhystad Wrote: [ -> ]This test does not result in a denominator.

d =  round(a / i)

if a == 42, d will have values 1, 2, 3, 4, 5, 6, 7, 8, 10, 14, 21, 42. The problem is that 4, 8 and 10 do not divide evenly into 42. The correct test is.

for i in range(1, a+1):
    if a % i == 0:
        d = i
        print(d)

This correctly prints 1, 2, 3, 6, 7, 14, 21, 42. But there is another problem.

Even if you correctly identified denominators your code has no way to test for commonality. After printing the denominators of 42 your code has d == 42 and after printing the denominators for 154 your code has f == 154. 42 does not equal 154, so GCD is never printed. This is not a problem caused by missing curly brackets or an ignorance of Python. This is a logic error.

If you were solving this problem with pencil and paper you might write down all the denominators for 42 and all the denominators for154 and look for numbers that appear in both lists. In Python this looks like this:

def denominators(x):
    '''Returns list of denominators for x"""
    return [d for d in range(1, x+1) if x % d == 0]

def common_denominators(x, y):
    """Returns list of values appearing in both lists x and y"""
    return [d for d in x if d in y]

d42 = denominators(42)
d154 = denominators(154)
common = common_denominators(d42, d154)

print("42", d42)
print("154", d154)
print("common", common[-1], common)

Output:
42 [1, 2, 3, 6, 7, 14, 21, 42]
154 [1, 2, 7, 11, 14, 22, 77, 154]
common 14 [1, 2, 7, 14]

There are other ways to find what numbers are common to two lists using Python set operations. Set operations are a bit faster but as with most programming tasks the real speed improvement results from thinking about the problem and optimizing the procedure.

If you have two numbers 42 and 154 you know there are no common denominators greater than 42 and that computing denominators for numbers in the range 43 to 154 is a waste of time. It is also a waste of time testing if a number divides evenly into 154 if we know it does not divide evenly into 42. Putting some smart into the algorithm gives us this:

def common_denominators(x, y):
    if x > y:
        x, y = y, x  # Make x the smaller of the two numbers
    return [d for d in range(x, 0, -1) if x % d == 0 and y % d == 0]

print(common_denominators(42, 154))

Output:
[14, 7, 2, 1]

Very instructive. I like your approach.
Very helpful
Thank you

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.