%load_ext watermark
%watermark -a 'Sebatian Raschka' -u -d -v
Sebatian Raschka last updated: 2016-06-02 CPython 3.5.1 IPython 4.2.0
Now, the greatest common divisor (GCD) is the largest natural number $d$ that divides $a$ and $b$ in a fraction $\frac{a}{b}$ without a remainder.
For example, the GCD of the fraction $\frac{6}{9}$ is 3: $$\frac{6/3}{9/3} = \frac{2}{3}$$
First, let us start with the "intuitive," yet naive, brute-force implementation. Here, we simply iterate through all integers from 1 to max(a, b) to find the largest common divisor of the fraction $\frac{a}{b}$ or equivalently $\frac{a}{b}$.
def naive_gcd(a, b):
gcd = 0
if a < b:
n = a
else:
n = a
for d in range(1, n + 1):
if not a % d and not b % d:
gcd = d
return gcd
print('In: 1/1,', 'Out:', naive_gcd(1, 1))
print('In: 1/2,', 'Out:', naive_gcd(1, 2))
print('In: 3/9,', 'Out:', naive_gcd(3, 9))
print('In: 12/24,', 'Out:', naive_gcd(12, 24))
print('In: 12/26,', 'Out:', naive_gcd(12, 26))
print('In: 26/12,', 'Out:', naive_gcd(26, 12))
print('In: 13/17,', 'Out:', naive_gcd(13, 17))
In: 1/1, Out: 1 In: 1/2, Out: 1 In: 3/9, Out: 3 In: 12/24, Out: 12 In: 12/26, Out: 2 In: 26/12, Out: 2 In: 13/17, Out: 1
The Greek mathematician Euclid described this algorithm approx. 300 BC in It is still being used in the field of number theory and conseqently cryptography to reduce fractions to their simplest form. For additional, interesting details and the proof by Gabriel Lamé in 1844, please take a look at the excellent Wikipedia page.
The idea behind the more efficient version, the Euclidean division (in contrast to the substraction-based) approach is the following:
Given that we want to compute gcd(a, b)
, the greatest common divisor of the fraction{a}{b}, we first compute the remainder of the division $\frac{a}{b}$; we call this remainder a'. Then, we compute gcd(a', b)
. We repeat this procedure in recursive manner until b=0.
def eucl_gcd_recurse(a, b):
if not b:
return a
else:
return eucl_gcd_recurse(b, a % b)
print('In: 1/1,', 'Out:', naive_gcd(1, 1))
print('In: 1/2,', 'Out:', naive_gcd(1, 2))
print('In: 3/9,', 'Out:', naive_gcd(3, 9))
print('In: 12/24,', 'Out:', naive_gcd(12, 24))
print('In: 12/26,', 'Out:', naive_gcd(12, 26))
print('In: 26/12,', 'Out:', naive_gcd(26, 12))
print('In: 13/17,', 'Out:', naive_gcd(13, 17))
In: 1/1, Out: 1 In: 1/2, Out: 1 In: 3/9, Out: 3 In: 12/24, Out: 12 In: 12/26, Out: 2 In: 26/12, Out: 2 In: 13/17, Out: 1
The Euclidean GCD algorithm will reduce either of the number at least by half at each step (see the Wikipedia page for details). Thus, the time complexity of this algorithm is
$O(log_2 b) + O(log_2 a) = O(log_2 n),$
where $n = max(a, b)$. In contrast, our previous, naive implementation has an upper bound of $O(n)$.
Since Python is "notoriously bad" at recursion, let us implement a dynamic version of this algorithm. (One problem of recursion via Python is the limited stack size, and the other one is that tail recursion optimization not implemented.)
def eucl_gcd_dynamic(a, b):
while b:
tmp = b
b = a % b
a = tmp
return a
print('In: 1/1,', 'Out:', naive_gcd(1, 1))
print('In: 1/2,', 'Out:', naive_gcd(1, 2))
print('In: 3/9,', 'Out:', naive_gcd(3, 9))
print('In: 12/24,', 'Out:', naive_gcd(12, 24))
print('In: 12/26,', 'Out:', naive_gcd(12, 26))
print('In: 26/12,', 'Out:', naive_gcd(26, 12))
print('In: 13/17,', 'Out:', naive_gcd(13, 17))
In: 1/1, Out: 1 In: 1/2, Out: 1 In: 3/9, Out: 3 In: 12/24, Out: 12 In: 12/26, Out: 2 In: 26/12, Out: 2 In: 13/17, Out: 1
Given an arbitrary fraction $\frac{a}{b}$, let us use the %timeit
module for a quick comparison:
a = 12313432
b = 34234232342
%timeit -r 3 -n 5 naive_gcd(a, b)
5 loops, best of 3: 1.78 s per loop
%timeit -r 3 -n 5 eucl_gcd_recurse(a, b)
5 loops, best of 3: 3.23 µs per loop
%timeit -r 3 -n 5 eucl_gcd_dynamic(a, b)
5 loops, best of 3: 2.21 µs per loop