Problem 5. Invariants: Integer Multiplication from Bit Shifts We'll show that the following simple algorithm (state machine efficiently computes the product of two nonnegative integers, I and y. (It takes advantage of the fact that multiplying or dividing an integer by 2 is especially fast on most computers, requiring just a single bit- shift operation. The set of states is N = {(r, s, a) r, s, a EN}, i.e., the set of triples of nonnegative integers. The start state is (r, y,0). Finally, the state transitions are as follows: (r, s, a) + (2r, s/2, a) 2r, (s - 1)/2, a +r) nothing for even s > 0 for odd s > 0, for s=0 We'll show that this state machine eventually reaches a final state with no transitions re- maining the algorithm doesn't run forever!), and that this final state (ry, Spa) will have a = r.y the algorithm computes the desired answer!). (a) Compute the full sequence of transitions from starting state (5,22,0). Does it correctly compute 5. 22 = 110? (b) Prove by strong induction on s that from any state r, s, a), this algorithm terminates after at most 1 + log, s steps (if s > 0). So the algorithm finishes, and it does so quickly. Hint: Recall that log (/2) = log2 s) - 1. (c) Prove that rs + a=ry is an invariant of this procedure (d) Use the previous two parts to conclude that this algorithm must terminate in some final state rf, Sf. a) that has a = ry. Problem 5. Invariants: Integer Multiplication from Bit Shifts We'll show that the following simple algorithm (state machine efficiently computes the product of two nonnegative integers, I and y. (It takes advantage of the fact that multiplying or dividing an integer by 2 is especially fast on most computers, requiring just a single bit- shift operation. The set of states is N = {(r, s, a) r, s, a EN}, i.e., the set of triples of nonnegative integers. The start state is (r, y,0). Finally, the state transitions are as follows: (r, s, a) + (2r, s/2, a) 2r, (s - 1)/2, a +r) nothing for even s > 0 for odd s > 0, for s=0 We'll show that this state machine eventually reaches a final state with no transitions re- maining the algorithm doesn't run forever!), and that this final state (ry, Spa) will have a = r.y the algorithm computes the desired answer!). (a) Compute the full sequence of transitions from starting state (5,22,0). Does it correctly compute 5. 22 = 110? (b) Prove by strong induction on s that from any state r, s, a), this algorithm terminates after at most 1 + log, s steps (if s > 0). So the algorithm finishes, and it does so quickly. Hint: Recall that log (/2) = log2 s) - 1. (c) Prove that rs + a=ry is an invariant of this procedure (d) Use the previous two parts to conclude that this algorithm must terminate in some final state rf, Sf. a) that has a = ry