8.13. References 287
Problem 8.14.
Prove that the smallest positive integersabfor which, starting in state.a;b/,
the Euclidean state machine will makentransitions areF.nC1/andF.n/, where
F.n/is thenth Fibonacci number.
Hint:Induction.
In a later chapter, we’ll show thatF.n/ 'nwhere'is the golden ratio
.1C
p
5/=2. This implies that the Euclidean algorithm halts after at most log'.a/
transitions. This is a somewhat smaller than the 2 log 2 abound derived from equa-
tion (8.4).
Problem 8.15.
Let’s extend the jug filling scenario of Section 8.1.3 to three jugs and a receptacle.
Suppose the jugs can holda,b, andcgallons of water, respectively.
The receptacle can be used to store an unlimited amount of water, but has no
measurement markings. Excess water can be dumped into the drain. Among the
possible moves are:
- fill a bucket from the hose,
- pour from the receptacle to a bucket until the bucket is full or the receptacle
is empty, whichever happens first, - empty a bucket to the drain,
- empty a bucket to the receptacle, and
- pour from one bucket to another until either the first is empty or the second
is full.
(a)Model this scenario with a state machine. (What are the states? How does a
state change in response to a move?)
(b)Prove that Bruce can getk 2 Ngallons of water into the receptacle using the
above operations if gcd.a;b;c/jk.
Problem 8.16.
TheBinary GCDstate machine computes the GCD of integersa;b > 0using only
division by 2 and subtraction, which makes it run very efficiently on hardware that
uses binary representation of numbers. In practice, it runs more quickly than the
more famous Euclidean algorithm described in Section 8.2.1.