10 GCD

Chapter 12
Euclidean algorithm
The Euclidean algorithm is one of the oldest numerical algorithms still to be in common
use. It solves the problem of computing the greatest common divisor (gcd) of two positive
integers.
12.1. Euclidean algorithm by subtraction

The original version of Euclids algorithm is based on subtraction: we recursively subtract
the smaller number from the larger.
12.1: Greatest common divisor by subtraction.
1
2
3
4
5
6
7
def gcd(a, b):

if a == b:
return a
if a > b:
gcd(a - b, b)
else:
gcd(a, b - a)
Lets estimate this algorithms time complexity (based on n = a+b). The number of steps can
be linear, for e.g. gcd(x, 1), so the time complexity is O(n). This is the worst-case complexity,
because the value x + y decreases with every step.
12.2. Euclidean algorithm by division

Lets start by understanding the algorithm and then go on to prove its correctness. For two
given numbers a and b, such that a b:
if b | a, then gcd(a, b) = b,
otherwise gcd(a, b) = gcd(b, a mod b).

24 mod 9 = 6
9 mod 6 = 3
gcd(24, 9)
gcd(9, 6)
gcd(6, 3)
6 mod 3 = 0
=
c Copyright 2015 by Codility Limited. All Rights Reserved. Unauthorized copying or publication pro
hibited.
Lets prove that gcd(a, b) = gcd(b, r), where r = a mod b and a = b t + r:

Firstly, let d = gcd(a, b). We get d | (b t + r) and d | b, so d | r.
Therefore we get gcd(a, b) | gcd(b, r).
Secondly, let c = gcd(b, r). We get c | b and c | r, so c | a.
Therefore we get gcd(b, r) | gcd(a, b).
Hence gcd(a, b) = gcd(b, r). Notice that we can recursively call a function while a is not
divisible by b.
12.2: Greatest common divisor by dividing.
1
2
3
4
5
def gcd(a, b):

if a % b == 0:
return b
else:
return gcd(b, a % b)
Denote by (ai , bi ) pairs of values a and b, for which the above algorithm performs i steps.
Then bi Fibi1 (where Fibi is the i-th Fibonacci number). Inductive proof:
1. for one step, b1 = 0,
2. for two steps, b 1,
3. for more steps, (ak+1 , bk+1 ) (ak , bk ) (ak1 , bk1 ), then ak = bk+1 , ak1 = bk ,
bk1 = ak mod bk , so ak = q bk + bk1 for some q 1, so bk+1 bk + bk1 .
Fibonacci numbers can be approximated by:
( 1+2 5 )n
Fibn
5
(12.1)
Thus, the time complexity is logarithmic based on the sum of a and b O(log(a + b)).
12.3. Binary Euclidean algorithm

This algorithm finds the gcd using only subtraction, binary representation, shifting and parity
testing. We will use a divide and conquer technique.
The following function calculate gcd(a, b, res) = gcd(a, b, 1) res. So to calculate
gcd(a, b) it suffices to call gcd(a, b, 1) = gcd(a, b).
12.3: Greatest common divisor using binary Euclidean algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a, b, res):

if a == b:
return res * a
elif (a % 2 == 0) and (b % 2 == 0):
return gcd(a // 2, b // 2, 2 * res)
elif (a % 2 == 0):
return gcd(a // 2, b, res)
elif (b % 2 == 0):
return gcd(a, b // 2, res)
elif a > b:
return gcd(a - b, b, res)
else:
return gcd(a, b - a, res)
This algorithm is superior to the previous one for very large integers when it cannot be
assumed that all the arithmetic operations used here can be done in a constant time. Due
to the binary representation, operations are performed in linear time based on the length of
the binary representation, even for very big integers. On the other hand, modulo applied in
algorithm 10.2 has worse time complexity. It exceeds O(log n log log n), where n = a + b.
Denote by (ai , bi ) pairs of values a and b, for which the above algorithm performs i steps.
We have ai+1 ai , bi+1 bi , b1 = a1 > 0. In the first three cases, ai+1 bi+1 2 ai bi . In the
fourth case, ai+1 bi+1 2 ai1 bi1 , because a difference of two odd numbers is an even
number. By induction we get:
i1
(12.2)
ai bi 2 2
Thus, the time complexity is O(log(a b)) = O(log a + b) = O(log n). And for very large
integers, O((log n)2 ), since each arithmetic operation can be done in O(log n) time.
12.4. Least common multiple

The least common multiple (lcm) of two integers a and b is the smallest positive integer that
is divisible by both a and b. There is the following relation:
lcm(a, b) =
ab
gcd(a,b)
Knowing how to compute the gcd(a, b) in O(log(a+b)) time, we can also compute the lcm(a, b)
in the same time complexity.
12.5. Exercise
Problem: Michael, Mark and Matthew collect coins of consecutive face values a, b and c
(each boy has only one kind of coins). The boys have to find the minimum amount of money
that each of them may spend by using only their own coins.
Solution: It is easy to note that we want to find the least common multiple of the three
integers, i.e. lcm(a, b, c). The problem can be generalized for the lcm of exactly n integers.
There is the following relation:
lcm(a1 , a2 , . . . , an ) = lcm(a1 , lcm(a2 , a3 , . . . , an ))
We simply find the lcm n times, and each step works in logarithmic time.
Every lesson will provide you with programming tasks at http://codility.com/programmers.

10 GCD

Uploaded by

Copyright:

Available Formats

10 GCD

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

10 GCD

Uploaded by

Copyright:

Available Formats

Chapter 12

12.1. Euclidean algorithm by subtraction

def gcd(a, b):

12.2. Euclidean algorithm by division

otherwise gcd(a, b) = gcd(b, a mod b).

Lets prove that gcd(a, b) = gcd(b, r), where r = a mod b and a = b t + r:

def gcd(a, b):

12.3. Binary Euclidean algorithm

def gcd(a, b, res):

12.4. Least common multiple

Every lesson will provide you with programming tasks at http://codility.com/programmers.

You might also like