Section 2.3 More on Proof of Correctness
133
The two functions of Example 25 and Practice 10 are somewhat unrealistic;
after all, if we wanted to compute x * y or x + y, we could no doubt do it with a
single program statement. However, the same techniques apply to more meaningful computations, such as the Euclidean algorithm.
Euclidean Algorithm
The Euclidean algorithm was described by the Greek mathematician Euclid over
2300 years ago, although it may have been known even earlier. At any rate, it is
one of the oldest known algorithms.This algorithm finds the greatest common
divisor of two positive integers a and b with a > b. The greatest common divisor
of a and b, denoted by gcd(a, b), is the largest integer n such that n 0 a and n 0 b. For
example, gcd(12, 18) is 6 and gcd(420, 66) = 6.
First, let’s dispense with two trivial cases of the gcd(a, b) that do not require
the Euclidean algorithm.
i. gcd(a, a) = a. Clearly a 0 a and no larger integer divides a.
ii. gcd(a, 0) = a. Again, a 0 a and no larger integer divides a, but also a 0 0
because 0 is a multiple of a: 0 = 0(a)
The Euclidean algorithm works by a succession of divisions. To find gcd(a, b),
assuming that a > b, you first divide a by b, getting a quotient and a remainder.
More formally, at this point a = q 1 b + r 1 , where 0 ≤ r 1 < b. Next you divide the
divisor, b, by the remainder, r 1 , getting b = q 2 r 1 + r 2 , where 0 ≤ r 2 < r 1 . Again divide the divisor, r 1 , by the remainder, r 2 , getting r 1 = q 3 r 2 + r 3 , where 0 ≤ r 3 < r 2 .
Clearly, there is a looping process going on, with the remainders getting successively smaller. The process terminates when the remainder is 0, at which point the
greatest common divisor is the last divisor used.
A pseudocode version of the algorithm follows, given in the form of a function to return gcd(a, b).
Algorithm EuclidEan algorithm
GCD (positive integer a; positive integer b)
//a > b
Local variables:
integers i, j
i = a
j = b
ExAmplE 27
To find gcd(420, 66) the following divisions are performed:
6
2
1
3
66q420
24q66
18q24
6q18
396
48
18
18
24
18
6
0
The answer is 6, the divisor used when the remainder became 0.
133
The two functions of Example 25 and Practice 10 are somewhat unrealistic;
after all, if we wanted to compute x * y or x + y, we could no doubt do it with a
single program statement. However, the same techniques apply to more meaningful computations, such as the Euclidean algorithm.
Euclidean Algorithm
The Euclidean algorithm was described by the Greek mathematician Euclid over
2300 years ago, although it may have been known even earlier. At any rate, it is
one of the oldest known algorithms.This algorithm finds the greatest common
divisor of two positive integers a and b with a > b. The greatest common divisor
of a and b, denoted by gcd(a, b), is the largest integer n such that n 0 a and n 0 b. For
example, gcd(12, 18) is 6 and gcd(420, 66) = 6.
First, let’s dispense with two trivial cases of the gcd(a, b) that do not require
the Euclidean algorithm.
i. gcd(a, a) = a. Clearly a 0 a and no larger integer divides a.
ii. gcd(a, 0) = a. Again, a 0 a and no larger integer divides a, but also a 0 0
because 0 is a multiple of a: 0 = 0(a)
The Euclidean algorithm works by a succession of divisions. To find gcd(a, b),
assuming that a > b, you first divide a by b, getting a quotient and a remainder.
More formally, at this point a = q 1 b + r 1 , where 0 ≤ r 1 < b. Next you divide the
divisor, b, by the remainder, r 1 , getting b = q 2 r 1 + r 2 , where 0 ≤ r 2 < r 1 . Again divide the divisor, r 1 , by the remainder, r 2 , getting r 1 = q 3 r 2 + r 3 , where 0 ≤ r 3 < r 2 .
Clearly, there is a looping process going on, with the remainders getting successively smaller. The process terminates when the remainder is 0, at which point the
greatest common divisor is the last divisor used.
A pseudocode version of the algorithm follows, given in the form of a function to return gcd(a, b).
Algorithm EuclidEan algorithm
GCD (positive integer a; positive integer b)
//a > b
Local variables:
integers i, j
i = a
j = b
ExAmplE 27
To find gcd(420, 66) the following divisions are performed:
6
2
1
3
66q420
24q66
18q24
6q18
396
48
18
18
24
18
6
0
The answer is 6, the divisor used when the remainder became 0.