|
1 | | -<!--?title The Euclidean algorithm for finding greatest common divisor --> |
2 | | - |
3 | | -# The Euclidean algorithm for finding greatest common divisor |
4 | | - |
5 | | -Given two non-negative integers $a$ and $b$, find their greatest common divisor, i.e. the largest number which is a divisor of both $a$ and $b$. It's commonly denoted by $gcd$. |
6 | | - |
7 | | -$$gcd(a, b) = \max_ {k = 1 \ldots \infty \ : \ k \mid a \ \& \ k \mid b} k$$ |
| 1 | +<!--?title Euclidean algorithm for computing the greatest common divisor --> |
| 2 | +# Euclidean algorithm for computing the greatest common divisor |
8 | 3 |
|
| 4 | +Given two non-negative integers $a$ and $b$, we have to find their **GCD** (greatest common divisor), i.e. the largest number which is a divisor of both $a$ and $b$. |
| 5 | +It's commonly denoted by $\gcd(a, b)$. Mathematically it is defined as: |
| 6 | +$$\gcd(a, b) = \max_ {k = 1 \dots \infty ~ : ~ k \mid a ~ \wedge k ~ \mid b} k.$$ |
9 | 7 | (here the symbol "$\mid$" denotes divisibility, i.e. "$k \mid a$" means "$k$ divides $a$") |
10 | 8 |
|
11 | | -When one of the numbers is zero, while the other is non-zero, their greatest common divisor, by definition, is the second number. When both numbers are zero, their greatest common divisor is undefined (it can be any arbitrarily large number), but we can define it to be zero. So we have a simple rule: if one of the numbers is zero, the greatest common divisor is the other number. |
| 9 | +When one of the numbers is zero, while the other is non-zero, their greatest common divisor, by definition, is the second number. When both numbers are zero, their greatest common divisor is undefined (it can be any arbitrarily large number), but we can define it to be zero. Which gives us a simple rule: if one of the numbers is zero, the greatest common divisor is the other number. |
12 | 10 |
|
13 | | -The Euclidean algorithm, discussed below, allows to find the greatest common divisor of two numbers $a$ and $b$ in $O(\log min(a, b))$. |
| 11 | +The Euclidean algorithm, discussed below, allows to find the greatest common divisor of two numbers $a$ and $b$ in $O(\log \min(a, b))$. |
14 | 12 |
|
15 | | -The algorithm was first described in Euclid's "Elements" (circa 300 BC), but it is possible that the algorithm has earlier origins. |
| 13 | +The algorithm was first described in Euclid's "Elements" (circa 300 BC), but it is possible that the algorithm has even earlier origins. |
16 | 14 |
|
17 | 15 | ## Algorithm |
18 | 16 |
|
19 | 17 | The algorithm is extremely simple: |
20 | 18 |
|
21 | | -$$gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\\\ gcd(b, a\mod b),&\text{otherwise}\end{cases}$$ |
| 19 | +$$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\\\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}$$ |
22 | 20 |
|
23 | 21 | ## Implementation |
24 | 22 |
|
25 | 23 | ```cpp |
26 | 24 | int gcd (int a, int b) { |
27 | | - if (b == 0) |
28 | | - return a; |
29 | | - else |
30 | | - return gcd (b, a % b); |
| 25 | + if (b == 0) |
| 26 | + return a; |
| 27 | + else |
| 28 | + return gcd (b, a % b); |
31 | 29 | } |
32 | 30 | ``` |
33 | 31 |
|
34 | | -Using the ternary operator in C++, we can write a shorter implementation: |
| 32 | +Using the ternary operator in C++, we can write it as a one-liner. |
35 | 33 |
|
36 | 34 | ```cpp |
37 | 35 | int gcd (int a, int b) { |
38 | | - return b ? gcd (b, a % b) : a; |
| 36 | + return b ? gcd (b, a % b) : a; |
39 | 37 | } |
40 | 38 | ``` |
41 | 39 |
|
42 | | -Finally, here is a non-recursive implementation: |
| 40 | +And finally, here is a non-recursive implementation: |
43 | 41 |
|
44 | 42 | ```cpp |
45 | 43 | int gcd (int a, int b) { |
46 | | - while (b) { |
47 | | - a %= b; |
48 | | - swap(a, b); |
49 | | - } |
50 | | - return a; |
| 44 | + while (b) { |
| 45 | + a %= b; |
| 46 | + swap(a, b); |
| 47 | + } |
| 48 | + return a; |
51 | 49 | } |
52 | 50 | ``` |
53 | 51 |
|
54 | 52 | ## Correctness Proof |
55 | 53 |
|
56 | | -First, notce that at each iteration of the Euclidean algorithm the second argument strictly decreases, therefore (since the arguments are always non-negative) the algorithm will always terminate. |
| 54 | +First, notice that in each iteration of the Euclidean algorithm the second argument strictly decreases, therefore (since the arguments are always non-negative) the algorithm will always terminate. |
57 | 55 |
|
58 | | -For the proof of correctness, we need to show that $gcd(a, b) = gcd(b, a \mod b)$ for all $a \geq 0$, $b > 0$. |
| 56 | +For the proof of correctness, we need to show that $\gcd(a, b) = \gcd(b, a \bmod b)$ for all $a \geq 0$, $b > 0$. |
59 | 57 |
|
60 | 58 | We will show that the value on the left side of the equation divides the value on the right side and vice versa. Obviously, this would mean that the left and right sides are equal, which will prove Euclid's algorithm. |
61 | 59 |
|
62 | | -Let $d = gcd(a, b)$. Then by definition $d\mid a$ and $d\mid b$. |
63 | | -
|
64 | | -Now let's represent the remainder from dividing $a$ by $b$ as follows: |
65 | | -
|
66 | | -$$ |
67 | | -a \mod b = a - b \cdot \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor |
68 | | -$$ |
69 | | -
|
70 | | -But then, it follows: |
71 | | -
|
72 | | -$$ |
73 | | -d \mid (a \mod b) |
74 | | -$$ |
| 60 | +Let $d = \gcd(a, b)$. Then by definition $d\mid a$ and $d\mid b$. |
75 | 61 |
|
76 | | -So, recalling that $d \mid b$, we obtain the system: |
| 62 | +Now let's represent the remainder of the division of $a$ by $b$ as follows: |
| 63 | +$$a \bmod b = a - b \cdot \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor$$ |
77 | 64 |
|
78 | | -$$ |
79 | | -\begin{cases}d \mid b,\cr d \mid (a \mod b)\cr\end{cases} |
80 | | -$$ |
| 65 | +From this it follows that $d \mid (a \bmod b)$, which means we have the system of divisiblities: |
| 66 | +$$\begin{cases}d \mid b,\\\\ d \mid (a \mod b)\end{cases}$$ |
81 | 67 |
|
82 | | -Now we use the fact that for any three numbers $p$, $q$, $r$, if $p\mid q$ and $p\mid r$ then $p\mid gcd(q, r)$, In our case, we get: |
83 | | -
|
84 | | -$$ |
85 | | -d \mid gcd(b, a \mod b) |
86 | | -$$ |
87 | | -
|
88 | | -Substituting $d$ with its definition ($gcd(a, b)$) we get: |
89 | | -
|
90 | | -$$ |
91 | | -gcd(a, b) \mid gcd(b, a \mod b) |
92 | | -$$ |
| 68 | +Now we use the fact that for any three numbers $p$, $q$, $r$, if $p\mid q$ and $p\mid r$ then $p\mid \gcd(q, r)$. In our case, we get: |
| 69 | +$$d = \gcd(a, b) \mid \gcd(b, a \mod b)$$ |
93 | 70 |
|
94 | 71 | Thus we have shown that the left side of the original equation divides the right. The second half of the proof is similar. |
95 | 72 |
|
96 | 73 | ## Time Complexity |
97 | 74 |
|
98 | | -The running time of the algorithm is estimated by Lame's theorem, which establishes a surprising connection between the Euclidean algorithm and the Fibonacci sequence: |
| 75 | +The running time of the algorithm is estimated by Lamé's theorem, which establishes a surprising connection between the Euclidean algorithm and the Fibonacci sequence: |
99 | 76 |
|
100 | 77 | If $a > b \geq 1$ and $b < F_n$ for some $n$, the Euclidean algorithm performs at most $n-2$ recursive calls. |
101 | 78 |
|
102 | 79 | Moreover, it is possible to show that the upper bound of this theorem is optimal. When $a = F_n$ and $b = F_{n-1}$, $gcd(a, b)$ will perform exactly $n-2$ recursive calls. In other words, consecutive Fibonacci numbers are the worst case input for Euclid's algorithm. |
103 | 80 |
|
104 | | -Given that Fibonacci numbers grow exponentially (as a constant raised to $n$th power), we get that the Euclidean algorithm works in $O(\log min(a, b))$ multiplication operations. |
105 | | -
|
106 | | -## LCM (least common multiple) |
| 81 | +Given that Fibonacci numbers grow exponentially, we get that the Euclidean algorithm works in $O(\log \min(a, b))$. |
107 | 82 |
|
108 | | -Calculating least common multiple (commonly denoted LCM) is reduced to calculating $gcd$ with the following simple formula: |
| 83 | +## Least common multiple |
109 | 84 |
|
110 | | -$$ |
111 | | -lcm(a, b) = \dfrac{a \cdot b}{gcd(a, b)} |
112 | | -$$ |
| 85 | +Calculating the least common multiple (commonly denoted **LCM**) can be reduced to calculating the GCD with the following simple formula: |
| 86 | +$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$ |
113 | 87 |
|
114 | 88 | Thus, LCM can be calculated using the Euclidean algorithm with the same time complexity: |
115 | 89 |
|
| 90 | +A possible implementation, that cleverly avoids integer overflows by first dividing $a$ with the GCD, is given here: |
| 91 | +
|
116 | 92 | ```cpp |
117 | 93 | int lcm (int a, int b) { |
118 | | - return a / gcd (a, b) * b; |
| 94 | + return a / gcd(a, b) * b; |
119 | 95 | } |
120 | 96 | ``` |
121 | | -(here it is advantageous to first divide by $gcd$ and then multiply by $b$ to avoid overflow in some cases) |
122 | | - |
123 | | -## Literature |
124 | | - |
125 | | -- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algorithms: Construction and analysis [2005] |
126 | 97 |
|
127 | 98 | ## Practice Problems |
128 | 99 |
|
129 | | -- [GCD and LCM [easy]](https://www.codechef.com/problems/FLOW016) |
| 100 | +- [Codechef - GCD and LCM](https://www.codechef.com/problems/FLOW016) |
0 commit comments