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
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
(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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 -
Technical Note No. M.S.38
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 instruction that is obeyed and also
stored in the appropriate QS. When the modifier contains a P22 there is no
carry to this position from the lower order digits. Carry can occur between
successive minor cycles.
The case of Ch = 0 is used for automatic counting. Here the NIS. will
have its normal effect (because the transfer has ceased before the next
instruction is presented to TS Count) and so there is a restriction - either
we count in the place determined by the NIS. or, if we wish to count in a
particular digit position, the next instruction must be in a certain
position. Counts on P5 and P10 are possible only with an even numbered
NIS., while those on P17 and P18 require an odd numbered NIS.
The remainder of this section is composed of simple examples using
A.I.M.
It should be noticed that the A.I.M. facility is the only one in the
machine where the number in the source is altered on being sent to a
destination that is not related to it.
The first example of I.8 can be shortened as follows using A.I.M.
- 45 -
Technical Note No. M.S.38
Example 1
123 : 125 - 171 C(125) = (1,i 0 - 11, 0, 0, (15), 27 X)
|--> 126 : (2P1)171 - 029, 1 Adds P17
|
| Q29 : [(125):0 - 11 X]
|<----------------|
| Spill
127 : ....
The original wait number in the modified instruction is 0, because it will
become 1 before it is obeyed for the first time, thereby correctly filling
in turn 110, 11.1, ..., 1131 and leaving the loop on the last occasion.
The 17 - 0 instruction is in 126 so that 128 can still be used for a 13 - 0
instruction.
Example 2 Example 2 of I.8 can be similarly shortened.
217 : 221 - 171, C(221)= (3, 3 - 29, 0, 12, (4), 28, X)
|--> 315 : (6P1) 171 - 017, 1 Adds P17 + P22
|
| Q17.: [(221) : 3 - 29 X]
|<-------------------|
|
316 .....
The method has now actually changed from the example of I.8. Here the
count in the Joe digits is always increased, until there is a carry into
the timing number.
Example 3 n (≤32) numbers, xi, are given in A0, A1, ... . They are to
be replaced by f(xi).
Assuming f(x) is calculated by a first-order subroutine which has
the specification
TS 13 TS 16
At entry Link x
at exit f(x) -
Entered at 228 , does not disturb QS 18,
our program might be as below. n is in 183 at the start.
/Example
- 46 -
Technical Note No. M.S.38
319 : 321,22 - 181,2 (2 m.c.)
/
328 : (10 P1 ) 182 - 030,1 <-----| < Adds P17 to instruction
| \ before obeying it.
Q30 [(322) : Ar - 16] |
|
323 : 325 - 13 | Place link
______ |
228 : | f(x) | |
|
130 : (325) : 183 - 03,0 | Subtract P17 from counter
| /
326 : (10 P1) 181 - 029,1 | <Adds P17 to instruction
| \before obeying it
Q29 : [(321) : 13 - Ar] |
|
324 : 183 - 28 | Test counter
| \ |
| \ nz |
Zero | \---------->|
|
327 Exit
The contents of 321, 322 and 325 are
C(321) = (3, 13 - A, 0, 0, (0), 25) obeyed Q29
C(322) = (3, A - 16, 0, 31, (0), 23) obeyed Q30
C(325) = (3, 18 - 0, 0, 3, (0), 26) obeyed Q30, used as link.
There are some points to notice,
(i) The two instructions that perform modifications have Y = 10, to add
P17. (Y = 10, not 2, because the normal modification in QS 18 is subtracted.)
(ii) The fetch instruction, in 322, and the store instruction, in 321,
are coded to have a wait number 1 less than is required to pick out the
first number, because the first modification occurs before any numbers have
been used.
(iii) The link instruction does the counting. We are able to count X P17,
as the NIS. = 3. The P17 is subtracted in m.c.3.
(iv) The master routine has been coded to be placed at one end of DL 3, it
uses 319 and 321-28 only.
Example 4 The same as Example 3 without the restriction on n. A possible
program follows. Again, n is in 183 at the start.
/Example
- 47 -
Technical Note No. M.S.38
318 : 321,22 - 181,2 (2 m.c.)
328 : (10 P1) 182 - 030, 1 <----------|
|
Q30 [(322) : Ar - 16] |
|
320 : 323 - 13 |
|
______ |
228 : | f(x) | |
|
130 : (323) 183 - 0, 0 |
|
326 : (10 P1) 181 - 029, 1 |
|
Q29 :[(321) : 13 - Ar] |
| |
| Spill | Spill on replacing A31
|------------------>| |
|->315 : 183 - 28 | |
| z / \ nz | |
| 327 exit \--->-------|---|
| |
| 316 : 329,30-181,2(2 m.c.)<-|
|
| 30 : (8 P1) 182 - 02,1
| Adds P5 to instruction
| Q2 :[(330) (A + 1- 16]
|
| 324 16 - 13
| Adds P10 to instruction
| 331 : (9 P1) 181 - 01, 1
|
| Q1 :[(329) 13 - (A + 1)]
|
| 319 : 181,2 - 329,30( 2 m.c.)
|<----------------------------|
where C(321) = (3, 13 - A, 0, 0, (15), 16) .. obeyed Q29
C(322) = (3, A - 16, 0, 31, (0), 20) obeyed Q30
C(323) = (3, 18 - 0, 0, 3, (0), 26) Link; obeyed in 130
C(329) = (3, 13 - A, 0, 0, (15), 16) obeyed Q1
C(330) = (3, A - 16, 0, 31, (0), 20) obeyed Q2
Notes: (i) As far as the test instruction in 315, everything is as
in Example 3, (except for the placing of some instructions).
(ii) The store instruction, in 321, has 15 in the Joe digits,
to make use of spill-over after A31 has been replaced by f(x)
(iii) The instructions in 329,30 at start are the same as those
in 321,22. They will be changed to
13 - (A + 1) and (A + 1) - 16
respectively and then replaced in 329,30. In this way, if there are more
- 48 -
Technical Note No. M.S.38
than 64 numbers, the instructions will later become
13 - (A + 2) and (A + 2) - 16,
etc.
(iv) The instruction
16 - 13
in 324 is necessary because otherwise a wrong number will be placed in
A + 1. The purpose of the two modified instructions is to add P5 and P10 to
them respectively. The instruction in 324 avoids any harmful effects. If
the subroutine for f(x) required x in TS 13, instead of TS 16, this
instruction would not be necessary.
(v) The coding of the instructions following 316. It is
essential that the two 18 - 0 instructions are obeyed in consecutive minor
cycles, as here, since this is the way they are obeyed in the main loop.
If this is not done the number placed in DL (A + 1) by the second instruc-
tion does not go back where it came from. Just when the two instructions
are obeyed is fairly immaterial but they dictate the placing of the
instructions in 324 and 319 - these must follow from the modified
instructions with timing numbers 20 and 16 respectively.
To satisfy all these requirements can be something in the nature of
a jig-saw puzzle. As in Example 3 the instructions have been placed quite
compactly. Wherever possible the delay between instructions has been kept
small.
I.10 Optimum coding
The use of wait and timing numbers to control the actual execution
of an instruction and selection of its successor was explained in I.6
The wait number is often non-zero, because it is not always possible to
place the required numbers two minor cycles away from the instruction
calling for them. This means that the computer has to wait until the
minor cycles asked for are available. It is obvious that this wasted
waiting time would be reduced if data were so disposed in the high-speed
store that numbers became available with as small a delay as possible.
Naturally, this requires very careful planning.
Again, the time the computer waits between instructions depends on
their relative placing. Generally speaking, if the timing numbers are
small the wasted time is small. This implies that it is necessary to place
instructions in advantageous positions relative to each other if the full
speed of the computer is to be realised. In I.6 we saw the consequences
of having a timing number that was less than the wait number - the DEUCE
waits a whole major cycle before the next instruction can enter TS Count.
A loss of 1 millisecond may not seem vital, but if this is done with every
instruction the speed of the machine is reduced from a maximum of about
16,000 operations per second (when W = T = 0 in every instruction) to
about 500 operations per second (W = 31, T = 30 everywhere). This is, of
course, an extreme case but it does illustrate what could happen with
completely thoughtless coding of instructions.
It is therefore reasonable to lay down as a principle that wherever
possible instructions should be coded in such a way that the waiting time
until actual execution is small (i.e. W small) and that the next instruction
emerges from its DL as soon as possible after the end of the operation.
- 49 -
Technical Note No. M.S.38
This procedure is known as 'optimum coding'. In general, if it is
necessary to deal with large quantities of numbers it is not possible to
optimize both the instructions and the data without a completely
uneconomic amount of effort by the programmer.
Usually, the optimum coding is done only for instructions. Here,
also, the amount of time spent on the actual allocation of storage should
be commensurate with the expected use of the program. The places where
the technique pays the highest dividends. are loops that are repeated many
times. For example, suppose that at the first attempt at coding a loop it
is found that 3 major cycles are necessary but that the last instruction
has a high timing number, say T = 28. This means that 30 minor cycles are
wasted every time round the loop. By reallocation of the positions of some
instructions it may be possible to reduce the total time of the loop to 2
major cycles. If this loop is the innermost of a program this saving may be
quite significant. It is a matter of experience to recognise when such a
saving is possible. If the excess over a whole number of major cycles is
small, say 3 or 4 m.c.'s at most, it is almost always possible to save these
by recoding. It is certainly worth trying. On the other hand, this loss of
time may not matter, that even if the minor cycles could be saved there
would be no overall saving in time. As an example, the punch allows 116
major cycles of computing time between successive cards. If the necessary
calculation can be done in this time it may be possible to keep the punch
running continuously. Shortening the time of the calculation would be no
use, as the time saved would merely lengthen the time DEUCE waits for the
next card to reach the punching knives. If this hypothetical calculation
took just over the 116 major cycles allowed between cards, it would be
necessary to stop the punch between cards, thereby halving its speed. In
this instance some reprogramming might save considerable time.
When a program is being coded, the normal procedure is to tackle
first those sections that are obeyed most frequently. Any saving in
machine time that results from optimum programming here is most noticeable.
We then work outwards to the less frequent loops, until we reach the master
program, when there is generally little need for great rapidity. If it is
possible to optimize this as well as all other sections so much the better
but this is the least important part - as far as total machine time is
concerned. Subroutines are normally optimum coded, as these are frequently
used sections of programs.
Optimizing a subroutine may be quite a tricky operation, as there are
often conflicting requirements. The routine is to be fast, yet its
instructions should be packed into a limited number of DL's, not dotted all
over the store. It may even be necessary to pack the instructions compactly
into several consecutive m.c.'s of one DL, for example entirely within
m.c.'s 16 - 31, so that it may be used in the same DL as another subroutine
occupying the other minor cycles.
There are many operations on DEUCE that are autonomous, in the sense
that once started the machine is free to perform other duties. These are
multiplication and division, reading and punching cards, and transfers of
information to and from the magnetic drum. All of these operations are
comparatively lengthy. Optimum coding can save much time here. If at all
possible the instruction should be coded so that many succeeding instruc-
tions can be obeyed before the autonomous one is complete. For example,
it is common to anticipate a transfer from the drum to the high speed store,
so that the information is already available when required.
- 50 -
Technical Note No. M.S.38
The whole art of optimum coding, and the necessity for it, is often
held up as a drawback of the DEUCE*. Actually, it is not nearly as bad as
is suggested by those accustomed to other computers (see Ref.11). It is not
difficult to write programs that are 'nearly optimum' at the first attempt.
Like other things it is less fearsome when familiar and familiarity only
comes with practice in programming.
I.11 The double-length accumulator
Any digital computer, whether a desk machine working in decimal or a
large automatic machine working in binary which multiplies together two
numbers with n digits will need a register with 2n digits to take the
product; and this register will need facilities for addition so that the
multiplication can take place. This is the immediate reason why DEUCE has
an accumulator, DS 21, which holds 64 binary digits as well as the short
accumulator, TS 13; however DS 21 has facilities for subtraction and
shifting as well as for addition.
The use of TS 13 for addition and subtraction of numbers was
explained in I.3, In this section destinations 22 and 23 and source 22
will be used for addition, subtraction and shifting in DS 21. However the
double-length accumulator is not quite as simple to use as the short
accumulator, TS 13.
The result of any operation using S.22, D.22 or D.23 may depend on
the state of an electronic trigger called TCB: source 21 and destination
21, as already explained, act in the same way as the source and destination
of any other mercury store, and their behaviour is unaffected by the state
of TCB. TCB can be "off" or "on". Its usual state is off - in fact all
subroutines assume that TCB is off when they are entered and they should all
leave it off at exit.
TCB is put off by the instruction 4 - 24 and is put on by the
instruction 5 - 24, These come in the special class of instructions with
destination 24 known as "Destination Triggers", which are fully explained
in I.14. All that needs to be said now is that the source numbers 4 and
5 do not refer to the corresponding delay line when the destination is 24.
The machine realises this and switches TCB accordingly.
When TCB is off the number is treated as one long 64-bit number,
so the operations of addition, subtraction and shifting must cause a carry
from the less significant half of the number (in 212) into the more signifi-
cant half (in 213). When TCB is on the two halves of DS 21 they are
treated as separate 32-bit numbers and there can be no carry from one half
to the other. This means that there will be no carry from 213 into 212,
whatever the state of TCB, and there can only be carry from 212 into 213
when TCB is off.
Operations in 213
The state of TCB does not affect these operations.
Example 1 95 - 213 C'(213) = C(95), whether TCB is off or on.
Example 2 95 - 223 C'(213) = C(213) + C(95), whether TCB is off or on.
Example 3 95 - 233 C'(213) = C(213) - C(95) whether TCB is off or on.
* It is also used as a selling point in favour of the machine – 'Optimum
coding' has a fine verbal flourish about it.
- 51 -
Technical Note No. M.S.38
Example 4 223 - 213 C'(213) = ½C(213), whether TCB is off or on.
This is a shift down exactly like 23 - 14.
Example 5 223 - 95 C'(95) = ½C(213), whether TCB is off or on.
The numbers in 212 and 213 are unaffected.
Example 6 213 - 223 C'(213) = 2C(213), whether TCB is off or on.
Shifting up in 21 is done by addition, just like
13 - 25.
Not one of these operations affects the number in 212.
Double-length operations in 21
TCB is off in all the following examples because the numbers in 21
are all double-length.
Example 7 94,5 - 212,3 C'(21) = C'(94), C'(213) = C'(95).
(2 m.c.) Of course this result is also true if TCB is on.
Example 8 94,5 - 222,3 C'(21) = C(21) + C(94,5).
(2 m.c.) Double-length addition.
Example 9 94,5 - 232,3 C'(21) = C(21) -- C(94,5).
(2 m.c.) Double-length subtraction..
Example 10 222,3 - 94,5 C'(94,5) = ½C(21).
(2 m.c.) Double-length shift down. This is like S.23;
the shift is correctly signed and is truncated.
The number in 21 is unaffected.
Example 11 22 - 21 C'(21) = 2-n C(21 ).
(2n m.c, e.o.) The letters (e.o) mean "transfer starts in an
even minor cycle and ends in an odd one". Of
course, 2n < 32. This is just like 23 - 14
(n m.c.). Unless n = 1 characteristic 1 must be
used. The next instruction will then have to be
in an odd minor cycle.
Example 12 21 - 22 C' (21) = 2n C(21). Of course, 2n < 32. Shift-
(2n m.c. e.o.) ing up is done by addition just like 13:- 25
(n m.c.). Unless n = 1 characteristic 1 must be
used. The next instruction will then have to be
in an odd minor cycle
Example 13 20 - 22 C'(21) = C(21) + C(20). As in all of examples
(2 m.c., e.o.) 7-12 it is essential that transfer ends in an
odd minor cycle. The instruction
20 -22
(2 m.c., o.e.) may well give the wrong result. The reason is
explained in Example 26.
- 52 -
Technical Note No. M.S. 38
Operations in 212
Example 14 94 - 212 C'(212) = C(9 ), whether TCB is off or on.
Of course, C'(213) = 0(213).
Example 15 94 - 222 C'(212) = C(212) + C(94), whether TCE is off or on.
But C'(213) = C(213) if TCB is on,
only may be if TCB is off.
Example 16 94 - 232 C'(212) = C(212) - C(94), whether TCB is off or on.
But C'(213) = C(213) if TCB is on,
only may be if TCB is off.
Example 17 222 - 94 C'(94) = C(212) if TCB is on,
only may be if TCB is off.
The numbers in 212 and 213 are unaffected whatever
the state of TCB.
Example 18 212 - 222 C'(212) = 2C(212), whether TCB is off or on,
But C'(213) = C(213) if TCB is on,
only may be if TCB is off.
It will be seen that destinations 22 and 23 can always be used for
addition and subtraction in 212 with TCB on, and they can also be used with
TCB off if the programmer does not mind changing the content of 213.
Operations in 212 with TCB off must be explained further.
Example 19 4 - 24 TCB off
31 - 21 (2 m.c.) "Ones" in both halves of 21
27 - 222 Add P1 to 212.
TCB is off and the double-length integer -1 is placed in DS 21. The
integer 1 is added to the least significant half of 21, so the result ought
to be 0 in 212 and 213, This means that carry from 212 to 213 must be allowed.
Example 20 4 - 24 TCB off
27 - 212 P1 to 212
30 - 213 0 to 213
31 - 222 Add "ones" to 212.
TCB is off. This time we place the double-length integer 1 in 21
and add "ones" to 212. If we just allow carry from 212 to 213 the result
is a P1 in 213, i.e. 232, whereas we should like the result to be 0. The
addition has been 1 + (232 - 1) = 232
not 1 + (- 1) = 0.
- 53 -
Technical Note No. M.S. 38
DEUCE does get the result 0, but to do this it has to treat the
number added as -1, not as 232 -1. The method used when adding a number
into 212 with TCB off is to allow carry from 212 into 213 and to add a
number into 213 which is 32 copies of the sign digit of the number added -
all zeros or all ones.
Then a number is subtracted from 212 with TCB off carry is allowed
from 212 into 213 and a number is subtracted from 213 - this number is
again 32 copies of the sign digit of the number subtracted from 212.
What DEUCE does, in effect, is to extend the single-length number
being added or subtracted to double-length by copying the sign digit.
In example 19, 10.0...00 is extended by 00...00 so that it is the double
length number 1 which is being added; in example 20, 111....11 is extended
by 11...11 so that the double-length number -1 is added and the result is
0.
Example 21 4 - 24 TCB off
30 - 21 (2 m.c.) 0 in 212 and 213
27 - 232 Subtract P1 from 212.
100...00 is extended by 00...00 to became a double-length number and
subtracted from 0. The result is the double-length number 11...11, 11...11,
i.e. -1.
Example 22 4 - 24 TCB off
30 - 21 (2 m.c.) 0 in 212 and 213
31 - 232 Subtract "ones" from 212.
111...11 is extended by 11....11 and the resulting double-length
number is subtracted from 0, giving 100..00, 00..00, i.e. +1.
Example 23 4 - 24 TCB off
29 - 232.
00...001 is extended by 11.....11 and the double-length number is
subtracted from the number already in 21. This is equivalent to adding the
double-length number 00..001, 00...00. The instruction appears to subtract
a P32 from 212, but in fact it adds P32 to 212, so rounding off the double-
length number in 21 to single-length. This instruction is very common at
the end of multiplication subroutines.
Example 24 4 - 24. TCB off
29 - 222.
The converse effect to the previous example: P32 is subtracted from
212.
Example 25 4 - 24 TCB off
212 - 232
The second instruction subtracts C(212) from (212) and leaves in
212. Also, if the number in 212 had a P32, (-P1) is subtracted from 213;
- 54 -
Technical Note No. M.S.38
but if the number in 212 had no P32, 0 is subtracted from 213. The total
effect is to clear 212 and to round off the double-length number in 21 in a
single instruction.
Example 26
As already explained,
4 - 24
20 - 22 (2 m.c., o.e.)
is the correct method of adding C(20) to 21.
The instructions
4 - 24
20 - 22 (2 m.c., o.e.)
use destination 22 ending in an even minor cycle; so DEUCE goes through
the same procedure of extending the number added in the even minor cycle
to double-length. This gives an incorrect result.
The same is also true if destination 23 is used.
Example 27 5 - 24 TCB on
222 - 94
½C(212) is put into 94; neither half of 21 is affected. The shift
is a correctly signed arithmetical shift - the P31 digit of C'(94) is the
P32 digit of C(212) and the P32 digit of C'(94) is the same - and the P1
digit of C(212) is truncated.
Example 28 4 - 24 TCB off
222 - 94
The only difference from the previous example is in the P32, digit
of C'(94). It is now a copy of the P1 digit of C(213). It is difficult to
see any application c this.
Example 29 4 - 24 TCB off
22 - 21
(2n m.c., e.o.) C'(21) = 2-n C(21). n < 16 )
is the correct method of shifting down n places;
4 - 24
22 - 21 (2n m.c., o.e.)
is correct
- 55 -
Technical Note No. M.S.38
For instance, if n = 1 and the digits in 21 are numbered 1, 2, ... 31,32;
33, 34,...63, 64,
4 - 24
22 - 21 (2 m.c., e.o.)
gives the correct result 2, 3,...32, 33; 34, 35,...64, 64; whereas
4 - 24
22 - 21 (2 m.c., o.e.)
gives the result 2, 3,...32, 34; 34, 35,....64, 64.
Example 30
The instruction
223 - 213
gives a truncated shift of one place, whatever the state of TCB. To get
a rounded shift, call the number in 213 the integer a + 2b, where a is the
least significant digit; a = 0 or 1. A rounded shift should give a + b;
the truncated shift gives b from source 223. The instruction
223 - 233
gives (a + b) in 213 as required (whatever the state of TCB).
Similarly
22 - 23 (2 m.c., e.o.) with TCB off
gives a rounded shift of the double-length number in 21; and
222 - 232 with TCB on
gives a rounded shift of the number in 212.
Example 31 C(15) = r P17 where r < 32.
|-> 13 16,7 - 212,3 (2 m.c.) [1, 9-16, 0,0,27 and 1, 16-9,0,0,(15)4]
|
| 18 15 - 22 (2 m. c.)
|
| 128 212 - 030
|
| Q30 [16, 9r - 16]
|
| 127 213 - 029
|
| Q29[17, 16 - 9r-1]
| |
|<---------------| Spill over, r=32
14
In this example it does not matter whether TCB is off or on, and it
does even not matter whether the second instruction is obeyed (e. o.) or
- 56 -
Technical Note No. M.S.38
(o.e.) - because the number in 15 is positive. (The fact that the numbers
in both halves of 21 are negative does not affect the position.)
I.12 The multiplier and divider
DEUCE is probably the only machine with an automatic multiplier and
divider (electronically they are parts of, the same unit) in which sub-
routines are regularly used for both these operations. Multiplication, in
particular, is such a common operation that other machines make the multi
plication instruction one which is easy to use, but DEUCE's multiplier
operates on positive integers (integers in which the presence of the P32
digit means that the number is greater than 231) although signed fractions
are the form numbers usually taken. To maim things more illogical, DEUCE's
divider does work with signed fractions.
Because subroutines are regularly used fro multiplication and
division there is no necessity for the beginner to read this section before
he can program any useful arithmetic - in fact a multiplication subroutine
was first used in I.4. This section is addressed to the programmer who
wishes to have a complete knowledge of DEUCE.
The multiplier and divider are started by the instructions 0 - 24
and 1 - 24 respectively. These are two more instructions with destination
24: again it must be emphasised that the machine does not use the nominal
sauces 0 and 1 (I.D. and D.L.1) when it encounters these instructions.
The multiplier
The one time the programmer may want to use the multiplier without
recourse to a subroutine is when the product of two positive integers is
required.
The two positive integers are placed in 16 and 213, and 212 must be
cleared*. Then the multiplier is started by the instruction 0 - 24, obeyed
in an odd minor cycle. After 65 minor cycles the product, a double-length
number, is in 21: the number which was placed in 213 has been lost but the
number in 16 is still available for use. The result would not be affected
if the 0 - 24 had characteristic 1 or 2, nor if another 0 - 24 instruction
were obeyed while the multiplication started by the previous one is still
running. TCB is put off as the multiplication starts.
If the program is
21 31 - 16
23 31 - 213
25 30 - 212
28 0 - 24 (in m.c. 11)
the multiplier takes the product of 11....11 and 11....11. These are both
the positive integer 232 -1, so the product obtained is (232 -1)2, i.e.
100...00,011....11.
* If 212 contains a reasonably small positive number when multiplication
starts this number will be added to the more significant half of the
product. If the number in 212 is negative, however, the number in 16 is
multiplied by a number which is not the content of 213.
- 57 -
Technical Note No. M.S.38
If these numbers represent signed integers we should be squaring -1,
and the result should be 1, i.e. 100...00,00...00.
If the numbers represent signed fractions with 30 binary places
(i.e. with that number of binary digits below the binary point) we should
be squaring -2-30 and the result should be +2-60, i.e. 00100...00,00...00.00.
The rest of this section on the multiplier is concerned with the
corrections necessary to get these results. It is also concerned with the
question of timing.
In the above example the multiplier was started in m.c.11 (not
m.c.10 because this is an even minor cycle). The 65 minor cycles during
which the multiplier works run from the beginning of this minor cycle to the
end of m.c.11 in the next major cycle but one. The earliest the result can
be taken from 21 is therefore m.c.12 and 13 of this major cycle,
While the multiplier is working destinations 16, 21, 22 and 23 must
not be used or an incorrect product will be given. Source 21 will give the
partly-formed product during this period and so will source 22: using them
will not affect the result of the multiplication, but it is difficult to see
any application except the one given below. Source 16 can be used freely
during the multiplication process. The second reason for using a subroutine
for multiplication is to waste sufficient time for the multiplication to
have ended before the master routine can affect the result.
Multiplication of signed integers
a and b are signed integers, say in 14 and 16. The subroutine to
multiply them will start
30 - 212
14 - 213
0 - 24 in an odd m.c.
If both a and b are positive this gets the correct answer ab.
If a is negative the multiplier treats it as (232 + a) because it
takes the presence of the P32 digit in a to mean that a > 231, not that a
is negative. So if a is negative and b is positive the multiplier
produces (232 + a)b, and the subroutine must subtract 232b from the result.
Conversely, if a is positive and b negative, the multiplier produces
a(232 + b) and the subroutine must subtract 232a from the result.
If both a and b are negative the multiplier produces (232 + a)(232+ b)=
264 + 232 (a + b) + ab, so the subroutine must subtract 232(a + b) from the
result given by the multiplier. This appears to give 264 + ab, not the
required result, but as DS 21 only holds 64 binary digits the 264 is a single
digit beyond the more significant end of the result.
The method used to subtract 232c from the double-length number in
21 is simply to subtract c from 213.
The rule for sign-correction is:
If either of a or b is negative, subtract the other from 213.
- 58 -
Technical Note No. M.S.38
The complete subroutine for multiplying signed integers is
220 30 - 212
223 14 - 213 a to 213 (b is already in 16)
225 0 - 24 MULT starts in m.c.27
228 13 - 130 Plant link
230 14- 27 Test sign of a
/ \
+/ \-
226 30 - 13 227 16 - 13 C!(13) = 0 or b as a is +ve, -ve
\ /
\ /
229 16 - 27 Test sign of b
/ \
+/ \-
221 30 - 25 222 14 - 25 Add 0 or a as b is +ve, -ve Subtract sign
\ /
\ / Subtract sign correction
\ /
224 13 - 233 in m.c.29 after MULT has ended.
130 Link
As much of the work as possible has been done while the multiplier
is working so that the subroutine is as fast as possible. It fills m.c.20 to
30 of DL 2. The reason for the apparently haphazard locations for the
instructions after the one in 230 is time wasting. The time between start-
ing the multiplier and reaching the instruction in 229 is 34 minor cycles.
Another 32 minor cycles pass before a number is sent to DS 21 so that 66
minor cycles elapse between the starting of the multiplier and the next use
of DS 21.
There is an alternative method of evaluating the sign-correction
which uses the first partial product. If the multiplier is started in m.c.
25 with a in 213 and b in 16, it looks at the sign of a in m.c.25 and adds
b to 21 in m.c.26 only if a is negative. This is exactly what is done by
the three instructions in 230, 226 and 227 in the above example. So source
21 in m.c.28 will give 0 or b according as a is positive or negative. The
subroutine then becomes
218 30 - 212
221 14 - 213
223 0 - 24 in m.c.25
226 212 - 15 in m.c.28
222 13 - 130 Plant link
220 16 - 27
/ \
+/ \- (Correction for sign of b)
224 30 - 233 225 14 - 233 in m.c.27
\ /
\ /
227 15 - 233 (Correction for sign of a)
130 Link
- 59 -