Scribd
Upload
17 views

Nptel Mooc: Programming, Data Structures and Algorithms in Python

Uploaded by

Manab kumar Jena
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
17 views

Nptel Mooc: Programming, Data Structures and Algorithms in Python

Uploaded by

Manab kumar Jena
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/ 11

NPTEL MOOC

PROGRAMMING, 

DATA STRUCTURES AND
ALGORITHMS IN PYTHON
Week 1, Lecture 3

Madhavan Mukund, Chennai Mathematical Institute


http://www.cmi.ac.in/~madhavan
Algorithm for gcd(m,n)

To find the largest common factor, start at the end


and work backwards

Let i run from min(m,n) to 1

First common factor that we find will be gcd!


Euclid’s algorithm

Suppose d divides both m and n, and m > n

Then m = ad, n = bd

So m-n = ad - bd = (a-b)d

d divides m-n as well!

So gcd(m,n) = gcd(n,m-n)
Euclid’s algorithm

Consider gcd(m,n) with m > n

If n divides m, return n

Otherwise, compute gcd(n,m-n) and return that


value
Euclid’s algorithm
def gcd(m,n):
# Assume m >= n

if m < n:

(m,n) = (n,m)


if (m%n) == 0:

return(n)

else:

diff = m-n
# diff > n? Possible!

return(gcd(max(n,diff),min(n,diff))
Euclid’s algorithm, again
def gcd(m,n):

if m < n: # Assume m >= n



(m,n) = (n,m)



while (m%n) != 0:

diff = m-n

# diff > n? Possible!

(m,n) = (max(n,diff),min(n,diff))

return(n)
Even better
Suppose n does not divide m

Then m = qn + r, where q is the quotient, r is the


remainder when we divide m by n

Assume d divides both m and n

Then m = ad, n = bd

So ad = q(bd) + r

It follows that r = cd, so d divides r as well


Euclid’s algorithm

Consider gcd(m,n) with m > n

If n divides m, return n

Otherwise, let r = m%n

Return gcd(n,r)
Euclid’s algorithm
def gcd(m,n):

if m < n: # Assume m >= n



(m,n) = (n,m)



if (m%n) == 0:

return(n)

else:

return(gcd(n,m%n)) # m%n < n, always!
Euclid’s algorithm, revisited

def gcd(m,n):

if m < n: # Assume m >= n



(m,n) = (n,m)



while (m%n) != 0:

(m,n) = (n,m%n) # m%n < n, always!



return(n)
Efficiency

Can show that the second version of Euclid’s


algorithm takes time proportional to the number of
digits in m

If m is 1 billion (109), the naive algorithm takes


billions of steps, but this algorithm takes tens of
steps

You might also like