procedure multiply(x, y: nonnegative integers) r := ac; s := y; a := 0; while s * 0 do if 3 | s then r:=rtrt r; S : = S/3; else if 3 | (s - 1) then a : = atr; r:=rtrtr; S := (s - 1)/3; else a : = atr+r; r:=rtrtr; S := (s - 2)/3; return a; We can model the algorithm as a state machine whose states are triples of nonnegative integers (r, s, a). The initial state is (x, y, 0). The transitions are given by the rule that for s > 0: (3r, s/ 3, a) if 3 | s (r, s, a ) - (3r, (s - 1)/3, atr) if3| (s - 1) (3r, (s - 2) /3, a + 2r) otherwise