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, y0, and return(d,;r,i/).
  • 2. Set 0, y2<— 0, yi<— 1.
  • 3. While b > 0 do the following:
  • 3.1 q<-[a/b, r^a-qb, x^x2 - qxi, y^y2 - qy.
  • 3.2 a^b, b^r, X2<—xi, xi^x, y2<-y,znd yi^y.
  • 4. Set dx—a, x^x2, y<— y2, 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.

 
Source
< Prev   CONTENTS   Source   Next >