Minds and Computers : An Introduction to the Philosophy of Artificial Intelligence

Exercise 8.4
Write a register machine program which computes the
multiplication function: f (x
1
, x
2
) 

 x
1
 x
2
. Assume you
begin with 1 in the pc, x
1
in R
1
and x
2
in R
2
, but make no
assumptions about the contents of other registers.
As always, the di
fficulty is in determining the algorithm. Multiplying
two numbers x and y can be understood as accumulating x copies of
y. So the algorithm we want to implement will try to decrement R
1
80
  

---

and, if successful, will add a copy of R
2
to a working register. When
R
1
is empty, we want to move the accumulated value in the working
register (x copies of y) into R
1
and terminate.
We know we need at least one working register to accumulate the
result in. We are also going to need another working register to e
ffect
copying without loss from R
2
into the register accumulating the solu-
tion. That is to say, each time we are successful in decrementing R
1
,
we want to copy R
2
into a solution accumulator (say R
3
) as well as
into another working register (say R
4
), then we want to put R
4
back
into R
2
before attempting to decrement R
1
again.
We have been told not to make any assumptions concerning regis-
ters other than R
1
and R
2
which hold the inputs of the function. This
means that the first thing our program should do is ensure that our
working registers are empty. This is easily done with one program line
per register.
So the algorithm we want to implement will do the following. First,
ensure the working registers (R
3
and R
4
) are empty. Attempt to decre-
ment R
1
. If unsuccessful, move R
3
(the solution accumulator) into R
1
and halt. If successful copy R
2
into R
3
and R
4
, then move R
4
back
into R
2
before attempting to decrement R
1
again.
Translating this into register machine code gives the following:
1
D
3 1
2
2
D
4 2
3
3
D
1 4
9
4
D
2 5
7
5
I
3 6
6
I
4 4
7
D
4 8
3
8
I
2 7
9
D
3 10 12
10
I
1 9