Python Recap – I
Madhavan Mukund
https://www.cmi.ac.in/~madhavan
Programming, Data Structures and Algorithms using Python
Week 1
Computing gcd
gcd(m, n) — greatest common divisor
Largest k that divides both m and n
gcd(8, 12) = 4
gcd(18, 25) = 1
Also hcf — highest common factor
Madhavan Mukund Python Recap – I PDSA using Python Week 1 2/4
Computing gcd
gcd(m, n) — greatest common divisor
Largest k that divides both m and n
gcd(8, 12) = 4
gcd(18, 25) = 1
Also hcf — highest common factor
gcd(m, n) always exsits
1 divides both m and n
Madhavan Mukund Python Recap – I PDSA using Python Week 1 2/4
Computing gcd
gcd(m, n) — greatest common divisor
Largest k that divides both m and n def gcd(m,n):
gcd(8, 12) = 4 cf = [] # List of common factors
for i in range(1,min(m,n)+1):
gcd(18, 25) = 1
if (m%i) == 0 and (n%i) == 0:
Also hcf — highest common factor cf.append(i)
gcd(m, n) always exsits return(cf[-1])
1 divides both m and n
Computing gcd(m, n)
gcd(m, n) ≤ min(m, n)
Compute list of common factors from
1 to min(m, n)
Return the last such common factor
Madhavan Mukund Python Recap – I PDSA using Python Week 1 2/4
Computing gcd
Points to note
def gcd(m,n):
Need to initialize cf for cf.append()
cf = [] # List of common factors
to work
for i in range(1,min(m,n)+1):
Variables (names) derive their type if (m%i) == 0 and (n%i) == 0:
from the value they hold cf.append(i)
return(cf[-1])
Madhavan Mukund Python Recap – I PDSA using Python Week 1 3/4
Computing gcd
Points to note
def gcd(m,n):
Need to initialize cf for cf.append()
cf = [] # List of common factors
to work
for i in range(1,min(m,n)+1):
Variables (names) derive their type if (m%i) == 0 and (n%i) == 0:
from the value they hold cf.append(i)
Control flow return(cf[-1])
Conditionals (if)
Loops (for)
Madhavan Mukund Python Recap – I PDSA using Python Week 1 3/4
Computing gcd
Points to note
def gcd(m,n):
Need to initialize cf for cf.append()
cf = [] # List of common factors
to work
for i in range(1,min(m,n)+1):
Variables (names) derive their type if (m%i) == 0 and (n%i) == 0:
from the value they hold cf.append(i)
Control flow return(cf[-1])
Conditionals (if)
Loops (for)
range(i,j) runs from i to j-1
Madhavan Mukund Python Recap – I PDSA using Python Week 1 3/4
Computing gcd
Points to note
def gcd(m,n):
Need to initialize cf for cf.append()
cf = [] # List of common factors
to work
for i in range(1,min(m,n)+1):
Variables (names) derive their type if (m%i) == 0 and (n%i) == 0:
from the value they hold cf.append(i)
Control flow return(cf[-1])
Conditionals (if)
Loops (for)
range(i,j) runs from i to j-1
List indices run from 0 to len(l) - 1
and backwards from -1 to -len(l)
Madhavan Mukund Python Recap – I PDSA using Python Week 1 3/4
Computing gcd
Eliminate the list
def gcd(m,n):
Only the last value of cf is important
cf = [] # List of common factors
for i in range(1,min(m,n)+1):
if (m%i) == 0 and (n%i) == 0:
cf.append(i)
return(cf[-1])
Madhavan Mukund Python Recap – I PDSA using Python Week 1 4/4
Computing gcd
Eliminate the list
def gcd(m,n):
Only the last value of cf is important
for i in range(1,min(m,n)+1):
Keep track of most recent common if (m%i) == 0 and (n%i) == 0:
factor (mrcf) mrcf = i
return(mrcf)
Madhavan Mukund Python Recap – I PDSA using Python Week 1 4/4
Computing gcd
Eliminate the list
def gcd(m,n):
Only the last value of cf is important
for i in range(1,min(m,n)+1):
Keep track of most recent common if (m%i) == 0 and (n%i) == 0:
factor (mrcf) mrcf = i
return(mrcf)
Recall that 1 is always a common
factor
No need to initialize mrcf
Madhavan Mukund Python Recap – I PDSA using Python Week 1 4/4
Computing gcd
Eliminate the list
def gcd(m,n):
Only the last value of cf is important
for i in range(1,min(m,n)+1):
Keep track of most recent common if (m%i) == 0 and (n%i) == 0:
factor (mrcf) mrcf = i
return(mrcf)
Recall that 1 is always a common
factor
def gcd(m,n):
No need to initialize mrcf cf = [] # List of common factors
Efficiency for i in range(1,min(m,n)+1):
Both versions of gcd take time if (m%i) == 0 and (n%i) == 0:
proportional to min(m, n) cf.append(i)
return(cf[-1])
Madhavan Mukund Python Recap – I PDSA using Python Week 1 4/4
Computing gcd
Eliminate the list
def gcd(m,n):
Only the last value of cf is important
for i in range(1,min(m,n)+1):
Keep track of most recent common if (m%i) == 0 and (n%i) == 0:
factor (mrcf) mrcf = i
return(mrcf)
Recall that 1 is always a common
factor
def gcd(m,n):
No need to initialize mrcf cf = [] # List of common factors
Efficiency for i in range(1,min(m,n)+1):
Both versions of gcd take time if (m%i) == 0 and (n%i) == 0:
proportional to min(m, n) cf.append(i)
return(cf[-1])
Can we do better?
Madhavan Mukund Python Recap – I PDSA using Python Week 1 4/4
