This page devoted to some more example register machines, all written with the basic instructions of primitive register machines. Some of them are given for you to try out and some are for you to write on your own.
You will recall the following operations.
The INFLOOP and BREAK were instructions that cannot be performed with primitive register machines.
You have already seen the following program to decrement a number,
// decr.cpp
INPUT(x)
USES(y)
USES(z)
// does DECR(x) but without using the DECR command
LOOP(x) { INCR(y) } // make y the same as x
ZERO(x) // clear x
LOOP(y) { LOOP(z) { INCR(x) } ZERO(z) INCR(z) }
PRINT(x)
Here is another program to do exactly the same thing.
// decr2.cpp
INPUT(x)
USES(y)
USES(z)
// does DECR(x) but without using the DECR command
LOOP(x) { INCR(y) } // make y the same as x
ZERO(x) // clear x
// now copy z to x for each z=0..y-1
LOOP(y) { ZERO(x) LOOP(z) { INCR(x) } INCR(z) }
PRINT(x)
Check they both work. They both have exactly one INCR(x) statement. How many times is this INCR(x) statement executed? Make a table giving your answers with values 0,1,2,3,4,... of the input against the number of times INCR(x) is executed in decr.cpp and in decr2.cpp. If possible give a formula for the values in your table.
Hint: You do not have to work this out by hand, you can get the computer to do the work! Add a new variable USES(c) and put INCR(c) next to the statement you are trying to measure.
Which of the two programs do you prefer, and why?
The following example divides x by two, setting r to be the remainder.
INPUT(x)
USES(r)
USES(y)
LOOP(x) { INCR(y) }
ZERO(x) // start with y=input and x=0
INFLOOP {
DECR(y) ELSE { BREAK }
DECR(y) ELSE { INCR(r) BREAK }
INCR(x)
}
PRINT(x) // the quotient
PRINT(r) // the remainder
An unbounded loop is not really needed here. LOOP(y) { ... } would have worked just as well. (Note that BREAK breaks out of both kinds of loops.)
Here's a completely different way to program the same function. How does it work?
INPUT(x)
USES(y)
LOOP(x) { INCR(y) }
ZERO(x)
USES(r) // exactly one of r,s,t will be 1 at any time
USES(s)
USES(t)
INCR(s)
LOOP(y) {
LOOP(s) { ZERO(s) INCR(t) }
LOOP(r) { INCR(x) ZERO(r) INCR(s) }
LOOP(t) { ZERO(t) INCR(r) }
}
PRINT(x)
PRINT(r)
From studying the previous example, you should notice a useful trick. Immediately after a loop of the form
LOOP(y) { ... BREAKIFZ(x) ... }
you might want to test if the loop was ended because of the break or if it ended normally. You can do this with another register that always takes value 0 or 1.
ZERO(s)
LOOP(y) { ... INCR(s) BREAKIFZ(x) ZERO(s) ... }
IFZ(s) { ... }
IFNZ(s) { ... }
The register s is 1 just before the BREAKIFNZ and reset to 0 immediately afterwards. This trick applies in other cases too with other kinds of loops perhaps.
Exercise.
Write a program that sets z to be x / y using integer division discarding the remainder. (If the input variable y is zero your program should finish but it doesn't matter what the output is.)
Exercise.
Write a program that sets z to be x % y, the remainder on dividing x by y. (If the input variable y is zero your program should finish but it doesn't matter what the output is.)
Exercise.
(For more ambitious students.) Write a program that sets z to be highest common factor of x and y. You may assume the input variables are not zero.
There is an assignment at the end of this section. As always the details are elsewhere and there is an associated quiz. Be careful that you start this one early. It might be tricky!
Here is a program that repreatedly divides x by 2 (discarding remainder) and returns the number of times this can be done when the result of the division is non-zero.
// repdiv.cpp
INPUT(x)
USES(c)
USES(y)
INFLOOP {
LOOP(x) { INCR(y) }
ZERO(x)
INFLOOP {
DECR(y) ELSE { BREAK }
DECR(y) ELSE { BREAK }
INCR(x)
}
BREAKIFZ(x)
INCR(c)
}
PRINT(c)
This is an interesting program to study, especially with relation to the time it takes.
For a given input x roughly how many times is DECR(y) executed?
For a given input x roughly how many times is ZERO(x) executed?