TAOCP 1.3.1 Exercise 13

Section 1.3.1: Description of MIX

Exercise 13. [10] Suppose location 1000 contains the instruction JOV 1001. This instruction turns off the overflow toggle if it is on (and the next instruction executed will be in location 1001, in any case). If this instruction were changed to JNOV 1001, would there be any difference? What if it were changed to JOV 1000 or JNOV 1000?

Verified: no
Solve time: 10m12s

For JOV 1001, if the overflow toggle is on, control transfers to location 1001 and the toggle is turned off. If the overflow toggle is off, control does not jump, so the next instruction executed is the one in location 1001. Hence, regardless of the state of the overflow toggle, execution continues at location 1001, and the toggle is off afterward.

If the instruction is changed to JNOV 1001, the situation is the same. When the overflow toggle is off, the jump is taken to 1001. When it is on, the jump is not taken, so the next instruction is again at 1001. In the latter case the toggle remains on. Thus the sequence of instructions executed is unchanged, but the final state of the overflow toggle differs when it was initially on.

If the instruction is changed to JOV 1000, then when the overflow toggle is on, the instruction jumps to itself and simultaneously turns the toggle off. The next execution of location 1000 therefore finds the toggle off and does not jump; execution proceeds to location 1001. When the overflow toggle is initially off, execution proceeds directly to 1001. Thus location 1000 is executed twice if and only if the toggle is initially on.

If the instruction is changed to JNOV 1000, then when the overflow toggle is off, the instruction jumps to itself and leaves the toggle off. The same instruction is executed again indefinitely. When the overflow toggle is on, no jump occurs and execution proceeds to location 1001. Hence this version enters an infinite loop whenever the overflow toggle is initially off. ∎