Nonplussed! (42 page)

This time the pseudo-code is

where we interpret line 1 as a loop, multiplying the input by
for as long as the product is an integer and when this fails multiplying it by the number
and letting control pass to line 2, which multiplies the input by
until the result is nonintegral, and then the process stops.

Now the addition sum is performed as before, but after this
r
₅
is emptied and
r
₃
filled, leaving the final registers as
r
₂
=
m +n
,
r
₃
=
m
and
r
₅
= 0. This is tidier in that it does not destroy the information held in
r
₃
and uses
r
₅
as the working register that it really is.

Figure 14.5.
Loops which multiply.

Using a fraction list we can add, but can we multiply?

Consider the following program code:

This describes a simple multiplication algorithm for positive integers which we can simulate using
figure 14.5
. This adds a further loop to
figure 14.4
, controlled by the fraction
.

Our pseudo-code is now

with the implied interpretation given above.

Notice that the
fraction is again used to force a jump.

If we start with
r
₂
=
a
,
r
₃
=
b
,
r
₅
= 0,
r
₇
=
c
, and so with the integer
N
= 2
^a
×3
^b
×7
^c
, then, after each cycle is completed, we have
b
added into
r
₂
and, using
r
₇
as a counter, we will finish with
r
₂
=
a + bc
,
r
₃
=
b
,
r
₅
= 0,
r
₇
= 0. In particular, if we take the case
a =
0, an input of
N
= 3
ⁿ
×7
^c
results in an output of
N =
2
^cn
, and so multiplication has indeed been accomplished.

Fractran

Where, though, is the fraction list equivalent to this? There is a problem, since the rules force the
to be evaluated repeatedly wherever it is encountered in the list, which denies its use as a loop. To manufacture that fraction list we need to look a bit deeper into our pseudo-code, or, as Conway has named it, the Fractran programming language.

Conway defines a Fractran program as a sequence of numbered lines each of the form

where
n
,
n
₁
,
n
₂
,…,
n
_r
are positive integer line numbers and