Scribd
Upload
52 views17 pages

Python Recap - III: Madhavan Mukund

The document discusses algorithms for computing the greatest common divisor (GCD) of two numbers. It first presents a naive method that takes time proportional to the smaller of the two numbers. An iterative recursive method is then proposed that takes time proportional to the larger number. Finally, Euclid's algorithm is presented, which recursively computes the GCD in time proportional to the number of digits in the larger number, providing a more efficient solution.

Uploaded by

Harsh Rawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
52 views17 pages

Python Recap - III: Madhavan Mukund

The document discusses algorithms for computing the greatest common divisor (GCD) of two numbers. It first presents a naive method that takes time proportional to the smaller of the two numbers. An iterative recursive method is then proposed that takes time proportional to the larger number. Finally, Euclid's algorithm is presented, which recursively computes the GCD in time proportional to the number of digits in the larger number, providing a more efficient solution.

Uploaded by

Harsh Rawat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

Python Recap – III

Madhavan Mukund
https://www.cmi.ac.in/~madhavan

Programming, Data Structures and Algorithms using Python


Week 1
Computing gcd

Both versions of gcd take time


def gcd(m,n):
proportional to min(m, n)
cf = [] # List of common factors
Can we do better? for i in range(1,min(m,n)+1):
if (m%i) == 0 and (n%i) == 0:
cf.append(i)
return(cf[-1])

def gcd(m,n):
for i in range(1,min(m,n)+1):
if (m%i) == 0 and (n%i) == 0:
mrcf = i
return(mrcf)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 2/4
Computing gcd

Both versions of gcd take time


def gcd(m,n):
proportional to min(m, n)
cf = [] # List of common factors
Can we do better? for i in range(1,min(m,n)+1):
if (m%i) == 0 and (n%i) == 0:
Suppose d divides m and n cf.append(i)
m = ad, n = bd return(cf[-1])
m − n = (a − b)d
d also divides m − n def gcd(m,n):
for i in range(1,min(m,n)+1):
if (m%i) == 0 and (n%i) == 0:
mrcf = i
return(mrcf)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 2/4
Computing gcd

Both versions of gcd take time


def gcd(m,n):
proportional to min(m, n)
(a,b) = (max(m,n), min(m,n))
Can we do better? if a%b == 0:
return(b)
Suppose d divides m and n else
m = ad, n = bd return(gcd(b,a-b))
m − n = (a − b)d
d also divides m − n

Recursively defined function


Base case: n divides m, answer is n
Otherwise, reduce gcd(m, n) to
gcd(n, m − n)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 2/4
Computing gcd

Unfortunately, this takes time


def gcd(m,n):
proportional to max(m, n)
(a,b) = (max(m,n), min(m,n))
if a%b == 0:
return(b)
else
return(gcd(b,a-b))

Madhavan Mukund Python Recap – III PDSA using Python Week 1 3/4
Computing gcd

Unfortunately, this takes time


def gcd(m,n):
proportional to max(m, n)
(a,b) = (max(m,n), min(m,n))
Consider gcd(2,9999) if a%b == 0:
→ gcd(2,9997)
return(b)
else
→ gcd(2,9995)
return(gcd(b,a-b))
...
→ gcd(2,3)
→ gcd(2,1)
→1

Madhavan Mukund Python Recap – III PDSA using Python Week 1 3/4
Computing gcd

Unfortunately, this takes time


def gcd(m,n):
proportional to max(m, n)
(a,b) = (max(m,n), min(m,n))
Consider gcd(2,9999) if a%b == 0:
→ gcd(2,9997)
return(b)
else
→ gcd(2,9995)
return(gcd(b,a-b))
...
→ gcd(2,3)
→ gcd(2,1)
→1

Approximately 5000 steps

Madhavan Mukund Python Recap – III PDSA using Python Week 1 3/4
Computing gcd

Unfortunately, this takes time


def gcd(m,n):
proportional to max(m, n)
(a,b) = (max(m,n), min(m,n))
Consider gcd(2,9999) if a%b == 0:
→ gcd(2,9997)
return(b)
else
→ gcd(2,9995)
return(gcd(b,a-b))
...
→ gcd(2,3)
→ gcd(2,1)
→1

Approximately 5000 steps


Can we do better?
Madhavan Mukund Python Recap – III PDSA using Python Week 1 3/4
Euclid’s algorithm

Suppose n does not divide m

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


Then m = qn + r

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


Then m = qn + r
Suppose d divides both m and n

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


Then m = qn + r
Suppose d divides both m and n
Then m = ad, n = bd

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


Then m = qn + r
Suppose d divides both m and n
Then m = ad, n = bd
m = qn + r → ad = q(bd) + r

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


Then m = qn + r
Suppose d divides both m and n
Then m = ad, n = bd
m = qn + r → ad = q(bd) + r
r must be of the form cd

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


def gcd(m,n):
Then m = qn + r (a,b) = (max(m,n), min(m,n))
if a%b == 0:
Suppose d divides both m and n return(b)
Then m = ad, n = bd else
return(gcd(b,a%b))
m = qn + r → ad = q(bd) + r
r must be of the form cd
Euclid’s algorithm
If n divides m, gcd(m, n) = n
Otherwise, compute gcd(n, m mod n)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


def gcd(m,n):
Then m = qn + r (a,b) = (max(m,n), min(m,n))
if a%b == 0:
Suppose d divides both m and n return(b)
Then m = ad, n = bd else
return(gcd(b,a%b))
m = qn + r → ad = q(bd) + r
Can show that this takes time
r must be of the form cd
proportional to number of digits in
Euclid’s algorithm max(m, n)
If n divides m, gcd(m, n) = n
Otherwise, compute gcd(n, m mod n)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4
Euclid’s algorithm

Suppose n does not divide m


def gcd(m,n):
Then m = qn + r (a,b) = (max(m,n), min(m,n))
if a%b == 0:
Suppose d divides both m and n return(b)
Then m = ad, n = bd else
return(gcd(b,a%b))
m = qn + r → ad = q(bd) + r
Can show that this takes time
r must be of the form cd
proportional to number of digits in
Euclid’s algorithm max(m, n)
If n divides m, gcd(m, n) = n One of the first non-trivial algorithms
Otherwise, compute gcd(n, m mod n)

Madhavan Mukund Python Recap – III PDSA using Python Week 1 4/4

You might also like