UNCLASSIFIED
U.D.C. No. 518.5 : 531.791
Technical Note No. M.S.38
April, 1959
R O Y A L A I R C R A F T E S T A B L I S H M E N T
(FARNBOROUGH)
A PROGRAMMING HANDBOOK FOR THE COMPUTER DEUCE
by
D.G. Burnett-Hall, B.A.
and
P.A. Samet, Ph.D., B.Sc.
__________________
SUMMARY
The technique of programming the digital computer DEUCE is described.
_____________
UNCLASSIFIED
LIST OF CONTENTS
Page
1 INTRODUCTION 4
PART I THE ESSENTIALS OF PROGRAMMING 5
I.1 Description of a computing machine 5
I.2 Description of DEUCE 7
I.3 DEUCE instruction code 8
I.4 Some simple programs 12
I.5 Loops and counting 16
I.6 The instruction word 24
I.7 Subroutines 34
I.8 Modification of instructions and counting 38
I.9 Automatic modification and counting 43
I.10 Optimum coding 49
I.11 The double length accumulator 51
I.12 The multiplier and divider 57
I.13 Logical operations 62
I.14 Destination 'Triggers' 65
I.15 The reader and the punch 69
I.16 The magnetic drum 78
I.17 Input of programs 82
PART II PROGRAM TESTING 91
II.1 The DEUCE console 91
II.2 Common errors in programs 100
II.3 The use of checking routines 102
II.4 Machine aids to program testing 104
II.5 Programmed aids 107
PART III AVAILABLE PROGRAMS 111
III.1 The DEUCE library 111
III.2 DEUCE library subroutines 115
III.3 List of recommended subroutines 118
III.4 Specifications of programs 124
PART IV SPECIAL TOPICS 126
IV.1 The detailed coding program (R.A.E.415) 126
IV.2 The program changing routine (R.A.E.180) 127
IV.3 Floating point arithmetic 130
IV.4 Interpretive and translating programs 134
IV.5 The R.A.E. translation routine for a single address
code (R.A.E.424) 135
IV.6 The N.P.L. General Interpretive Program (G.I.P.) 138
IV.7 Matrix schemes A, B, Z 143
IV.8 Simplified programming, the "alphacode" 145
IV.9 An introduction to logical design 148
PART V EXERCISES AND SOLUTIONS 152
V.1 Exercises 152
V.2 Solutions to the previous exercises 159
LIST OF REFERENCES 186
ADVANCE DISTRIBUTION LIST 187
- 2 -
LIST OF CONTENTS (Contd)
Page
APPENDICES 1-4 188-198
ILLUSTRATIONS - Figs. 1-8 -
DETACHABLE ABSTRACT CARD -
LIST OF APPENDICES
Appendix
1 - Function code of DEUCE 188
2 - Binary Arithmetic 191
3 - Useful constants 195
4 - Hollerith timings 197
LIST OF ILLUSTRATIONS
Fig.
DEUCE logical diagram 1
The DEUCE console 2
Numbering switches on the punch 3
Logical diagrams 4, 5 & 6
Sources 14, 23 and 24 7
The output staticiser 8
_________
- 3 -
1 INTRODUCTION
This Note describes the technique of programming the DEUCE electronic
computer. Two such machines* are in operation in Mathematical Services
Department.
The original programming manual (Ref.2) was published in 1955, before
a machine was available. In it there was an account of how to write pro-
grams but no mention was made of techniques used in program testing and the
methods that can be used to simplify programming. These techniques,
however, are important to all machine users and are not readily accessible
to beginners. Many of the methods now in general use, at R.A.E. and else-
where, are of more recent date than the programming manual. It was therefore
decided to write a new manual, which was to be a comprehensive guide to all
machine users, especially beginners.
The Note consists of five parts. Part I contains all that is necessary
for efficient use of the machine's facilities in the construction of programs.
Part II is concerned with program testing. The techniques described were
mostly developed at R.A.E. and are the result of much cooperative effort and
shared experience in Mathematical Services Department. Part III gives some
details of the library of programs and subroutines available for DEUCE, as
well as a list of recommended subroutines to perform standard operations.
Part IV is meant for the more advanced programmer. It contains sections
that deal with specialized topics, such as interpretive programs, and also
has a simple introduction to logical design. Part V consists of exercises
for the beginner, although others may learn something useful from the
examples.
The text is, to a large extent, based on a course given by Mathematical
Services Department in May 1957. The order of presentation of the subjects
in Part I is the result of experiment with this course.
One small point concerns the spelling of 'program'. There is a rather
meaningless controversy about this, some supporting 'program' while others
favour 'programme'. The spelling adopted here was used for the EDSAC in
Cambridge in 1949, when there were no other machines. We are therefore in
good company and the spelling has the virtue of English precedent but really
it is only a matter of personal taste.
A word of explanation is needed for the long delay between the time of
writing of most of this Note and its publication. The authors both left
R.A.E. at the end of the summer of 1957, when most of the text was in manu-
script form. Their commitments elsewhere allowed little time for writing
the remaining sections until late 1958. By this time certain alterations
had been made to the DEUCE, which required a further revision of some
sections of the text. Even now (early 1959) the exercises of Part V are
fewer than had originally been hoped and there is no index. For all these
delays and omissions we beg our readers' pardon.
Thanks are due to many people. To our colleagues in Mathematical
Services Department, especially Mr. E.J. York and Mr. J.M. Watt, we owe
much. Their comments and suggestions, when followed, have improved the
presentation in many places. Mr. J.M. Hahn, of Bristol Aircraft Company,
has allowed us to copy Fig.1, 'A Schematic Diagram of DEUCE'.
Dr. S.H. Hollingdale has been patient with us and supported our efforts
over a long and often frustrating period. To all these persons we say
'thank you'.
* Affectionately known as 'Gert' and 'Daisy'
- 4 -
PART I THE ESSENTIALS OF PROGRAMMING
I.1 Description of a computing machine
The function of any computing machine, whether it is a simple desk
calculator or an electronic high speed machine, is to do arithmetic. Some
features that are essential and are common to all machines are:-
(i) A store
(ii) An arithmetic unit
(iii) Input and output mechanism.
The exact nature of each of these requirements varies from machine to
machine: for example, on a Brunsviga hand machine the store contains 3
numbers, on DEUCE the total storage space is more than 8,500 numbers and on
the newer (American) machines the capacity is several times this figure.
Similarly, input and output devices vary from hand-switches and dials to
tape readers and punches, etc.
As the speed of the arithmetic operations in increased it becomes
essential to store more numbers inside the machine. This allows storage of
intermediate results and therefore a certain speeding up of the calculation.
If the speed of operations is increased still further, very little of the
time of a calculation is spent in computing and a great deal of time is
taken up by the operator in deciding what is to be done next. The high
speed of operation is completely lost if the operator takes as long to
decide on the next step as on a slow machine. One way out of the difficulty
is to store the sequence of operations (the 'program') in the machine. The
selection of consecutive 'instructions' is now done by the machine and can
be accomplished at much the same rate as the arithmetic. Often it is very
much faster. It is necessary to allow the machine a conditional choice of
next instruction under certain circumstances - a number may be positive or
negative and each case may require different consideration. Such a choice
is called a 'discrimination'.
It is desirable to make out the program in a general way, i.e. the
program should be applicable to a calculation independent of the figures in
the particular case. For example, the method of multiplying matrices does
not depend on the elements of the matrices. The program therefore is made
to refer to the locations in the store, where the required numbers will be
found. Every location in the store is given a unique 'address'. To specify
a number we give the address where the number is stored. We denote by "word"
the contents of any location. Just how numbers find their way into the store
in the first place we must leave for the moment.
For machines of the 'stored program' variety it is necessary to have
a 'control unit' in addition to requirements (i), (ii) and (iii) given
earlier. The function of the control unit is to select instructions in the
correct sequence and to initiate the operations required.
The questions arise of how instructions are made up and how they are
to be stored in the machine. Let us first consider the nature of the instruc-
tions. Every arithmetic operation must specify at least one operand, and in
general two, and also where the result is to be stored. This implies that in
general three addresses must be given, two 'sources' and one 'destination'.
A certain simplification can be achieved if one of the operands is always in
a particular register (generally called the `accumulator') and the result is
also placed in the same register. Only one address has to be stated now.
However, we must add an extra function, to transfer the contents of the
accumulator to other addresses in the store. All the basic functions of which
- 5 -
the machine is capable are numbered (preferably systematically!) and every
instruction now specifies the requisite number of addresses and the
required function. And this gives the clue as to how instructions are
stored they are kept as if they are numbers. Of the digits that corres-
pond to an instruction some will be the function number and some will be
an address (or addresses if several are to be given in every instruction).
The choice of what functions are to be included in the machine's
basic set is one of design and varies from machine to machine. Suffice it
to say that the user is never satisfied with the set supplied. Sometimes
engineering convenience is the dominant factor, at other times simplicity
of programming is purchased at the cost of much extra equipment. The
functions on modern machines include addition, subtraction, multiplication,
division, shifts, comparison and transfer. Other operations can be reduced
to combinations of these simple ones.
Storage of instructions as numbers suggests the possibility of doing
arithmetic on instructions. This is indeed done and is one of the striking
features of automatic computing. Frequently operations are to be performed
on each of a sequence of numbers. Rather than store the instructions
required for dealing with each term we have them only once and always add
sufficient to the address part of the instructions to make them refer to
different members in turn. On some machines there are facilities for
automatic modification of instructions, on others it has to be programmed.
A further consequence of storing instructions in this way is that care must
always be taken. that the control unit selects only actual instructions not
numbers.
Selection of instructions is done in one of two ways. The simpler,
and historically earlier, one is to store instructions in consecutive
addresses and to go through these in sequence. The other way, adopted on
DEUCE, is for each instruction to name its successor. The extra, complica-
tion of this method is tolerated because, on machines like DEUCE, there can
be a great saving of time between operations.
Most electronic machines work in the scale of 2, the binary scale.
This is purely for reasons of electronic convenience as the only digits
occurring are 0 and 1, and it is very simple to represent one of two states.
The computer itself is used to convert numbers to and from the more
familiar decimal scale*.
Machines can be classified into two groups, serial and parallel. In
the serial machine the digits of any word appear one after the other, with
the least significant digit first. Such machines often have delay line
storage, where words are stored as trains of pulses which circulate
indefinitely in delay lines. DEUCE is of this type. The delay line store
is the reason for the non-sequential type of instruction selection -
instructions and numbers are placed so that they emerge from the delay line
at the right time, with as little waiting time as possible. In parallel
machines all the digits of a number are available at the same time and their
significance depends on their position in the number. Parallel machines
can be much faster than serial ones but require more equipment.
Modern machines generally have more than one type of store attached
to them, a high-speed store, with very short access time to all words, and
a much larger backing store with longer access time. On DEUCE the high
speed store consists of mercury delay lines holding 402 words with a maximum
access time of 1024µ sec. and there is a magnetic drum, with a capacity of
8192 wards. Access to a particular word takes about 13 m.sec. in general but
may be as long as 50 m. sec.
* Binary arithmetic is discussed in Appendix 2.
- 6 -
All of the foregoing has been quite general and applies too all high
speed machines. In future we shall be concerned entirely with DEUCE.
I.2 Description of DEUCE
DEUCE (Digital Electronic Universal Computing Engine) is a machine
built by the English Electric Co. Ltd., from designs used by N.P.L. for the
ACE Pilot Model (Automatic Computing Engine). The differences between DEUCE
and the ACE Pilot Model concern certain rationalizations of design and the
size of store.
The machine is of the serial type and uses a system of instructions
which state one source, one destination and the 'next instruction source'.
No function is stated in the instruction word. Instead, a rather curious
system of 'functional sources' and 'functional destinations' is used.
Basically, this means that certain locations in the store have more than one
address attached to them and these extra addresses allow the operations of
arithmetic to be performed. Just how this is done is described in detail in
the succeeding chapters. Every instruction specifies the one that is to
follow - this system causes certain complications in programming but allows
greater speed of operation. Such a system has two addresses for operands
and one for the next instruction and is often known as a '2 + 1 address' code.
There are two kinds of storage. The high speed store consists of
mercury delay lines and holds 402 words in all. There are 12 long delay
lines holding 32 words each and some short lines, known as temporary stores,
which hold one, two and four words. The time taken for the contents of one
delay line to circulate is called a 'major cycle', the time of one word is
a 'minor cycle'. There are 32 minor cycles in one major cycle. The words
are all of the same length, 32 binary digits (about 10 decimal digits).
Words are stored in the delay lines as a succession of pulses of 1µ sec
duration. A minor cycle is therefore 32 µ sec and a major cycle is 1O24µ sec,
or just over 1 m.sec. All operations are performed in the high speed store.
The secondary storage is a magnetic drum which holds 8192 words,
disposed in 256 tracks of 32 words each. The drum itself is a rapidly
rotating cylinder coated with magnetic material. There are 'reading heads'
and 'writing heads', to transfer information to and from the high speed
store. A whole track is transferred with one instruction. Access to the
drum is much slower than to the high speed store.
Additional storage on magnetic tape is projected. This has virtually
unlimited capacity, and transfer to and from the high speed store is more
rapid then with the drum. Access time, however, may be much longer because
it may be necessary to search through the tape.
Input and output are by means of conventional Hollerith punched card
equipment. Cards may be read at a rate of 200 per minute and punched at
100 cards per minute. Results are printed on an ordinary tabulator - there
is no printer attached to DEUCE. 64 columns of a card are used by DEUCE,
which means that 24 words punched in binary can be read from one card.
Special conversion routines are required to convert decimally punched
information into the binary required by the machine and vice versa*.
(The operation of the reader and punch are controlled entirely by the
program.) Extra input and output devices using 5-hole teleprinter tape may
be added. Nothing will be said here about such devices.
* Such routines already exist and can be incorporated into programs.
- 7 -
The console, at the front of the machine, has a bewildering array of
keys and lights and two cathode ray monitor tubes. These tubes display the
contents of the temporary stores and any selected long delay line. Inspec-
tion of the monitors can give an indication of how a computation is pro-
ceeding and can be used when testing programs. The most important row of
hand-switches is called the Input Dynamicizer (I.D.) and. can be used as an
extra input. One word can be stored on the I.D. switches. There are two
rows of lights above the I.D. switches. The lower is connected to the I.D.
and shows which keys have been depressed. The upper rows of lights is an
additional form of output, called the Output Staticizer (O.S.). One word
can be displayed on the 0.S. lamps. A further row of 13 lamps displays the
instruction (in abbreviated form) that is about to be obeyed. These are
the Instruction Staticiser lamps (I.S. lamps). Normally they are changing
too rapidly to be of any use, but can be very valuable when testing programs.
All the other keys are concerned, in some way or other, with facilities for
program testing and will be described in Part II.
Physically, the DEUCE consists of a cabinet, roughly 10' x 8' x 6',
which houses all the circuitry needed and has the console at one end. The
card reader is an the left of the console and the punch is on the operator's
right. The delay lines are kept in a thermostatically controlled mushroom-
shaped bin, away from the main body of the machine. The power units
associated with the machine are also separate. Power consumption is about
8kW and air-cooling of the frame is necessary.
I.3 DEUCE instruction code
In DEUCE (most) instructions involve a transfer of a number in one
position in the store (the 'source') to somewhere else in the store (the
'destination'). In general the number in the source is unchanged. Every
instruction also specifies the address of the next instruction. This
arrangement gives a system known as a '3 - address code'*.
It is not immediately obvious how moving numbers from one position
to another performs any useful operations. The trick is to associate
several addresses with a particular storage position and then make each of
these addresses have a different function. As an example, one of the stores,
called TS 13, has three destinations associated with it, D 13, D 25 and
D 26. Sending a number to D 13 replaces the content of TS 13 by this
number. If the number is sent to D 25 it is added to the content of TS 13:
the sum is now stored in TS 13. Subtraction from TS 13 is done by sending
the number to D 26. In this way it is possible to do arithmetic.
Some of the addresses used for sources and destinations do not
correspond to a position in the store but to a part of the control unit.
An example is D 27, which is the 'discriminator' that examines the sign of
a number and affects the choice of the next instruction. Source 27 does
not exist as a storage position, either, but always gives a word with a
P 1. The reader will notice that there is no connection between source 27
and destination 27.
A complete list of sources and destinations will be found in
Appendix 1. The schematic diagram of DEUCE (Fig. 1) will also be found
helpful.
We now examine the high speed store in some detail.
These are:
* The DEUCE system is sometimes referred to as a '2 + 1 address code'.
- 8 -
(i) 12 Delay Lines (DL) each holding 32 words. The DL's are numbered
1, ..., 12 and the minor cycles of a DL are numbered 0, ..., 31. We write
Am for minor cycle m of DL A. Only those minor cycles with the same number
are available at the same time.
DL's 1, ..., 8 are the only ones available directly as next instruc-
tion sources.
(ii) 4 Temporary Stores (TS), numbered 13, 14, 15, 16. They each hold
one word, which is available in every minor cycle.
(iii) 2 Quadruple Stores (QS), QS 17 and QS 18: each holds four words.
The minor cycles are numbered 170, 171, 172, 173 and 180, 181, 182, 183;
minor cycle m is available at the same time as minor cycle 4r + m of a
DL, (see Appendix 1).
(iv) 3 Double Stores (DS), DS 19, 20, 21, with two words in each. The
minor cycles are written as 192, 193, etc. (not 190, 191). They are avail-
able for computation only with minor cycles of same parity.
Addresses 1, ..., 21 used as source or destination refer to the
appropriate store. The exact method of addressing a particular word in a
DL will be explained later (in I.6). For the moment, we may assume that
there is a way of executing an instruction like
93 - 13 ,
which copies the content of 93 into TS 13.
In general, no confusion arises if we drop the letters DL, TS, QS,
DS. If necessary, the contents of Am are denoted by C(Am), Thus, C(93)
means 'the word in m.c. 3 of DL 9', C(14) is the word in TS 14, etc. Quite
often, one refers to 14, say, meaning C(14). Saying 'Is 14 positive or
negative?' does not refer to the number 14, but to C(14). It is convenient
to write C'(n) to denote the contents of address n immediately after an
operation. On occasion, however, even this is abbreviated to n'.
There are some extra addresses in the computer. These are 0,
22, ..., 31. Their effects are different depending on whether they are used
as source or destination. The only special sources and destinations that we
shall need for the moment are:-
Sources 0, 23, 24, 27, 28, 29, 30, 31
and
Destinations 25, 26, 27, 28, 29
Their effects are:-
Source 0: This is the input of the machine. All information that
passes from the external world into the computer has to go through S.O. If
the card reader is running S.0. gives the word corresponding to the contents
of the row just passing the reading brushes. Otherwise S.O. takes the word
on the I.D. switches.
Source 23 and Source 24: are connected to TS 14. They give words which
are respectively half and double C(14). The instruction
23 - 13
places ½C(14) in TS 13. Similarly,
24 - 15
puts 2C(14) into TS 15.
- 9 -
Because the machine works in binary notation, multiplication and
division by 2 corresponds to a bodily shift of the digits in a word.
Sources 23 and 24 give a shift down and shift up (of C(14)) respectively.
These shifts are correct arithmetic shifts. Care is necessary when
doubling a number to avoid exceeding capacity.
It is perfectly permissible to send a number from Source 23 or 24
to destination 14. Note that the effects of
23 - 14
24 - 14
and
24 - 14
23 - 14
need not be the same. In the first case a digit is lost from the least
significant end, in the second example we lose the most significant digit.
These are the only cases in which the use of Sources 23 and 24 can affect
the content of TS 14.
Sources 27, 28, 29, 30, 31 all give special combinations of digits.
S 27 is a P 1 \
\
S 28 is a P 17 > and nothing else.
/
S 29 is a P32 /
S 30 gives a word consisting entirely of zeros.
S 31 gives a word consisting entirely of ones
(This is - P1).
The reason for the choice of these combinations will become apparent
in due course.
27 - 13
puts a P1 into TS 13,
30 - 14
clears TS 14
Destinations 25 and 26. respectively add to TS 13 and subtract from
TS 13.
14 - 25
gives C'(13) = C(13) + C(14),
15 - 26
gives C'(13) = C(13) - C(15)
Note that it is possible to use 13 as a source with these
destinations. Thus
13 - 25
gives C'(13) = C(13) + C(13) = 2C(13),
13 - 26
has the same effect as
30 - 13
- 10 -
Destinations 27 and 28 are the discriminators, which allow a choice
of next instruction.
D 27 examines the sign; (zero is a positive number).
D 28 tests for zero.
Examples are:
(1) 13 - 27
/ \
+ -
/ \
C(13) ≥ 0 C(13) < 0
(2) 14 - 28
/ \
z nz
/ \
C(14) = 0 C(14) ≠ 0
These discriminators allow one to use a particular loop of instruc-
tions several times until some criterion is satisfied. The normal state
of the discriminators is 'off', i.e. positive for D 27, zero for D 28. We
make the convention in writing out programs that the off side is the left
hand branch. It is an additional safeguard to mark the branches, as in
the examples. The two alternative instructions following a discrimination
must be in consecutive minor cycles of the same DL,
This leaves
Destination 29 This is the output organ of the machine. All
information from the machine to the external world has to go through D 29.
If the punch is running, the instruction
A - 29
causes C(A) to be punched on a row of cards. If the punch is idle C(A) is
displayed on the O.S. lamps.
All the sources and destinations described affect only one word, of
32 binary digits, at a time. This sort of arithmetic is called 'single
length'.
There are special facilities in DEUCE that allow the transfer by one
instruction of more than one word. All the transfers illustrated above were
single transfers. It is possible to transfer two (consecutive) words or any
number up to 32*. When transferring more than two words certain extra condi-
tions have to be satisfied. These will all be explained in I.6. For
multiple transfers we write the number of minor cycles in brackets beside
the instruction. Examples of such long transfers are:-
* It may soon be possible to transfer four words.
- 11 -
(1) 12 - 1 (32 m.c.)
which transfers all the 32 words in DL 12 into DL 1
(2) 16 - 17 (4 m.c.)
which puts C(16) into the four minor cycles of Q.S. 17.
(3) 24 - 14. (3 m.c.)
which gives. C'(14) = 23C(14).
(4) 11 - 25 (32 m.c.)
which gives C'(13) = C(13) + C(110) + C(111) + ... + C(1131), i.e. adds all
of DL 11 into TS 13, all numbers being single length. Any carry is lost.
The next section, I.4, shows how simple programs can be made up with
the apparatus available.
I.4 Some simple programs
There are usually several ways of programming a problem, and often
no single best way. The solutions given below should be as good as any the
reader can produce.
(1) x = c(14), y = c(16). Put (x + y) in 15.
14 - 13 C'(13) = x, C'(14) = x
16 - 25 C'(13) = x + y, C'(16) = y.
13 - 15 C'(13) = x + y, C'(15) = x + y.
Notice that if w C(13) is non-zero, the program
14 - 25 C'(13) = w + x
16 - 25 C'(13) = w + x + y
13 - 15 C'(15) = w + x + y
puts (w + x + y) into TS 15 and so gives an incorrect result. Never assume
that any storage location contains zero unless this is stated.
(2) x = C(14), y = C(16). Put (2y - x) in 13
16 - 13 C'(13) = y.
16 - 25 C'(13) = 2y.
14 - 26 C'(13) = 2y - x.
If w = C(13) is not zero, the program
14 - 26 C'(13) = w - x
16 - 25 C'(13) = w - x + 2y
(2 m.c.)
gives the wrong result.
- 12 -
(3) x = C(14), y = C(16). Put (2x - y) in 13.
24 - 13 C'(13) = 2x, C'(14) = x
16 - 26 C'(13) = 2x - y
The number in 14 is unchanged by the first instruction.
(4) x = C(192), y = C(203). Put (2x + y) in 14
203 - 13 C'(13) = y
192 - 25 C'(13) = x + y
192 - 25 C'(13) = 2x + y
13 - 14 C'(14) = 2x + y
The program
202 - 13
192 - 25 (2 m.c.)
13 - 14
is meaningless. If z is the number in 193, the instruction
19- 25 (2 m.c.)
will add from 19 into 13 for two successive minor cycles, one even and one
odd. So x and z will be added into 13 and the result will be (x + y + z).
It is impossible to add 2x in one instruction in this case.
(5) x = C(14). Put 2x in 14.
24 - 14
(6) x = C(14). Put 8x in 14.
24 - 14 (3 m.c.)
At the end of one minor cycle 2x has replaced x in 14. So in the second
minor cycle 4x replaces 2x, and 8x replaces 4x in the third minor cycle.
(7) x = C(14). Put 5/4x in 14.
14 - 13 C'(13) = x, C'(14) = x
23 - 14 C'(13) = x, C'(14) = ½x
23 - 25 C'(13) = 1¼x, C'(14) = -½x.
- 13 -
(8) x= C(14) Put |x| in 13.
[|x|, the "modulus of x", means the positive number x if x is positive;
the positive number -x if x is negative].
14 - 27 Test. sign of x.
/ \
+/ \-
14 - 13 30 - 13 C'(13) = 0.
14 - 26 C'(13 = -x.
(9) x = C(192), y = (193). Put the greater into 212
192 - 13 C'(13)= x
193 - 26 C'(13)= x - y
13 - 27 Test sign of x - y.
/ \
+/ \-
192 - 212 193 - 13
13 - 212
It is impossible to write the one instruction
193 - 212
on the negative side of the discrimination, because a word cannot come out
of DS 19 in an odd minor cycle and simultaneously go into DS 21 in an even
minor cycle,
(10) x = C(14), y = C(15). Put the numerically greater in 13;
i.e. if |x| (> or =) |y| put x in 13, if |x| < |y| put y in 13.
30 - 13 C'(13) = 0
14 - 27 Inspect sign of x
/ \
+/ \-
C'(13) = x = |x| 14 - 25 14 - 26 C'(13) = -x = |x|
\ / Now C'(13) = |x|
15 - 27 Inspect sign of y.
/ \
+/ \-
C'(13) = |x|-y = |x|-|y| 15 - 26 15 - 25 C'(13) = |x|+y = |x|-|y|
\ /
13 - 27 Inspect sign of |x|-|y|
/ \
+/ \-
14 - 13 15 - 13
Notice that it is x or y, not |x| or |y|, which must be put in 13 at the
end.
There is a shorter way of doing this example when source 26 has been
explained; see I.13.
Although the use of the multiplier will not be explained in full
until , more interesting examples can be constructed if multiplication
is possible. So the following method of multiplying will be used for the
moment:
- 14 -
If x and y are the fractions to be multiplied, put them in 14 and 16
and write MULT as an order. The product xy will be found in 213. The
numbers in 14 and 16 are undisturbed, but the numbers in 13, 15, 212 and
213 are lost.
(11) x = C(170), y = C(171). Put xy in 172.
170 - 14 C'(14) = x .
171 - 16 C'(16) = y.
MULT C'(213) = xy.
213 - 13 C'(13) = xy.
13 - 172 C'(172) = xy.
(12) x = C(14). Calculate x13 as quickly as possible.
Multiplication is a slow. process compared with addition and subtraction, so
the aim must be to use as few multiplications as possible. 5 multiplica-
tions are necessary
14 - 16 C'(16) = x, C'(14) = x
MULT C'(213) = x2
213 - 16 C'(16) = x2, C'(14) = x
MULT C'(213) = x3
213 - 14 C'(14) = x3, C'(16) = x2
MULT C'(213) = x5
213 - 16 C'(16) = x5, C'(14) = x3
MULT C'(213) = x8
213 - 14 C'(14) = x8, C'(16) = x5
MULT C'(213) = x13
213- 13 C'(13) = x13.
(13) r is an integer. Given r = C(15), r2 = C(16), put (r + 1) in
15 and (r + 1)2 in 16 and punch (r + 1)2; assume that the punch is running.
This can be done without using the multiplier because (r + 1)2 = r2 + 2r + 1;
in fact this is the quickest way. In any case the method of multiplication
described above applies only to fractions.
- 15 -
16 - 13 C'(13) = r2
15 - 25 (2 m.c.) C'(13) = r2 + 2r
27 - 25 C'(13) = r2 + 2r + 1
13 - 16 C'(16) = (r + 1)2
15 - 13 C'(13) = r
27 - 25 C'(13) = r + 1
13 - 15 C'(15) = r + 1
16 - 29 Punch C(16) = (r + 1)2
If the last instruction is made to lead back to the first one, the
next time this string of instructions has been obeyed (r + 2)2 will be in
16 and (r + 2) in 15; the following time (r + 3)2 and (r + 3) will be in
16 and 15 respectively.
I.5 Loops and counting
One of the great advantages of digital computers is their speed of
operation. On DEUCE about 16,000 instructions could be obeyed in one
second. This is hardly an advantage if all 16,000 instructions have to be
written out and punched separately. The speed of a digital computer can
only be utilised if it is possible to obey a loop of instructions many
times and eventually to leave the loop.
The decision whether or n ;)t to leave the loop will consist of a
discrimination on some quantity which will be encountered each time round
the loop. What this quantity is depends entirely on the problem: sometimes
it will be suggested by the form of the problem (see Example 4 below);
sometimes it will be a counter which goes up (or down) in steps of 1 every
time the loop is traversed, and this counter may or may not be used elsewhere
in the loop - Examples 2 and 3 below give different uses of counters.
Example 1
Punch the squares of the numbers 1, 2, ... 10 in binary.
Example 13 of I.4 gives a method by which, if r2 and r are given in
16 and 15, they can be replaced by (r + 1)2 and r + 1, and (r + 1)2 punched.
So if the last instruction leads straight back to the first the numbers
(r + 1)2, (r + 2)2, (r + 3)2 and so on will be punched. What remains to be
done is to arrange to start with the right value of r and to come out of
the loop at the right time.
It is a good principle in general to arrange the method leaving
the loop before deciding how to start going round it. because the initial
conditions which have to be set before the loop is entered may depend on
what test is used at the end. The next example will show this more clearly,
but this principle will be followed in all examples.
After the sequence of instructions given in Example 13 of I.4 have
been obeyed, 13 and 15 both contain (r + 1) and 16 contains (r + 2)2;
(r + 1)2 has just been punched. Now suppose that the number 10 has been
stored somewhere, say in 115.
- 16 -
Add the instructions
115 - 26 | C'(13) = (r + 1) - 10
|
13 - 28 |
/ \ |
z/ \nz |
/ \ ---->|
to those already given, with the non-zero side of the discrimination leading
to the 16 - 13 instruction. The zero side will be taken. only when r + 1 =10,
i.e. 102 has just been punched.
If the 16 - 13 instruction is preceded by
30 - 16
30 - 15
we have arranged that r2 = 0 and r = 0 initially. Therefore 12 will be
the first number punched.
The complete program is:
10 - 24 (Start punch)
30 - 16 C'(16) = 0
30 - 15 C'(15) = 0
16 - 13 <---------| C'(13) = 0 1 4 9 16 25 36 49 64 81
|
15 - 25(2 m.c.) | C'(13) = 0 3 8 15 24 35 48 63 80 99
|
27 - 25 |
|
13 -16 | C'(16) = 1 4 9 16 5 36 49 64 81 100
|
15 - 13 | C'(13) = 0 1 2 3 4 5 6 7 8 9
|
27 - 25 |
|
13 - 15 | C'(15) = 1 2 3 4 5 6 7 8 9 10
|
16 - 29 X | Punch 1 4 9 6 25 36 49 64 81 100
|
115- 26 |(Subtract 10)
|
13 - 28 | C(13) = -9 -8 -7 -6 -5 -4 -3 -2 -1 0
| |
|--nz--------->| Back Back Back Back Back Back Back Back Back On
z|
9 - 24 (Stop punch)
(Three details, the 10 - 24 and 9 - 24 instructions and the X after the
16 - 29 instruction, have been put in to make the example realistic. They are
explained in . )
This method has considerable flexibility. If the squares of the
integers up to 10002 were wanted, the only modification necessary would be
to change the constant 10 in 115 to 1000.
Example 2
x = C(14). Calculate x13 in as few instructions as possible and place
it in 13.
- 17 -
Suppose at some stage xr is in 16 and that x is never disturbed from
14. Then the instructions
MULT
213 - 16
replace xr by xr+1. These will be the basic instructions of our loop.
We must next decide how to get out of the loop. In the previous
example we had a number r stored in 15 which increased by 1 each time round
the loop; a discrimination on r was used to make the exit from the loop.
This time we do not have a convenient counter like r already in use, so one
will have to be introduced. It turns out that it is a little more con-
venient to keep (13 - r), which goes down in steps of 1 until it reaches 0,
than r, which would go up in steps of 1 until it reaches 13. (The reader
might like to do this case as an exercise.)
This counter cannot be kept in 13, 15 or. 212 because MULT disturbs the
contents of these stores, so it will be kept in 192, Therefore, if 192
contains (13 - r) when 16 contains xr, we must change C(192) to (12- r)
when we change C(16) to xr+1. So the loop consists of the instructions
MULT <------|
|
213 - 16 | C'(16) = xr+1
|
192 - 13 | C'(13) = 13 - r
|
27 - 26 |
|
13 - 192 | C'(192) = 12 - r
|
192 - 28 |
| ---nz-->| Out when r 12, C(16) = xr+l = x13
z|
213 - 13
We must now arrange to enter the loop with xr in 16 and (13 - r) in
192 for whatever value of r we like to choose. It is simplest to put x in
16, so 12 must be put into 192.
As in the last example, when the constant 10 was assumed to be stored
115, we shall need to have a constant. How this constant gets into. the store
is a question which often worries beginners; it cannot be satisfactorily
answered until the way in. which the program is read in is explained in ,
but it can be said now that it gets into the store at the time the instruc-
tions are read in.
Suppose that the constant is stored in 118. The obvious choice of
constant seems to be 12, so that we add the two instructions
14 - 16 C'(16) = x
118 - 192 C'(192) = 12
at the head of the loop. As we have to calculate x13 it would look tidier
if the constant 13 were used; but it looks as though four instructions
- 18 -
14 - 16 C'(16) = x
118 - 13 C'(13) = 13
27 - 26 C'(13) = 12
13 - 192 C'(192) = 12
would have to be added at the head of the loop.
But suppose we have two instructions
14 - 16 C'(16) = x
118 - 192 C'(192) = 13
after which we enter the loop at its third instruction, 192 - 13. Then 1
will be subtracted from the number 13 in 192 before any multiplication is
done.
Writing the instructions in a different order on the paper, but
obeying them in exactly the same order, we get the final form of the loop:
14 - 16 C'(16) = x
118 - 192 C'(192)= 13
192 - 13 <-----| C'(13) = 13 12 11 10 ....... 2 1
|
27 - 26 |
|
13 - 192 | C'(192)= 12 11 10 9 ....... 1 0
|
192 - 28 |
|<---z-----|nz | On On On On On Jump
| | | |
| MULT | |
| | | |
| 213 - 16 | C'(16) = x2 x3 x4 x5 ...... x13 |
| |---------->| |
| |
|----> 213 - 13 C'(13) = x13
There are 6 general points which this example illustrates:-
(a) The order in which the loop was constructed was:
(i) Basic orders: form xr+1 from xr;
(ii) "Red-tape" orders: changing the counter and testing
its value;
(iii) Setting the initial conditions;
although in its final form of the loop this is not apparent.
Moral: When a loop is being constructed the programmer should keep to
this order of working.
- 19 -
(b) If the arrow leading from the 213 - 16 instruction to the 192 - 13
instruction had been taken one line higher to include the 118 - 192
instruction in the loop, the number in 192 would be set at 13 every time
round the loop and so the loop would never be left. This may seem a stupid
thing to do, but it illustrates one of the common mistakes in programming.
Moral: Do not include in the loop one or more of the instructions
which set initial conditions.
(c) The three instructions
192 - 13
27 - 26
13 - 192
reduce the counter, and the one instruction
192 - 28
following them tests the counter. In fact, what the program does is
Reduce count
Test count
If, instead, the sequence had been
Test count
Reduce count
the result would have been to produce x14 unless the constant in 118 were
changed from 13 to 12.
The blunder of going round a loop one time too few or too many is
probably the most common of all programming mistakes.
Moral: Beginners (and others) would be well advised always to use
the sequence
Charge count
Test count
(d) The reader may wonder why the number 13 was transferred from 118 to
192 before being used for counting. There are two reasons of which the
second is the more important.
Firstly, the sequence
118 - 13
27 - 26
13 - 118
takes longer to obey than that used in the loop. The number 13 cannot be
stored in DS 19 when the program is being read in, but it can be stored in
a delay line.
- 20 -
Secondly, in the loop given, the number in 118 is not disturbed. So
if there is an outer loop leading back from the 213 - 13 instruction at the
end of this inner loop to the 14 - 16 at its beginning, leaving y in 14 this
time, the inner loop will produce y13 in 13. If counting had taken place in
118 there would have been 0 in 118 the second time the loop was started, and
-1 when the test was first made; to get a correct result the second time,
an instruction in the outer loop would have to reset the number 13 in 118
before the inner loop was re-entered. A section of program for which this
does not have to be done, such as the example given, is called "self-
resetting".
Moral: Each section of a program should be made self-resetting
unless there is a good reason to the contrary.
(e) No extra thought is needed to make this program calculate x15, say,
instead of x13. All that needs modifying is the parameter in 118. Compare
this with example 12 of I.4, which would have to be completely reprogrammed.
Of course this gain in flexibility is accompanied by a loss in speed; the
two usually go together. So do a saving in the number of instructions and
a loss in speed.
Moral: Programs should be made flexible unless speed is essential.
(f) The constant in 118 is n if xn is - to be calculated. If "Test count"
has preceded "Change count" (see (d) above) it would have to be (n - 1).
The parameter n is much more likely to have been used in another part of the
program than the parameter (n - 1).
Moral: The parameters of a program should be the convenient ones.
Example 3
Given x in (16), and 10.2-14 in 193, sum the polynomial 2-14
(10x9 + 9x8 + ... + 1) and put the result in 15. On DEUCE fractions are
normally regarded as having 30 binary digits below (to the left of) the
binary point and 2 bits above the point. The fraction 2-14 will consist
of one digit only, the P17 digit. This digit is always given by source 28.
The method used to sum the polynomial is that known as "nested
multiplication" and is commonly used on desk machines. We evaluate
(....(((10.2-14 x + 9.2-14) x + 8.2-14) x + 7.2-14) ....) x + 1.2-14.
Suppose at some stage we have
Sr = 10.2-14 x9-r + 9.2-14 x8-r + .... + (r + 1) 2-14
in 14. Obviously we need to end when r = 0.
One step in the calculation consists of the multiplication of
Sr by x and the addition of r.2-14; the result will be Sr-1. We shall need
to keep a counter r.2-14, say in 192, and this counter will have to be
reduced by 2-14.
The operative orders in the loop are:
- 21 -
MULT c(14) = Sr, C(16) = x, undisturbed
213 - 13 c'(13) = Srx
192 - 25 C'(13) = Srx + r 2-14 =Sr-1
13 - 14 C'(14) = Sr-1
192 - 13 C'(13) = r 2-14
28 - 26 Source 28 gives P17, i.e. 2-14
13 - 192 C'(192) = (r - 1) 2-14
We have now replaced Sr and r 2-14 by Sr-1 and (r- 1)2-14
respectively. Work has finished when S0 is obtained, so one further
instruction
192 - 28 |
/ \ |
z/ \nz--->|
is needed to close the loop. The non-zero side leads back to MULT.
Finally we set the initial conditions. There are two alternatives
here; either S10 = 0 and 10.2-14 in 14 and 192 respectively, or
S9 = 10.2-14 and 9.2-14 in 14 and 192 respectively. By a trick similar to
that in example 2 we can use the second alternative and so save going round
the loop once compared with the first. alternative.
We start with the instructions
193 - 14 C'(14) = 10.2-14 = S9
193 - 13 C'(13) = 10.2-14
and enter the loop at the 28 - 26 instruction, not at the MULT instruction.
The full program is:
193 - 14 Set S9 = 10.2-14
193 - 13 C'(13) = 10.2-14
28 - 26 <----|
|
13 - 192 | C'(192)= 9.2-14 8.2-14 7.2-14 ..... 1.2-14 0
|
# 19 - 28 |
| |
|<--z---| |
| |nz | On On On ..... On Jump
| | | |
| MULT | |
| | |
| 213 - 13 | C'(13) = S9x S8x S7x ..... S1x |
| | |
| 192 - 25 | |
| | |
| 13 - 14 | C'(14) = S8 S7 S6 ..... SO |
| | |
| 192 - 13 | C'(13) = 9.2-14 8.2-14 7.2-14 ..... 1.2-14|
| |-------->| |
| |
|-> 14 - 15 C'(15) = So
# Should be 13 - 28
- 22 -
The reader should check that none of the morals, of the previous
example are offended.
As far as moral (e) is concerned, he may notice that changing the
number in 193 will give different approximations to the infinite series
2-14 (1 + 2x + 3x2 + 4x3 .....) = 2-14 (1 - x)-2
Example 4
Given constants a, b, c and h in 171, 172, 173 and 170 respectively
where a, b, and h are strictly positive, find the value of r (an integer)
such that xr = rh gives the smallest value of yr = ax4r - bxr + C. Place
the corresponding values of xr and yr in 192 and 193 respectively. Assume
that numbers are within the capacity of the machine.
If y = ax4 - bx + c, y = 4ax3 - b. The gradient is negative at
x = 0 and becomes 0 at a point where x is positive. The question does not
ask that this point should be found; what is wanted is that y should be
evaluated for x = 0, h, 2h, 3h .... and the smallest y found.
The basic operations of the loop will be:
Given xr = rh in some store
Evaluate yr <------------------|
|
Test sign of yr - yr-1 |
/ \ |
+/ \- |
/ \ |
END. Replace yr-1 by yr |
|
yr-1 and xr-1 are required values. Replace xr_1 by xr |
|
Calculate xr+1 |
| |
|------------------->|
Notice that xr-1 and yr-1 are both needed until the discrimination
has taken place.
The first discrimination must be on y1 - yo, as the simplest method of
starting the calculation is to set xo = 0, yo = C and enter the loop at
"Calculate xr+1".
We shall keep xr-1 and yr-1 in 192 and 193; xr will be stored in 16
when it has been calculated for use in forming yr.
The full program is:
- 23 -
30 - 192 xo = 0 ------
Set initial conditions
173 - 193 yo = C
------
192 - 13 <--| xr-1
|
170 - 25 | xr_1 + h = xr Calculate xr
|
13 - 16 | Xr ------
|
171 - 14 | a
|
MULT |
|
213 - 14 | axr
|
MULT |
|
213 - 14 | ax2r
|
MULT |
| Calculate yr
213 - 13 | ax3r
|
172 - 26 |
|
13 - 14 | ax3r - b
|
MULT |
|
213 - 13 | ax4r - bxr
|
173 - 25 | ax4r - bxr + C = yr
|
193 - 26 |
| Test sign of yr - yr-1
13 - 27 | yr - yr-1 -------
+ | |
END--------| |
| - |
193 - 25 | Replace yr-1 by yr
|
13 - 193 | yr ------
|
16 - 192 | Xr Replace xr-1 by xr
|--------| ------
In this example it is yr that determines whether the exit from the
loop should be made, although the other variable xr is the. counter which
goes up in equal steps.
I.6 The instruction word
Until this point we have written flow diagrams for programs without
considering how they are fed into the machine or what the machine does with
them. This section describes the form of the instruction used inside DEUCE
which is not the same as that used so far.
- 24 -
So far we have not considered where each instruction is stored when
writing flow diagrams. It is only when the flow diagram has been written
that the next stage allocation of storage positions for the instructions and
for constants can take place; and this is followed by the stage known as
"detailed coding", in which instructions are written out in the exact form
in which they are stored in the machine. The second stage allocation of
stores is an art in itself. An experienced programmer will usually code a
loop of in instructions to take less time in operation than would an
inexperienced man: this is the art of "Optimum Programming" (I.10), often
(wrongly) considered to be one of DEUCE'S chief snags by programmers used to
other machines. It can only be learnt by practice when the methods of
detailed coding are familiar, so in this section we shall assume that
storage locations have already been allotted and that this has not been done
very well.
DEUCE'S word-length of 32 bits is rather shorter than that of more
modern machines. These often have a word of about 40 bits and pack 2
instructions into a word: because of its cumbersome order code DEUCE has
only one instruction in each word.
A DEUCE instruction has eight things to specify:-
(i) Source
(ii) Destination
(iii) Minor cycle when transfer starts
(iv) Length of transfer
(v) Delay line of next instruction
(vi) Minor cycle of next instruction
(vii) Whether the instruction is a stopper
(viii) Auxiliary staticizer
Source and destination
When we write the instruction 115 - 26 we mean that the machine must
make a transfer from Source 1 to Destination 26, starting (and ending) in
minor cycle 15. In the detailed form of the DEUCE instruction the source
number will be 1 and the destination number 26.
Wait number
The designers of DEUCE might have decided that the transfer specified
by each instruction should always take place 2 minor cycles after the minor
cycle of the instruction*. This would have meant that any instruction
referring to a number in 115 would have to be stored in minor cycle 13, and
so there could be only 8 such instructions in the high-speed store at any
one time. This would place an impossible burden on the programmer, so 5
bits in the instruction, the Wait Number, are provided to specify the minor
cycle in which transfer starts. The wait number is not just the number of
this minor cycle. The precise form is described below.
* This is virtually what the designers of MOSAIC did decide, as rather
different considerations applied on their machine.
- 25 -
Next Instruction Source (NIS) and Timing Number
Some machines expect the instructions to be stored in the sequence
in which they are written in the flow diagram so that instructions generally
do not specify where their successors are stored; but on DEUCE every
instruction specifies the delay line and the minor cycle in which the next
instruction is stored, and a string of instructions obeyed consecutively may
be scattered through the store.
Instructions can go into the control of DEUCE to be obeyed from delay
lines 1 to 8 only, so 3 binary digits are needed to specify the Next
Instruction Source - always abbreviated to NIS. NIS 1 to 7 refer to delay
lines 1 to 7 respectively and NIS 0 is used for DL 8. In addition a 5-bit
number, the Timing Number, specifies which of the 32 words in that delay line
is the next instruction; but the timing number like the wait number is not
just the number of the minor cycle of the next instruction.
Characteristic
In I.3 the possibility of one transfer going on for up to 32 minor
cycles was mentioned. The length of the transfer depends on the wait number,
the timing number and a 2-bit number called the Characteristic; but
whatever the value of the characteristic, the wait number specifies the
first minor cycle of transfer and the timing number specifies the position
of the next instruction*. DEUCE like certain aborigines, distinguishes only
between one, two and many minor cycles of transfer; the three cases are
called single transfer, double transfer and long transfer and the correspond-
ing values of the characteristic are 0, 2 and 1.
Characteristic 3 at present has rather an odd effect; it should
never be used because a proposal has been made to modify DEUCE and produce
a different result.
Go digit
The most significant bit of the word, used as the sign digit of a
number, is the Go Digit of an instruction. Normally it is 1; but if it is
0 the machine waits, just before obeying the instruction, until a pulse
called a "single-shot" is given. Then the instruction is obeyed and normal
operation continues.
The single-shot can be given from a key on the console: this
facility is used when testing programs. It is also given by the reader or
the punch whenever a row of a card comes into position. On the punch for
instance the user makes the instruction to punch each row a "stopped"
instruction by making the go digit 0 - he writes a cross after the instruc-
tion in the flow diagram, e.g.
16 - 29 X
When this instruction is reached the machine waits for a single-shot before
obeying it; as the next row of the card comes into position under the
punch knives a circuit in the punch supplies the single-shot and the number
in 16 is punched. The machine then goes on to obey the following instruc-
tions at full speed.
Auxiliary Staticizer
This is used in Automatic Instruction Modification and is explained
in I.9.
* Except, perhaps, in the case of a discrimination.
- 26 -
Layout of instruction word
Representing each of the 32 digits by a 1, the instruction is laid
out as follows:
1 111 11111 11111 11 11111 1111 11111 1 1
A NIS S D Ch W J T G
Digit 1 : A Auxiliary staticizer: used in automatic
modification of instructions (see I.9)
Digits 2- 4 : NIS, the Next Instruction Source
Digits 5- 9 : S, the Source
Digits 10-14 : D, the Destination
Digits 15,16 : Ch, the Characteristic
Digits 17-21 : W, the Wait number
Digits 22-25 : J, the Joe digits (etymology unknown); not used
in interpreting the instruction; but see I.8
for their use in counting
Digits 26-30 : T, the Timing number
Digit 31 : not used in interpreting the instruction
Digit 32 : G, the Go-digit.
Wait and timing numbers
There is a fifth temporary store, TS Count, as well as TS 13 to 16.
In operation it behaves very differently from them because instructions are
sent to it to be obeyed; and they do not usually go to it as they would to
any other destination, but along a special Next Instruction highway.
(Nothing can. be taken out of TS Count into the rest of the store.)
If an instruction specifies that the next one is stored in 117
circuits allow one instruction to flow from DL 1 along this special highway
into TS Count during minor cycle 17. Minor cycle 18 is spent in setting-up
this instruction, so this minor cycle is known as the set-up minor cycle.
The earliest that this instruction can be obeyed is in minor cycle 19;
in this case the wait number is 0. If the transfer is not to start until
minor cycle 20 the wait number must be 1; if the machine is to wait two
minor cycles until minor cycle 21 the wait number is made 2.
In general, if an instruction stored in minor cycle m is to be
obeyed starting in minor cycle F, the wait number is made (F - m - 2)
because, when the instruction is obeyed, the order of events is:
m.c. m Instruction flows into TS Count
m.c. m + 1 Set-up minor cycle
m.c. m + 2 \
to > Wait for (F - 1) - (m + 2) + 1 = F - m - 2 minor cycles
m.c. F - 1 /
m.c. F Instruction starts to be obeyed.
- 27 -
So the wait number W is defined by
W = F - m - 2 (mod 32)
Conversely F = m + W + 2 (mod 32)
(The words "mod 32 are included because F, m and W must all lie
between 0 and 31: they say that if a number calculated by one of these
relations is not in this range, 32 must be added or subtracted until it
does.)
Exactly the same procedure holds when the timing number is being
calculated. If an instruction in minor cycle m is followed by one in minor
cycle t, all the minor cycles from (m + 2) to (t - 1) inclusive are spent
waiting for the next instruction - the instruction may be obeyed during this
time - so the timing number T is defined by
T = t - m - 2 (mod 32)
Conversely t = m + T + 2 (mod 32)
The way in which the machine obeys any instruction is:
If the instruction N, S-D, Ch, W, T is stored in minor cycle m, its
effect is to start the transfer S-D in minor cycle m + W + 2 and then to
fetch the next instruction from minor cycle (m + T + 2) of delay line N
(DL 8 if N = 0).
There are three points still to be considered:
(i) what happens when the wait number is greater
than the timing number;
(ii) the exact effect of the characteristic,
(iii) the effect of discriminations.
Wait number greater than timing number
Let us code the three instructions
430 21 - 13
43 28 - 25
45 13 - 21
leading to 57.
The instruction in 430 has wait number 1-30-2 = 1 (mod 32)
and timing number 3-30-2 = 3 (mod 32). Its detailed form is
4, 2-13, 0, 1, 3. (This shows a property of instructions in m.c.30 -
the wait number is just the first minor cycle of transfer and the
timing number is just the minor cycle of the next instruction. This
does not hold for instructions stored in any other minor cycle.)
The instruction in 43 can be obeyed at any time: it is usual to
obey it as soon as possible, in m.c. 5 (m.c. 4 is the set-up minor
cycle). The wait number is 5-3-2 = 0. The timing number is the same
because the next instruction is in m.c. 5, so the detailed form of the
instruction is 4, 28-25, 0, 0, 0. In minor cycle 5 the machine is
- 28 -
simultaneously obeying 28 - 25 and picking up the next instruction; it is
quite capable of doing this.
The instruction in 45 has wait number 1-5-2 = 26 (mod 32) and timing
number 7-5-2 = 0 (mod 32), so its detailed form is 5,13-2,0,26,0. This time the
next instruction becomes available (in m.c. 7) before the present one is
available in m.c. 1; the fact that the wait number is greater than the
timing number is symptomatic of this. If the next instruction went into
TS Count in m.c. 7 it would cancel the setting-up of the instruction which
is still waiting to be obeyed. To prevent this, circuits in the control of
DEUCE prevent a new instruction from going into TS Count until the previous
one has started to be obeyed. In the present case the order of the opera-
tions will be:
m.c. 5 Instruction enters TS Count
m.c. 6 Set-up minor cycle
m.c. 7 Next instruction available, not allowed into TS Count
m.c. 8 \
. |
. |
. > Waiting before obeying instruction
. |
. |
m.c. 0 /
m.c. 1 Transfer 13 - 2 occurs
m.c. 2 \
. |
. |
. > Waiting before next instruction
. |
. |
m.c. 6 /
m.c. 7 Next instruction enters. TS Count.
If the programmer applies the rule-of-thumb T = t - m - 2 (mod 32),
and thinks of the machine (not himself) as adding 32 to the timing number
when this is necessary to make it larger than the wait number, he will get
the right results.
Effect of the Characteristic
The example given above used only single transfers, i.e. transfers for
one minor cycle, so each instruction had characteristic 0. The operation of
the characteristic must now be explained.
Characteristic 0, Single Transfer
The transfer takes place for the one minor cycle, m.c. (m + W + 2);
the next instruction is picked up in m.c. (m + T + 2). If W > T the machine
waits for one major cycle before picking up the next instruction.
Characteristic 2, Double Transfer
The transfer takes place for two minor cycles, m.c. (m + W + 2) and
(m + W + 3); the next instruction is picked up in m.c. (m + T + 2). If
W > T the machine waits for one major cycle before picking up the next
instruction; notice that W = T is included in this case.
- 29 -
Characteristic 1, Long Transfer
The transfer starts in m.c. (m + W + 2) and ends in m.c. (m + T + 2)
the minor cycle when the next instruction is picked up. If L is the length
of transfer
L = (m + T + 2) - (m + W + 2) + 1 = T - W + 1 (mod 32)
Conversely W = T - L + I (mod 32)
As with characteristic 0, W > T causes the machine to wait for one major
cycle before picking up the next instruction.
Characteristic 3
The present effect of characteristic 3 is that of characteristic 1,
with the single exception that, when W = T, characteristic 3 causes a
transfer for 33 minor cycles and characteristic 1 causes a transfer for only
1 minor cycle.
A proposed modification of DEUCE would make characteristic 3 a
quadruple transfer rather like double transfer; transfer would take place
in minor cycles (m + W + 2) to (m + W + 5) inclusive. As the present effect
of characteristic 3 is of no special value it should never be used.
Discrimination instructions
When the "off" side of a discrimination is taken (positive for D 27,
zero for D 28, absence of TIL for 2 - 24) the next instruction is taken
from minor cycle (m + T + 2) of delay line N; so, when a discrimination
instruction is coded, the next instruction is always taken as the one on
the "off" side. If the "on" side is taken, however, the next instruction
is taken from minor cycle (m + T + 3) of delay line N. This is the reason
for saying that the instructions on each side following a discrimination
have to be stored in successive minor cycles of the same delay line.
/Example
- 30 -
Example
Code the following program:
(1) |--> 58 212 - 14
|
(2) | 617 193 - 725
|
(3) | 529 180 - 1212
|
(4) | 412 13 - 15
|
(5) | 114 203 - 26
|
(6) | 817 0 - 171 X
|
(7) | 722 180 - 192
|
(8) | 329 183 - 27
|<--------------------|
+ | -
(9) 59 96,7 - 212,3 (2 m.c.)
(10) 11 67-9 - 173,0,1(3 m.c.)
(11) 89 19 - 25 (2 m.c.)
(12) 616 212,3- 170,1 (2 m.c.)
(13) 624 17 - 18 (4 m.c.)
(14) 23 10 - 25 (32 m.c.)
(15) 37 24 - 14 (5 m.c.)
(16) 511 21 - 22 (4 m.c. e.o.)
(17) 831 11 - 8 (32 m.c.)
80
As a program for DEUCE this example is useless: its only object is to
demonstrate certain points in coding. The instructions have been numbered
for reference in the section of comments which follows the results.
- 31 -
N, S - D, Ch, W, T
(1) 58 contains 6, 2 - 14, 0, 2, 7
(2) 617 " 5, 19 - 7, 0, 6, 10
(3) 529 " 4, 18 - 12, 0, 13, 13
(4) 412 " 1, 13 - 15, 0, 0, 0
(5) 114 " 0, 20 - 26, 0, 1, 1
(6) 817 " 7, 0 - 17, 0, 2, 3 X
(7) 722 " 3, 18 - 19, 0, 0, 5
(8) 329 " 5, 18 - 27, 0, 0, 9
(9) 59 " 1, 9 - 21, 2, 27, 22
(10) 11 " 0, 6 - 17, 1, 4, 6
(11) 89 " 6, 19 - 25, 2, 0, 5
(12) 616 " 6, 21 - 17, 2, 2, 6
(13) 624 " 2, 17 - 18, 1, 6, 9
(14) 23 " 3, 10 - 25, 1, 3, 2
(15) 37 " 5, 24 - 1, 1, 30, 2
(16) 511 " 0, 21 - 22, 1, 15, 18
(17) 831 " 0, 11 - 8, 1, 0, 31
In the comments which follow, the sequence in which the detailed
coding is worked out will always be the same:
S, D, Ch, N, T, W.
When the wait number has to be evaluated there are two possibilities;
(i) if characteristic = 1 use W = T-L+1 (mod. 32)
(ii) otherwise, determine first minor cycle of transfer and
use W = F-m-2 (mod 32).
(1) Source 2, Destination 14, Characteristic 0, NIS.6 (this is the delay
line of the next instruction). Timing number 17-8-2 = 7. As 2 is a
DL and 14. only a TS, the first minor cycle of transfer is 12, and the wait
number 12-8-2 = 2.
(2) Source 19, Destination 7, Characteristic 0, NIS.5. (Hereafter it
will usually be assumed that these are easy.) Timing number 29-17-2 = 10.
As 19 is a DS and 7 a DL, it is the suffix 25 to the DL which gives F; so
W = 25-17-2 = 6.
(3) T = 12-29-2 = -19+32 = 13 (mod 32). 18 is a QS, 12 is a DL so
F = 12 and W = 12-29-2 = -19+32 = 13 (mod 32). (The phrase (mod 32) will
be omitted in future.)
- 32 -
(4) T = 14-12-2 = 0. As both 13 and 15 are TS's this can be obeyed in
any minor cycle; conventionally we use the first possible minor cycle and
put W = 0.
(5) N = 0 as the next instruction is in DL 8, T = 17-14-2-1. 20 is a
DS; D 26 behaves like a TS (see Appendix 1); so we use the suffix 3,
meaning "any odd minor cycle". Conventionally we use the first available
odd minor cycle so F = 17, W = 17-14-2 = 1.
(6) T = 22-17-2 = 3. S.0 behaves like a TS (see Appendix 1); 17 is a
QS; so, using Appendix 1, F = 21 and W = 21-17-2 = 2. As the instruction
is a stopper, X is written after the timing number in the detailed coding.
When the instruction is being punched this indicates that the most signifi-
cant digit is not punched.
(7) T = 29-22-2 =5. F= 24, so W = 21-22-2 = 0.
(8) T = 8-29-2 = -23+32 = 9, because the next instruction is taken as 58,
the one on the off side of the discrimination. F = 31, so W = 31-29-2 =0.
(9) Ch = 2. T = 1-9-2 = -10+32 = 22. W =-6-9-2 = -5+32 = 27. This
happens to have W > T. In no way does this affect the coding; all that
occurs is that the machine waits of its own accord for an extra major cycle
before picking up the next instruction.
(10) Ch = 1. T = 9-1-2 = 6. F = 7, so W = 7-1-2 = 4. We can check that
the length of transfer L = 6-4+1 = 3. Notice that the instruction 67-9 - 173,0,1
(3 m.c.) can be coded only when the next instruction is also in minor cycle
9.
(11) Ch = 2. T 16-9-2 = 5. Since this instruction can be obeyed in any
pair of successive minor cycles we conventionally put W = 0.
(12) Ch = 2. T = 24-16-2 = 6. 21 is a DS, 17 is a QS, so using Appendix 1
F = 20 and W = 20-16-2 = 2.
(13) Ch = 1. T = 3-24-2 = -23+32 = 9. The instruction 17 - 18 (4 m.c.)
could be obeyed in any four successive minor cycles, but because Ch = 1,
the last minor cycle of transfer must be the minor cycle of the next instruc-
ion. (If the effect of characteristic 3 is changed this will no longer be
necessary.) We could count backwards from m.c.3 and so find, F = 0, but a
better method is to use W = T-L+1 = 9-4+1 =6.
(14) Ch = 1. T = 7-3-2 = 2. W = 2-32 + 1 = -29+32 = 3. Transfers for
32 minor cycles are among the commonest long transfers; it is easy to see
that W = T+1 in such cases.
(15) Ch = 1. T =11-7-2 = 2. W = 2-5+1 = -2+32 = 30. This is an
example of bad allocation of storage; if the next instruction were in
minor cycle 13 or a little later we should have W < T and a major cycle
would not be wasted.
(16) Ch = 1. T = 31-11-2 = 18. The meaning of this instruction is
explained fully in I.10. What needs to be said here is that D 22 behaves
like a DS; the letters "e.o." indicate that the instruction must start to
be obeyed in an even minor cycle and must end in an odd one. Of course,
because Ch = 1 the next instruction must be in an odd minor cycle.
W = 18-4+1 = 15.
(17) Ch = 1. T = 0-31-2 = -33+2.32 = 31. W = 31-32+1 = 0. This is the
most economical way of arranging a transfer for 32 minor cycles.
- 33 -
This instruction starts being obeyed in m.c.1; in the following minor
cycle 0 the last word is transferred from DL 11 to DL 8, and, simultaneously
the next instruction is taken from DL 8. This next instruction will be the
one just going into 80, not the one which is just about to be wiped out.
Checking
The reader who has worked through the above example is likely to have
concluded that detailed coding is a mechanical process fraught with error.
He should then have concluded that the process must be checked, or better
still, avoided altogether.
In II.3 there is a description of a DEUCE program which is used to
check detailed coding done by hand; if this program is not used, the length
of time spent removing all the errors in one's program is usually at least
doubled.
However, the "Detailed Coding Program", described in IV.1, is the
best solution to this problem. For this the instructions are punched in
decimal (not binary) in the order in which they occur in the flow diagram;
and only what is written on the flow diagram is punched - the user has to
do no arithmetic. The detailed coding program does all the arithmetic,
including all the conversion from decimal to binary, and punches out the
complete program in binary in the form in which the user would have to punch
his detailed coding.
The reasons why the use of this program is recommended in general,
but not to beginners, are two: the beginner must know the form of the
instruction inside the machine instinctively if he is ever to test a program,
and also if he is going to make up a program in which instructions are
modified.
I.7 Subroutines
Much time and effort is wasted if the programmer has to start every
programming job from scratch. It is obviously desirable to be able to draw
on the results of the experience of others. In the first place, if we can
incorporate a tested program in our own there is less chance of error.
Secondly, the complete program can be written more quickly.
These ideas lead to the concept of a 'subroutine'. This is a small
program to do a specific job, such as evaluating sin x, find a square root,
read or punch a decimal number. A fairly large library of subroutines; with
full instructions for their use, is available, for DEUCE. A selection of
recommended subroutines is given in III.3.
To use a subroutine in a program of our own we must know where the
routine expects to find its data, which stores it uses as working space,
how much space it occupies in the high speed store, where its first instruc-
tion is and where we wish to re-enter our own program.
The last of these requirements is the only one that presents any
difficulty. One possible way is to leave the NIS. and timing number blank
on the last instruction of the library copy of the subroutine. In con-
structing the program we should have to fill in these blanks to lead to the
rest of the program. The trouble with this method is that we need several
copies of the subroutine if we wish to perform the same operation several
times at different stages in the program. A very simple and elegant method
is to plant an instruction at the end of the subroutine every time we use it
This means that we need only one copy of the subroutine and one extra
instruction for every entry to the subroutine. Such an instruction is
- 34 -
called a 'link'. In practice, we arrange to place the link in a specified
store, usually a TS, and the subroutine itself plants the link as its last
instruction
As we can do only one thing at a time, we can effect a further economy
of space by making every subroutine plant its link in the sane place. The
fact that it is overwritten as soon as we enter another subroutine does not
matter, as it has already served its purpose. The standard minor cycle that
we use is 130. This has the advantage that wait and timing numbers are now
the numbers of the minor cycles referred to.
Example
Read a positive number K from a card. Then read a succession of
numbers ai and find the least n such that
n
---\
\
> |ai|½ > K
/
---/
1
Punch out this n and also the sum.
The steps would be as follows:
(1) Read K
(2) Read ai
(3) Find |ai|
(4) Find |ai|½
(5) Add |ai|½ to previous sum, i.e. S1 = |ai|½ + S
(6) Is S1 > K? If no, increase i and go to 2, otherwise go on
(7) Punch out S
(8) Punch out n
(9) Stop the machine. (Or better: return to 1, for a fresh K.)
In the list of recommended subroutines we find R01/3 (No.28) which reads one
decimal number, P01 (No.12) which punches one number in decimal and FO4/1
(No.136) which will find a square root. We shall use R01/3 in DL 2, P01 in
DL 3, F04/1 in DL4. Our complete program would be as given below, page 36.
We use 192 for storing E|ai|½, 193 for counting the number of terms,
202 for storing +K. We shall put -K into 192 at the beginning and add
successive values of |ai|½ to this. When a change of sign occurs we have
read enough terms. As the punch routine will deal only with fractions, we
calculate n.10-9, i.e. instead of adding P1's we store the number 10-9 to
30 b.p. and add this.
- 35 -
30 - 19 (2 m.c.) Clear 192, 193
|---> (1) - 13 Link to 13
| ______
| 228 |R 01/3| Reak K,
|
| 130 30 - 13
|
| 212 - 26 +K to 202; -K to 192
|
| 212 - 202
|
| 13 - 19 <--------------|
| |
| (2) - 13 | Link to 13
| ______ |
| 228 |R 01/3| | Read ai
| |
| 130 30 - 13 |
| |
| 212 - 27 |
| / \ |
| +/ \- |
| 212 - 13 212 - 26 | |a1| to TS13
| \ / |
| \ / |
| (3) - 14 | Link to TS 14
| |
| ______ |
| 428 |F 04/1| | |a1| already in TS 13 as required
| |
| 130 193 - 13 | Increase count.
| |
| (a) - 25 | (a)=10-9
| |
| 13 - 193 |
| |
| 14 - 13 | |a|½ to TS 13
| |
| 192 - 25 | Add previous sum
| |
| 13 - 27 | Is S - K > If no, store S -K in
| | \ | 192 and read next card
| +| \- |
| | \------->-------|
| 202 - 25 If yes, add K, to give S.
|
| 13 - 14 S to TS 14
|
| (4) - 13 Link to TS13
| ______
| 328 | P 01 | Punch S
|
| 130 193 - 14 Count to TS 14
|
| (5) - 13 Link to TS 13
| ______
| 328 | P 01 | Punch count
|
| 130 30 - 19 (2 m.c.) Clear DC 19 and return to beginning.
| |
|<------------|
- 36 -
The complete program, the 'master routine', that we have had to
write takes 25 instructions and can be placed in DL 1.
This program requires 5 links, which have been denoted by (1)....(5)
and the number 10-9, which has been denoted by (a). The links themselves
would be the instructions.
(1): 1, 30 - 13
(2): 1, 30 - 13
(3): 1, 193 - 13
(4): 1, 193 - 14
(5): 1, 30 - 19 (2 m.c.),
with appropriate wait and timing numbers in each case. In the actual
program, of course, (1), ..., (5) would be replaced by their correct
addresses, so that the program starts
30 - 19 (2 m.c.)
1 - 13
______
228 |R 01/3|
130: 30 - 13
...
It is usual practice to write the entry point to the subroutine on
the left and to write the address of the link in brackets by the actual
instruction. The above might therefore be written
30 - 19 (2 m.c.)
17 - 13
______
228 |R 01/3|
130: (17)30 - 13
...
if the link is stored in 17. It is obeyed as if it is stored in minor cycle
30 and the wait and timing numbers computed accordingly. One of the first
instructions of the read subroutine is
13 - 130,
which plants the link in 130. The TS where it was previously kept is now
available for other purposes. In general the link is no longer in this TS
at the end of the subroutine.
- 37 -
0ccasions arise when one subroutine requires the use of another
inside it Such a subroutine is called a 'second order subroutine'. It
cannot place its link in 130 because this would be overwritten by the link
of the inner subroutine (which can be used elsewhere in its own right).
We therefore plant the link in the next available place, in 131 This idea
can naturally be extended to higher order subroutines. Generally, an mth
order subroutine, uses at least one (m-1) order subroutine in it and plants
its own link in 129+m
Although DEUCE has a multiplier and divider we often use subroutines
to perform these operations. A very useful one is A 12/1 (subroutine
No.222), which has three entry points, for multiplication, division and
summation of series respectively. In all cases it is first order.
I.8 Modification of instructions and counting
The situation often arises that the same arithmetical operations are
to be performed on a sequence of numbers. Examples are the summation of
series and matrix multiplication. There are now two important requirements,
to select the numbers in turn and to count whether the operation has been
done the desired number of times. Selection of numbers can be done in two
ways - either there is a separate selection instruction for each number of
the sequence or we add some constant to the address of a basic selection
instruction to make it refer to different numbers in turn. The latter
technique is preferable, in general, because it saves much space and is
very flexible. Note, however, that it may take longer than the other way.
The technique of instruction modification is very important and we
shall now examine it in some detail.
Suppose, for example, that we wish to evaluate the power series
S(x) = a0 + a1x + a2x2 + ... + anxn
where the coefficients are stored in DL A. For simplicity; let us assume
they are in m.c.'s 0, ..., n and that n < 32. A convenient economical
method (economical in the number of operations required) is that of nested
multiplication, i.e.
S(x) = ( ... ((anx + an-1)x + an-2)x + ... )x + a0,
and we use this. If we define
Sn = an and Sr-1 = Sr x + ar-1 for r = n, n-1, ..., 1,
it is evident that S(x) = So.
The block flow diagram of the summation would be
Set r = n
Set Sn = an ( = Sr initially)
|
| <-----------------|
Is r = 0? |
/ | |
/ | No |
/ | |
Yes Replace r by r-1 |
(Summation |
complete) Find r by r-1 |
|
Find Sr x |
|
Add ar-1 to produce Sr-1 |
|--------->----------|
- 38 -
Here we require the coefficients, ar, in turn. If we have the
instruction
Ao - 14, (which picks out a0)
the addition of r.P17 (i.e. r is the wait number) will change this to
Ar - 14 ,
tofetch ar.
This suggests that we can use r.P17 for two purposes: to modify a
selection instruction and to count the number of times we perform the
operation. In the above example we must leave the loop when r has become
zero, which occurs when we have added ao.There is also the implication
that it may be advisable to store the basic instruction and add the modifica-
tion, rather than storing the modified instruction. This is not entirely
borne out in practice, (especially on automatic modification - to be
described in I.9), as several later examples will show.
In the example, the modification would be done like this:
(I) - 13
(r) - 25
13 - Bm
Bm: Ar - 14
where (I) and (r) as sources are abbreviations for the addresses where I
and r are stored. This method needs a minor cycle of a next instruction
DL. to store the modified instruction. There is, however, a facility on
DEUCE for avoiding this - Destination 0. .
Destination 0 is TS Count, which has been mentioned earlier. What
is sent to TS Count is normally determined by the NIS. and timing number -
it is the place in the machine where an instruction is interpreted and
executed. By sending an instruction to D0 in the minor cycle when the next
instruction is selected we can override the natural NIS. and obey this
instruction instead. As an example, the above would become:
(I) - 13
(r) - 25
13 - Om
Qm [Ar - 14]
The Q stands for 'quasi' and we write this to show that the instruction is
obeyed as if it stood in minor cycle m. Frequently, as here, we write the
minor cycle number with the Destination 0 as well. As with links, it is
common practice to write
Qm [(Bs) : Ar - 14]
if the basic instruction is stored in Bs. Normally we write the instruction
with square brackets.
To use Destination 0 for modification it is essential that the
transfer is still going on in the selection minor cycle of the next
- 39 -
instruction. This is ensured by having W = T and Ch = 0, or by having
Ch = 1. Normally the NIS. is irrelevant in a transfer to D0 and we leave
it blank*.
Many programs use the instruction
0, 13 - 0, 0, 0, 0.
in 128, with the next instruction Q30. This is one of the most useful
places for a modified instruction, as W is then the actual minor cycle
number. The sequence
126 : 14 - 25
128 : 13 - 030
Q30 : [ ]
is very common. The modifying constant is placed in TS 14.
This method of modification has one grave disadvantage, in that one
of the few places in the DEUCE where addition is possible is required.
Sometimes this may not matter, on other occasions it necessitates many
'red tape' instructions to store the contents of TS 13 in a safe place. To
overcome this difficulty to a certain extent, the two quadruple stores,
QS 17 and QS 18, behave quite differently in instructions sending information
to D0. For example, the instruction
17 - 0
adds a particular constant (depending on the NIS.) to the instruction before
obeying it and stores the modified instruction. This method of automatic
instruction modification (abbreviated to A.I.M.) is described in I.9.
A feature of automatic computation is the loop of instructions,
repeated until some particular criterion is satisfied. Most of the programs
given as examples up to now have made use of this idea. It is obviously
important to traverse the loop the correct number of times, which leads to
the subject of counting.
Let it be said at once that this is where a large proportion of
mistakes arise. It is only too easy to go round a loop one time too many
or too few. It is generally best to count down. If the loop is to be done
n times, we start with n in some convenient store and reduce this by 1 every
time. When the count has reached zero the loop has been obeyed the correct
number of times and is left. Great care must be taken, though, to see that
the orders are executed as
Reduce Count
Test Count
not as
Test Count
Reduce Count.
(In the latter case the counting number must be (n-1) at the start.) When
tested the counting number in 'counting down' is always equal to the number
of times that the loop must still be done.
* But see I.9 for cases when the NIS. is important, in automatic modifica-
tion.
- 40 -
Counting can be done anywhere in the word. Convenient places are the
P1 and P17 position, because P1 and P17 are available as special sources.
For automatic counting (I.9) the P5, P10 and P18 positions may also be used.
Just where we count depends on the problem. In the example given previously
the count is x P17, because it can then be used for modifying an instruc-
tion. If, on the other hand, we are merely counting how many times something
has happened there is no reason for not using P1.
It is, of course, possible to count upwards from zero. If the loop
is to be done n times we increase the count, r, by one each time and test
either
r - n or n - r
In this case r is the number of times we have already been round the loop.
The comparison of n and r may be done simply by using the 'not equivalent'
relation, described in . An alternative method is to start with -n and
count upwards until a change of sign occurs.
In all these methods n is a parameter that varies from program to
program. Quite often, however, the case arises when a loop has always to be
done the same number of times. An example is the digit-by-digit method for
finding square roots. The loop is done the same number of times, irrespec-
tive of the size of the number involved. In such cases we can sometimes use
a slightly different technique. If the loop is to be done 32 times we can
use a marker digit (a 'strobe'), which starts at P1 and is shifted up by one
place every time. When the strobe disappears we have been round the loop
32 times. This method is used in an example it .
A very elegant method that has the advantage that no discrimination
is needed to escape from the loop is the 'spill-over'. This uses the
'Joe digits' (P22 - 25) in the instruction word. These digits are ineffec-
tive in an instruction. They can, however, be used to propagate a carry
from the wait number to the timing number, thereby changing the selection
minor cycle of the next instruction. The 'Joe digits' are normally written
in brackets between the wait and timing numbers.
The following is an example of the spill-aver technique. It comes
from an input program.
Example 1
123 : 125 - 13 C(125) = (1, 0 - 11, 0, 1,(15), 14, X)
|-> 127 : 13 - 029
|
| Q29 : [(125) : 0 - 11 X]
| |
| |---->---|Spill
| | |
| 113 : 28 - 25 |
| | |
|-------<----------| |
|
114 .... <----|
The effect is to obey the Q 29 instruction in such a way that we fill m.c.'s
0, 1, 2, ... in turn. When the instruction fills m.c. 30 it is
1, 0 - 11, 0, 31, (15), 14, X
- 41 -
which is then modified to
1, 0 - 11, 0, 0, (0), 15, X ;
this fills 1131 and takes its next instruction one m.c. later than before.
Note that the instruction is obeyed Q29. Escape from the loop occurs when
the wait number has become zero - if the last instruction is to refer to
m.c.31, with a wait number of 0, it must be in m.c.29.
It is often useful to have a constant like
P17 and P22
available as a modifier. In this way we can obtain a small count in the
Joe digits. This can also be done automatically, as described in I.9.
It is possible to use the spill over technique backwards, by sub-
tracting from the wait number. If the Joe digits are zero the timing
number is reduced by one when the wait number 'goes negative'. (In case
the timing number starts at zero it will be necessary to put a P31 into
the instruction, to avoid disturbing the go digit.) A further refinement
of this method is to add one to the wait number at the same time as
decreasing the Joe digits by one: this can be achieved by. subtracting 31.P17
from the instruction.
Example 2
217 : 221 - 13 221 = (3, 3 - 29, 0, 0, (10), 17 X)
....
128 : 13 - 030 <-------|
|
Q30[ 221 : 3 - 29 x] |
|-----------------| |
| 317 : 28 - 26 (31 m.c.) |
| |----------------|
|
|->316 : ...
This comes from a punch subroutine: the loop is executed twelve times.
A further useful technique of instruction modification occurs when
we have two instructions referring to the same minor cycle, one to fetch
and one to store.
Example 3
In the same punch subroutine the instruction
Q3o [3m - 15]
is followed shortly after by
Q30 [26 - 3m]
TS 13 is not disturbed between these instructions. Here we add a suitable
constant to
3 - 15
to produce
26 - 3
- 42 -
The actual instructions are:
128 : 13 - 030
Q30 [ 3m - 15 ]
212 ...
......
225 : 227 - 25
128 : 13 - 030
Q30 [26 - 3m]
312 : ...
227 is the 'pseudo-instruction'
1, 23 - 20, 3, 31, (15), 31,(1),
where the (1) represents the P31 digit.
In all the examples given the modified instruction has been obeyed
with a
13 - 0
instruction. This is not essential and many similar instructions occur,
such as
14 - 0,
21 - 0, etc.
Note that with 21 - 0 we must specify which minor cycle is sent to DO.
In the whole of this section the modification and counting has been
done by program. Originally, this was the only method available on DEUCE.
The next section describes certain alterations that were made, late in 1957,
to the instructions
17 - 0 and 18 - 0
to allow a certain amount of automatic modification and counting.
I.9 Automatic modification and counting
The technique of modification, described in the preceding section, is
probably the most important single advance in the recent history of computing
devices. It is from this that much of the power of the modern high speed
computer derives. When the Pilot ACE was first constructed no facilities
were included for the automatic modification of instructions and this course
was also followed by the English Electric Co. in the first models of the
DEUCE. After such machines had been in operation for several months it was
felt that modification was of such frequent occurrence and general use that
extra facilities would be helpful. These would result in a general speeding
up of programs because the (restricted) addition facilities in DEUCE would be
left free for arithmetic and would not be needed for modified instructions.
- 43 -
Few programs in the DEUCE library used the instructions 17 0 and 18 - 0*
and accordingly these instructions were chosen for engineering changes to
the computer, to give some of the more commonly required modification
effects. These alterations were made to the DEUCE late in 1957. The new
facility is called 'Automatic Instruction Modification', abbreviated to
A.I.M.
We have seen in I.8 that a frequent requirement in modification is
the addition of a P17. When numbers are to be used in pairs, e.g. in
double-length arithmetic (), addition of a P18 is needed. Other
constants that are often needed are
P 17 + P22 or P18 + P22,
to achieve a small count in the Joe digits. To enable the DL's to be used
as a continuously numbered store (Example 2 below) it is often desirable to
have P5 and P10 available for modification. In we shall find a use
for the combination P5 + P22, for transfers to and from successive tracks
on the drum. All of these constants are available with A.I.M.
Usually the NIS, digits are irrelevant in an instruction sent to DO
and for this reason they are available for use in a sense different from the
normal one. This is what has been done with A.I.M. Different combinations
of NIS. digits have the effect of adding different modifying constants.
The P1 digit, which is not used by other instructions, has also been passed
into service, as the auxiliary staticizer 'A', to widen the scope of A.I.M.
by giving a greater variety of additive constants. It is also possible to
subtract the modifiers instead of adding them.
One extra facility supplied by the A.I.M. alteration is automatic
counting. For this, all of the previous paraphernalia is used in conjunct-
tion with the characteristic. We know that it is only when a transfer to
DO happens in the m.c. when the next instruction is due to enter TS Count
that we override the normal selection of instructions. A.I.M. uses this by
adding a constant to QS17 or QS18 of the
17 - 0 or 18 - 0
instruction is for a single minor cycle which is not the selection m.c. of
the next instruction**.
Up to now nothing has been said to imply that QS17 and QS18 behave
differently with A.I.M. Actually they do, in that additions in QS17
become subtractions in QS18 and vice versa. This means that QS18 is
normally used for counting down, QS17 for counting up.
The table below gives the exact values of the modifying constants
that are used by A.I.M. under all possible combinations of controlling
digits. We use the symbol 'Y' for the four digits P1, P2, P3, P4.
* Programs of one of the authors' were exceptions!
** In normal circumstances such a transfer to DO does nothing.
- 44 -
|
Y
|
17 - 0, 0
|
17 - 0, 1
|
|
|
|
|
|
0
|
+ P5
|
+ P5
|
|
1
|
+ P10
|
+ P10
|
|
2
|
+ P17
|
+ P17
|
|
3
|
+ P18
|
+ P18
|
|
|
|
|
|
4
|
+ P5
|
+ P5 + P22
|
|
5
|
+ P10
|
+ P10 + P22
|
|
6
|
+ P17
|
+ P17 + P22
|
|
7
|
+ P18
|
+ P18 + P22
|
|
|
|
|
|
8
|
+ P5
|
- P5
|
|
9
|
+ P10
|
- P10
|
|
10
|
+ P17
|
- P17
|
|
11
|
+ P18
|
- P18
|
|
|
|
|
|
12
|
+ P5
|
- P5 - P22
|
|
13
|
+ P10
|
- P10 - P22
|
|
14
|
+ P17
|
- P17 - P22
|
|
15
|
+ P18
|
- P18 - P22
|
For QS18 all signs are reversed.
The lower of the digits to be added is determined solely by the
P1, P2 digits, as is obvious from the table. If Ch = 0, i.e. no P15, the
other digits of Y have no effect. On the other hand, if a P15 is present,
(Ch = 1), the presence of a P3 adds a P22 to the modifying constant and a
P4 reverses the effect of the modification.
The modifying constant is added only in the first minor cycle of the
transfer to DO. It is the modified i