This algorithm is used to calculate the greatest common divisor for two positive integers. This uses Euclid’s rule and modular arithmetic.

Algorithm

Euclid(x,y):
	Input: integers x,y where x >= y >= 0
	Output: gcd(x,y)
1. If y = 0 return x
2. return Eculid(y, x mod y)

Run time

If $x$ and $y$ are $n$-bit integers then calculating $x$ mod $y$ takes $O(n^2)$ time. From Claim 1 we have every 2 rounds $x$ decreases by at least a factor of 2. So there are at most $2n$ rounds giving this algorithm a run time of $O(n^3)$.

Claim 1

Proof

If $y \leq x/2$ then $x$ mod $y$ $\leq y -1 < y \leq x/2$.

If $y > x/2$ then $x$ mod $y$ = $x - y < x - x/2 \leq x/2$.

Correctness

This follows from Euclid’s rule.