Algorithms in Z
Let a and b be non-negative integers, each less than or equal to n. Recall (Example 2.51) that the number of bits in the binary representation of n is |_lg nj + 1, and this number is approximated by lg n. The number of bit operations for the four basic integer operations of addition, subtraction, multiplication, and division using the classical algorithms is summarized in Table 2.1. These algorithms are studied in more detail in §14.2. More sophisticated techniques for multiplication and division have smaller complexities.
Operation |
Bit complexity |
Addition a + b Subtraction a - b Multiplication a ■ b Division a = qb + r |
O(lgo + lgi>) = 0(lg7l) 0(lgo + lgb) = O(lgn) 0((lga)(lgb))=0((lgn)^{2}) 0((lg9)(lgb)) = 0((lgn)^{2}) |
Table 2.1: Bit complexity of basic operations in Z.
The greatest common divisor of two integers a and b can be computed via Fact 2.98. However, computing a gcd by first obtaining prime-power factorizations does not result in an efficient algorithm, as the problem of factoring integers appears to be relatively difficult. The Euclidean algorithm (Algorithm 2.104) is an efficient algorithm for computing the greatest common divisor of two integers that does not require the factorization of the integers. It is based on the following simple fact.
- 2.103 Fact If a and b are positive integers with a > b, then gcd(a, b) = gcd(6, a mod b).
- 2.104 Algorithm Euclidean algorithm for computing the greatest common divisor of two integers
INPUT: two non-negative integers a and b with a>b.
OUTPUT: the greatest common divisor of a and b.
- 1. While b f 0 do the following:
- 1.1 Set r«— a mod b, a<—b, b^r.
- 2. Retum(a).
- 2.105 Fact Algorithm 2.104 has a running time of 0((lg ?г)^{2}) bit operations.
- 2.106 Example (Euclidean algorithm) The following are the division steps of Algorithm 2.104 for computing gcd(4864,3458) = 38:
- 4864 = 1 • 3458 + 1406
- 3458 = 2 • 1406 + 646
- 1406 = 2-646+ 114 646 = 5-114 + 76 114 = 1-76 + 38
- 76 = 2 • 38 + 0. □
The Euclidean algorithm can be extended so that it not only yields the greatest common divisor d of two integers a and b, but also integers x and у satisfying ax + by = d.
2.107 Algorithm Extended Euclidean algorithm
INPUT: two non-negative integers a and b with a>b.
OUTPUT: d = gcd(a, b) and integers x, у satisfying ax + by = d.
- 1. If b = 0 then set dt-a, 1, y
0, and return(d,;r,i/). - 2. Set 0, y_{2}<— 0, yi<— 1.
- 3. While b > 0 do the following:
- 3.1 q<-[a/b, r^a-qb, x^x_{2} - qxi, y^y_{2} - qy.
- 3.2 a^b, b^r, X2<—xi, xi^x, y_{2}<-y,znd yi^y.
- 4. Set dx—a, x^x_{2}, y<— y_{2}, and returned,#,?/).
- 2.108 Fact Algorithm 2.107 has a running time of 0((lg ?г)^{2}) bit operations.
- 2.109 Example {extended Euclidean algorithm) Table 2.2 shows the steps of Algorithm 2.107
with inputs a = 4864 and b = 3458. Hence gcd(4864,3458) = 38 and (4864)(32) + (3458)(—45) = 38. □
Я |
r |
X |
У |
a |
b |
X2 |
Xl |
У2 |
У i |
— |
— |
— |
— |
4864 |
3458 |
1 |
0 |
0 |
1 |
1 |
1406 |
1 |
-1 |
3458 |
1406 |
0 |
1 |
1 |
-1 |
2 |
646 |
-2 |
3 |
1406 |
646 |
1 |
-2 |
-1 |
3 |
2 |
114 |
5 |
-7 |
646 |
114 |
-2 |
5 |
3 |
-7 |
5 |
76 |
-27 |
38 |
114 |
76 |
5 |
-27 |
-7 |
38 |
1 |
38 |
32 |
-45 |
76 |
38 |
-27 |
32 |
38 |
-45 |
2 |
0 |
-91 |
128 |
38 |
0 |
32 |
-91 |
-45 |
128 |
Table 2.2: Extended Euclidean algorithm (Algorithm 2.107) with inputs a = 4864, b = 3458.
Efficient algorithms for ged and extended ged computations are further studied in §14.4.