1.9 State Machines - Invariants

Suppose that the following procedure is used to multiply two non-negative integers a and b.

• \(x ::= a\)
• \(y ::= b\)
• \(p ::= 0\)

Repeat the following commands:

• if \(x = 0\), then output \(p\) and terminate; else
• if \(x\) is even, then set \(x \leftarrow x/2\) and \(y \leftarrow 2y\); else
• if \(x\) is odd, then set \(x \leftarrow x - 1\) and \(p \leftarrow p + y\).

1. Which of the following predicates are preserved invariants for this algorithm?

   Exercise 1

    \(xy = p\) 

    \(xy = ab\) 

    \(xy + p = ab\) 

    \(xyp = ab\) 

   Predicates (1), (2), and (4) are preserved by the second command of the algorithm, but not necessarily by the third command. Predicate (3) is preserved by both commands. In the second command, the product \(xy\) remains the same and so does \(p\), so the sum keeps its old value. In the third command, the product \(xy\) decreases by \(y\) and \(p\) increases by \(y\), so the sum again keeps its old value.



2. Which of the following derived quantities get smaller at every transition?

   Exercise 2

    \(x\) 

    \(xy\) 

    \(p - y\) 

    \(x + p\) 

   In every transition, \(x\) is either halved or reduced by 1, so it is strictly decreasing. In contrast, \(xy\) either remains the same or reduces by \(y\), so it is weakly decreasing. \(p-y\) and \(x+p\) may each decrease or increase.
   CheckShow Answer