Mathematics for Computer Science

Chapter 8 Number Theory288

statesWWDN^3
start stateWWD.a;b;1/
transitionsWWDif min.x;y/ > 0;then.x;y;e/!
.x=2;y=2;2e/ (if 2 jxand 2 jy)
(8.22)
.x=2;y;e/ (else if 2 jx)
(8.23)
.x;y=2;e/ (else if 2 jy)
(8.24)
.xy;y;e/ (else ifx > y)
(8.25)
.yx;x;e/ (else ify > x)
(8.26)
.1;0;ex/ (otherwise (xDy)):
(8.27)
(a)Use the Invariant Principle to prove that if this machine stops, that is, reaches
a state.x;y;e/in which no transition is possible, theneDgcd.a;b/.

(b)Prove that rule (8.22)

.x;y;e/!.x=2;y=2;2e/

is never executed after any of the other rules is executed.

(c)Prove that the machine reaches a final state in at most 1 C3.logaClogb/
transitions. (This is a coarse bound; you may be able to get a better one.)

Problem 8.17.
Extend the binary gcd procedure of Problem 8.16 to obtain a new pulverizer that
uses only division by 2 and subtraction.
Hint:After the binary gcd procedure has factored out 2’s, it starts computing the
gcd.a;b/for numbersa;bat least one of which is odd. It does this by successively
updating a pair of numbers.x;y/such that gcd.x;y/D gcd.a;b/. Extend the
procedure to find and update coefficientsux;vx;uy;vysuch that

uxaCvxbDxanduyaCvybDy: