Question

a. Use the Euclidean algorithm to compute the GCDs of the following pairs of integers State how many iterations each one takes to compute, and the value of the potential s at each stage. Verify that indeed si+1≤2/3si. i. (77,143) ii. (90, 504) ii. (376, 475) iv. (987, 1597)b. Try to find pairs of inputs (x, y such that the number of iterations of Euclid(x, y) is "large", that is, as close as possible to the upper bound of loga3/2(x+y) that we derived in lecture. Can you come up with a hypothesis about what kinds of inputs yield the worst-case running time?

Answer 1

Explanation:

(a). given GCD (77,143)

143 = 77.1 + 66

77 = 66.1 + 11

66 = 11.6 + 0

∴ the gcd (77,143) = 11

the number of iterations = 3

(ii). GCD(90,504)

504 = 90.5 + 54

90 = 54.1 + 36

54 = 36.1 + 18

36 = 18.2 + 0

∴ the gcd(90,504) = 18

the number of iterations = 4

(iii). GCD(376,475)

475 = 376.1 + 99

376 = 99.3 + 79

99 = 79.1 + 20

79 = 20.3 + 19

20 = 19.1 + 1

19 = 1.19 + 0

∴ the gcd(376,475) = 1

the number of iterations = 6

(iv). GCD(987,1597)

1597 = 987.1 + 610

987 = 610.1 + 377

610 = 377.1 +233

377 = 233.1 +144

233 = 144.1 + 89

144 = 89.1 + 55

89 = 55.1 + 34

55 = 34.1 + 21

34 = 21.1 + 13

21 = 13.1 = 8

13 = 8.1 9+ 5

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 = 1.2 + 0

∴ the gcd(987,1597) = 1

the number of iterations = 15

(b). the pairs of inputs for which the number of iterations is large is given thus;

1. gcd(8,5)

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 = 1.2 + 0

the number of iterations from this is 4

2. also gcd(8,13)

13 = 8.1 + 5

8 = 5.1 + 3

5 = 3.1 + 2

3 = 2.1 + 1

2 =1.2 + 0

the number of iteration from this is 5

→ from the examples given, the worst case scenario occurs when the inputs are conservative Fibonacci numbers.

cheers, i hope this helps.