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

Exercise 8.5
Write a register machine program which computes the
squaring function:
f (x) 

 x
2
. Assume you begin with 1 in the pc and x in R
1
but
make no assumptions concerning the contents of other
registers.
Squaring is simply a special case of multiplication – the case where
both multiplicands are identical. So x
2
is simply x copies of x.

81

---

One way to design a register machine program to compute the
squaring function would be to make minor alterations to the algo-
rithm for multiplication we employed in solving Exercise 8.4, as
follows. As well as clearing R
3
and R
4
, we also clear R
2
. Then, before
attempting to decrement R
1
, we copy R
1
into R
2
, using R
3
as a
working register to copy without loss. We then follow the algorithm
for multiplying R
1
and R
2
.
There is, however, another algorithm we could implement. Con-
sider the following register machine program:
1
D
2
1
2
2
D
3
2
3
3
D
4
3
4
4
I
2
5
5
D
1
6
13
6
D
2
7
9
7
I
3
8
8
I
4
6
9
I
4
10
10
I
4
11
11
D
4
12
5
12
I
2
11
13
D
3
14
15
14
I
1
13
Exercise 8.6
The register machine program above computes the squaring
function. What algorithm does it implement?
It turns out that to find the nth square number, we can simply accu-
mulate the first n odd numbers. So 1
2
is 1, 2
2

 (1  3) 
 4, 3
2

 (1 
3 
 5) 
 9, etc. Figure 8.2 sheds some light on why this is the case.
The above register machine program for squaring implements an
algorithm which takes the sum of the series of odd numbers up to the
nth term (where n is the input of the function – the number we begin
with in R
1
).