UNCLASSIFIED U.D.C. No. 518.5 : 531.791 Technical Note No. M.S.38 April, 1959R 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. __________________SUMMARYThe technique of programming the digital computer DEUCE is described. _____________ UNCLASSIFIED## Technical Note No. M.S.38

LIST OF CONTENTSPage1 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)PageAPPENDICES 1-4 188-198 ILLUSTRATIONS - Figs. 1-8 - DETACHABLE ABSTRACT CARD -LIST OF APPENDICESAppendix1 - Function code of DEUCE 188 2 - Binary Arithmetic 191 3 - Useful constants 195 4 - Hollerith timings 197LIST OF ILLUSTRATIONSFig.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

1INTRODUCTIONThis 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 ITHE ESSENTIALS OF PROGRAMMINGI.1Description of a computing machineThe 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.2Description of DEUCEDEUCE (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.3DEUCE instruction codeIn 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 A_{m}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 17_{0}, 17_{1}, 17_{2}, 17_{3}and 18_{0}, 18_{1}, 18_{2}, 18_{3}; 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 19_{2}, 19_{3}, etc. (not19_{0}, 19_{1}). 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 9_{3}- 13 , which copies the content of 9_{3}into TS 13. In general, no confusion arises if we drop the letters DL, TS, QS, DS. If necessary, the contents of A_{m}are denoted by C(A_{m}), Thus, C(9_{3}) 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 theonlycases in which the use of Sources 23 and 24 can affect the content of TS 14.Sources 27, 28, 29, 30, 31all 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 14Destinations 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 28are 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 leavesDestination 29This 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) = 2^{3}C(14). (4) 11 - 25 (32 m.c.) which gives C'(13) = C(13) + C(11_{0}) + C(11_{1}) + ... + C(11_{31}), 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.4Some simple programsThere 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(19_{2}), y = C(20_{3}). Put (2x + y) in 14 20_{3}- 13 C'(13) = y 19_{2}- 25 C'(13) = x + y 19_{2}- 25 C'(13) = 2x + y 13 - 14 C'(14) = 2x + y The program 20_{2}- 13 19_{2}- 25 (2 m.c.) 13 - 14 is meaningless. If z is the number in 19_{3}, 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(19_{2}), y = (19_{3}). Put the greater into 21_{2}19_{2}- 13 C'(13)= x 19_{3}- 26 C'(13)= x - y 13 - 27 Test sign of x - y. / \ +/ \- 19_{2}- 21_{2}19_{3}- 13 13 - 21_{2}It is impossible to write the one instruction 19_{3}- 21_{2}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 21_{3}. The numbers in 14 and 16 are undisturbed, but the numbers in 13, 15, 21_{2}and 21_{3}are lost. (11) x = C(17_{0}), y = C(17_{1}). Put xy in 17_{2}. 17_{0}- 14 C'(14) = x . 17_{1}- 16 C'(16) = y. MULT C'(21_{3}) = xy. 21_{3}- 13 C'(13) = xy. 13 - 17_{2}C'(17_{2}) = xy. (12) x = C(14). Calculate x^{13}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'(21_{3}) = x^{2}21_{3}- 16 C'(16) = x^{2}, C'(14) = x MULT C'(21_{3}) = x^{3}21_{3}- 14 C'(14) = x^{3}, C'(16) = x^{2}MULT C'(21_{3}) = x^{5}21_{3}- 16 C'(16) = x^{5}, C'(14) = x^{3}MULT C'(21_{3}) = x^{8}21_{3}- 14 C'(14) = x^{8}, C'(16) = x^{5}MULT C'(21_{3}) = x^{13}21_{3}- 13 C'(13) = x^{13}. (13) r is an integer. Given r = C(15), r^{2}= 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}= r^{2}+ 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) = r^{2}15 - 25 (2 m.c.) C'(13) = r^{2}+ 2r 27 - 25 C'(13) = r^{2}+ 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.5Loops and countingOne 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 1Punch the squares of the numbers 1, 2, ... 10 in binary. Example 13 of I.4 gives a method by which, if r^{2}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 1_{15}. - 16 -## Technical Note No. M.S.38

Add the instructions 1_{15}- 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. 10^{2}has just been punched. If the 16 - 13 instruction is preceded by 30 - 16 30 - 15 we have arranged that r^{2}= 0 and r = 0 initially. Therefore 1^{2}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 | 1_{15}- 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 1000^{2}were wanted, the only modification necessary would be to change the constant 10 in 1_{15}to 1000.Example 2x = C(14). Calculate x^{13}in as few instructions as possible and place it in 13. - 17 -## Technical Note No. M.S.38

Suppose at some stage x^{r}is in 16 and that x is never disturbed from 14. Then the instructions MULT 21_{3}- 16 replace x^{r}by x^{r+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. 21_{2}because MULT disturbs the contents of these stores, so it will be kept in 19_{2}, Therefore, if 19_{2 }contains (13 - r) when 16 contains x^{r}, we must change C(19_{2}) to (12- r) when we change C(16) to x^{r+1}. So the loop consists of the instructions MULT <------| | 21_{3}- 16 | C'(16) = x^{r+1}| 19_{2}- 13 | C'(13) = 13 - r | 27 - 26 | | 13 - 19_{2}| C'(19_{2}) = 12 - r | 19_{2}- 28 | | ---nz-->| Out when r 12, C(16) = x^{r+l}= x^{13}z| 21_{3}- 13 We must now arrange to enter the loop with x^{r}in 16 and (13 - r) in 19_{2}for whatever value of r we like to choose. It is simplest to put x in 16, so 12 must be put into 19_{2}. As in the last example, when the constant 10 was assumed to be stored 1_{15}, 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 1_{18}. The obvious choice of constant seems to be 12, so that we add the two instructions 14 - 16 C'(16) = x 1_{18}- 19_{2}C'(19_{2}) = 12 at the head of the loop. As we have to calculate x^{13}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 1_{18}- 13 C'(13) = 13 27 - 26 C'(13) = 12 13 - 19_{2}C'(19_{2}) = 12 would have to be added at the head of the loop. But suppose we have two instructions 14 - 16 C'(16) = x 1_{18}- 19_{2}C'(19_{2}) = 13 after which we enter the loop at itsthirdinstruction, 19_{2}- 13. Then 1 will be subtracted from the number 13 in 19_{2}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 1_{18}- 19_{2}C'(19_{2})= 13 19_{2}- 13 <-----| C'(13) = 13 12 11 10 ....... 2 1 | 27 - 26 | | 13 - 19_{2}| C'(19_{2})= 12 11 10 9 ....... 1 0 | 19_{2}- 28 | |<---z-----|nz | On On On On On Jump | | | | | MULT | | | | | | | 21_{3}- 16 | C'(16) = x^{2}x^{3}x^{4}x^{5}...... x^{13 }| | |---------->| | | | |----> 21_{3}- 13 C'(13) = x^{13}There are 6 general points which this example illustrates:- (a) The order in which the loop was constructed was: (i) Basic orders: form x^{r+1}from x^{r}; (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 21_{3}- 16 instruction to the 19_{2}- 13 instruction had been taken one line higher to include the 1_{18}- 19_{2 }instruction in the loop, the number in 19_{2}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 19_{2}- 13 27 - 26 13 - 19_{2}reduce the counter, and the one instruction 19_{2}- 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 x^{14}unless the constant in 1_{18}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 advisedalwaysto use the sequence Charge count Test count (d) The reader may wonder why the number 13 was transferred from 1_{18}to 19_{2}before being used for counting. There are two reasons of which the second is the more important. Firstly, the sequence 1_{18}- 13 27 - 26 13 - 1_{18}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 1_{18}is not disturbed. So if there is an outer loop leading back from the 21_{3}- 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 y^{13}in 13. If counting had taken place in 1_{18 }there would have been 0 in 1_{18}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 1_{18}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 x^{15}, say, instead of x^{13}. All that needs modifying is the parameter in 1_{18}. 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 1_{18}is n if x^{n}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 3Given x in (16), and 10.2^{-14}in 19_{3}, sum the polynomial 2^{-14}(10x^{9}+ 9x^{8}+ ... + 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 P_{17 }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 S_{r}= 10.2^{-14}x^{9-r}+ 9.2^{-14}x^{8-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 S_{r}by x and the addition of r.2^{-14}; the result will be S_{r-1}. We shall need to keep a counter r.2^{-14}, say in 19_{2}, 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) = S_{r}, C(16) = x, undisturbed 21_{3}- 13 c'(13) = S_{r}x 19_{2}- 25 C'(13) = S_{r}x + r 2^{-14}=S_{r-1}13 - 14 C'(14) = S_{r-1}19_{2}- 13 C'(13) = r 2^{-14}28 - 26 Source 28 gives P_{17}, i.e. 2^{-14}13 - 19_{2}C'(19_{2}) = (r - 1) 2^{-14}We have now replaced S_{r}and r 2^{-14}by S_{r-1}and (r- 1)2^{-14}respectively. Work has finished when S_{0}is obtained, so one further instruction 19_{2}- 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 S_{10}= 0 and 10.2^{-14}in 14 and 19_{2}respectively, or S_{9}= 10.2^{-14}and 9.2^{-14}in 14 and 19_{2}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 19_{3}- 14 C'(14) = 10.2^{-14}= S9 19_{3}- 13 C'(13) = 10.2^{-14}and enter the loop at the 28 - 26 instruction, not at the MULT instruction. The full program is: 19_{3}- 14 Set S_{9}= 10.2^{-14}19^{3}- 13 C'(13) = 10.2^{-14}28 - 26 <----| | 13 - 19_{2 }| C'(19_{2})= 9.2^{-14}8.2^{-14}7.2^{-14}..... 1.2^{-14}0 | # 19 - 28 | | | |<--z---| | | |nz | On On On ..... On Jump | | | | | MULT | | | | | | 21_{3}- 13 | C'(13) = S_{9}x S_{8}x S_{7}x ..... S_{1}x | | | | | 19_{2}- 25 | | | | | | 13 - 14 | C'(14) = S_{8}S_{7}S_{6}..... S_{O}| | | | | 19_{2}- 13 | C'(13) = 9.2^{-14}8.2^{-14}7.2^{-14}..... 1.2^{-14}| | |-------->| | | | |-> 14 - 15 C'(15) = S_{o}# 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 19_{3}will give different approximations to the infinite series 2^{-14}(1 + 2x + 3x^{2}+ 4x^{3}.....) = 2^{-14 }(1 - x)^{-2}Example 4Given constants a, b, c and h in 17_{1}, 17_{2}, 17_{3}and 17_{0}respectively where a, b, and h are strictly positive, find the value of r (an integer) such that x_{r}= rh gives the smallest value of y_{r}= ax^{4}_{r}- bx_{r}+ C. Place the corresponding values of x_{r}and y_{r}in 19_{2 }and 19_{3}respectively. Assume that numbers are within the capacity of the machine. If y = ax^{4}- bx + c, y = 4ax^{3}- 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 x_{r }= rh in some store Evaluate y_{r}<------------------| | Test sign of y_{r}- y_{r-1}| / \ | +/ \- | / \ | END. Replace y_{r-1}by y_{r}| | y_{r-1}and x_{r-1 }are required values. Replace x_{r}__{1}by x_{r }| | Calculate x_{r+1 }| | | |------------------->| Notice that x_{r-1 }and y_{r-1}are both needed until the discrimination has taken place. The first discrimination must be on y_{1}- y_{o}, as the simplest method of starting the calculation is to set x_{o}= 0, y_{o}= C and enter the loop at "Calculate x_{r+1}". We shall keep x_{r-1}and y_{r-1 }in 19_{2}and 19_{3}; x_{r}will be stored in 16 when it has been calculated for use in forming y_{r}. The full program is: - 23 -## Technical Note No. M.S.38

30 - 19_{2}x_{o }= 0 ------ Set initial conditions 17_{3}- 19_{3}y_{o }= C ------ 19_{2}- 13 <--| x_{r-1}| 17_{0}- 25 | x_{r_1}+ h = x_{r}Calculate x_{r}| 13 - 16 |^{X}r ------ | 17_{1}- 14 | a | MULT | | 21_{3}- 14 | ax_{r}| MULT | | 21_{3}- 14 | ax^{2}_{r}| MULT | | Calculate y_{r }21_{3}- 13 | ax^{3}_{r}| 17_{2}- 26 | | 13 - 14 | ax^{3}_{r}- b | MULT | | 21_{3}- 13 | ax^{4}_{r}- bx_{r}| 17_{3}- 25 | ax^{4}_{r}- bx_{r}+ C = y_{r}| 19_{3}- 26 | | Test sign of y_{r }- y_{r-1}13 - 27 | y_{r}- y_{r-1}------- + | | END--------| | | - | 19_{3}- 25 | Replace y_{r-1}by y_{r }| 13 - 19_{3 }| y_{r}------ | 16 - 19_{2 }|_{Xr}Replace x_{r-1}by x_{r}|--------| ------ In this example it is y_{r}that determines whether the exit from the loop should be made, although the other variable x_{r}is the. counter which goes up in equal steps. I.6The instruction wordUntil 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 staticizerSource and destinationWhen we write the instruction 1_{15 }- 26 we mean that the machine must make a transfer fromSource1 toDestination26, 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 numberThe 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 1_{15 }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, theWait 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 NumberSome 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 theNext 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, theTiming 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.CharacteristicIn 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 theCharacteristic;but whatever the value of the characteristic, the wait number specifies thefirstminor 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 digitThe most significant bit of the word, used as the sign digit of a number, is theGo Digitof 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 StaticizerThis 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 wordRepresenting each of the 32 digits by a 1, the instruction is laid out as follows:11111111111111111111111111111111A 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 numbersThere 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. (Nothingcan. betaken out of TS Count into the rest of the store.) If an instruction specifies that the next one is stored in 1_{17}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 numberLet us code the three instructions 4_{30}2_{1 }- 13 4_{3}28 - 25 4_{5}13 - 2_{1}leading to 5_{7}. The instruction in 4_{30 }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 4_{3}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 4_{5}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 CharacteristicThe 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 TransferThe 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 TransferThe 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 TransferThe 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 3The 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 instructionsWhen 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

ExampleCode the following program: (1) |--> 5_{8}2_{12}- 14 | (2) | 6_{17}19_{3}- 7_{25}| (3) | 5_{29}18_{0}- 12_{12}| (4) | 4_{12}13 - 15 | (5) | 1_{14}20_{3}- 26 | (6) | 8_{17}0 - 17_{1}X | (7) | 7_{22}18_{0}- 19_{2}| (8) | 3_{29}18_{3}- 27 |<--------------------| + | - (9) 5_{9}9_{6,7}- 21_{2,3}(2 m.c.) (10) 1_{1}6_{7-9}- 17_{3,0,1}(3 m.c.) (11) 8_{9}19 - 25 (2 m.c.) (12) 6_{16}21_{2,3}- 17_{0,1}(2 m.c.) (13) 6_{24}17 - 18 (4 m.c.) (14) 2_{3}10 - 25 (32 m.c.) (15) 3_{7}24 - 14 (5 m.c.) (16) 5_{11}21 - 22 (4 m.c. e.o.) (17) 8_{31}11 - 8 (32 m.c.) 8_{0}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) 5_{8}contains 6, 2 - 14, 0, 2, 7 (2) 6_{17}" 5, 19 - 7, 0, 6, 10 (3) 5_{29}" 4, 18 - 12, 0, 13, 13 (4) 4_{12}" 1, 13 - 15, 0, 0, 0 (5) 1_{14}" 0, 20 - 26, 0, 1, 1 (6) 8_{17}" 7, 0 - 17, 0, 2, 3 X (7) 7_{22}" 3, 18 - 19, 0, 0, 5 (8) 3_{29}" 5, 18 - 27, 0, 0, 9 (9) 5_{9}" 1, 9 - 21, 2, 27, 22 (10) 1_{1}" 0, 6 - 17, 1, 4, 6 (11) 8_{9}" 6, 19 - 25, 2, 0, 5 (12) 6_{16}" 6, 21 - 17, 2, 2, 6 (13) 6_{24}" 2, 17 - 18, 1, 6, 9 (14) 2_{3}" 3, 10 - 25, 1, 3, 2 (15) 3_{7}" 5, 24 - 1, 1, 30, 2 (16) 5_{11}" 0, 21 - 22, 1, 15, 18 (17) 8_{31}" 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 thenextinstruction). 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 aDL,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 5_{8}, 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 6_{7-9}- 17_{3,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 aneven minor cycle and must end in anodd 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 8_{0}, not the one which is just about to be wiped out.CheckingThe 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.7SubroutinesMuch 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 1_{30}. This has the advantage that wait and timing numbers are now the numbers of the minor cycles referred to.ExampleRead a positive number K from a card. Then read a succession of numbers a_{i}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 a_{i}(3) Find|a^{ }_{i}| (4) Find |a_{i}|^{½}(5) Add |a_{i}|^{½}to previous sum, i.e. S^{1}= |a_{i}|^{½}+ S (6) Is S^{1}>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 wefind 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 DL3, F04/1 in DL4.^{ }Our complete program would be as given below, page 36. We use 19_{2}for storing E|a_{i}|^{½}, 19_{3}for counting the number of terms, 20_{2}for storing +K. We shall put -K into 19_{2}at the beginning and add successive values of |a_{i}|½ 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 19_{2}, 19_{3}

|---> (1) - 13 Link to 13 | ______ | 2_{28}|R 01/3| Reak K, | | 1_{30}30 - 13 | | 21_{2}- 26 +K to 20_{2}; -K to 19_{2}| | 21_{2}- 20_{2}| | 13 - 19 <--------------| | | | (2) - 13 | Link to 13 | ______ | | 2_{28 }|R 01/3| | Read a_{i}| | | 1_{30}^{ }30 - 13 | | | | 21_{2}- 27 | | / \ | | +/ \- | | 21_{2}- 13 21_{2}- 26 | |a_{1}| to TS13 | \ / | | \ / | | (3) - 14 | Link to TS 14 | | | ______ | | 4_{28}|F 04/1| | |a_{1}| already in TS 13 as required | | | 1_{30}19_{3}- 13 | Increase count. | | | (a) - 25 | (a)=10^{-9}| | | 13 - 19_{3}| | | | 14 - 13 | |a|^{½}to TS 13 | | | 19_{2}- 25 | Add previous sum | | | 13 - 27 | Is S - K>If no, store S -K in | | \ | 19_{2}and read next card | +| \- | | | \------->-------| | 20_{2}- 25 If yes, add K, to give S. | | 13 - 14 S to TS 14 | | (4) - 13 Link to TS13 | ______ | 3_{28}|P 01| Punch S | | 1_{30}19_{3}- 14 Count to TS 14 | | (5) - 13 Link to TS 13 | ______ | 3_{28}|P 01| Punch count | | 1_{30}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, 19^{3}- 13 (4): 1, 19_{3}- 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 ______ 2_{28}|R 01/3| 1_{30}: 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.) 1_{7}- 13 ______ 2_{28 }|R 01/3| 1_{30}: (1_{7})30 - 13 ... if the link is stored in 1_{7}.It is obeyed as if it is stored in minor cycle30 and the wait and timing numbers computed accordingly. One of the first instructions of the read subroutine is 13 - 1_{30},_{ }which plants the link in 1_{3}_{0}. 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 1_{30}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 1_{31}This idea can naturally be extended to higher order subroutines. Generally, an m^{th}order subroutine, uses at least one (m-1) order subroutine in it and plants its own link in 1_{29+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.8Modification of instructions and countingThe 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) = a_{0}+ a_{1}x + a_{2}x^{2}+ ... + a_{n}x^{n}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) = ( ... ((a_{n}x + a_{n-1})x + a_{n-2})x + ... )x + a_{0}, and we use this. If we define S_{n}= a_{n}and S_{r-1 }= S_{r}x + a_{r-1}for r = n, n-1, ..., 1, it is evident that S(x) = S_{o}. The block flow diagram of the summation would be Set r = n Set S_{n}= a_{n}( = Sr initially) | | <-----------------| Is r = 0? | / | | / | No | / | | Yes Replace r by r-1 | (Summation | complete) Find r by r-1 | | Find S_{r }x | | Add a_{r}_{-}_{1 }to produce S_{r-1}| |--------->----------| - 38 -## Technical Note No. M.S.38

Here we require the coefficients, a_{r}, in turn. If we have the instruction A_{o}- 14, (which picks out a_{0}) the addition of r.P17 (i.e. r is the wait number) will change this to A_{r}- 14 , tofetch a_{r}. 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 a_{o}.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 - B_{m}B_{m}: A_{r}- 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 - O_{m}Q_{m}[A_{r}- 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 Q_{m}[(B_{s}) : A_{r}- 14] if the basic instruction is stored in B_{s}. 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 1_{28}, with the next instruction Q_{30}. This is one of the most useful places for a modified instruction, as W is then the actual minor cycle number. The sequence 1_{26}: 14 - 25 1_{28}: 13 - 0_{30}Q_{30}: [ ] 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 Countnotas 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 11_{23}: 1_{25}- 13 C(1_{25}) = (1, 0 - 11, 0, 1,(15), 14, X) |-> 1_{27}: 13 - 0_{29}| | Q_{29}: [(1_{25}) : 0 - 11 X] | | | |---->---|Spill | | | | 1_{13}: 28 - 25 | | | | |-------<----------| | | 1_{14}.... <----| 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 11_{31}and takes its next instruction one m.c. later than before. Note that the instruction is obeyed Q_{29}._{ }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 22_{17}: 2_{21}- 13 2_{21}= (3, 3 - 29, 0, 0, (10), 17 X) .... 1_{28}: 13 - 0_{30}<-------| | Q_{30}[ 2_{21}: 3 - 29 x] | |-----------------| | | 3_{17}: 28 - 26 (31 m.c.) | | |----------------| | |->3_{16}: ... 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 Q_{3o}[3_{m }- 15] is followed shortly after by Q_{30}[26 - 3_{m}] 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: 1_{28}: 13 - 0_{30}Q_{30}[ 3_{m}- 15 ] 2_{12}... ...... 2_{25}: 2_{27}- 25 1_{28}: 13 - 0_{30}Q_{30}[26 - 3_{m}] 3_{12}: ... 2_{27}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.9Automatic modification and countingThe 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

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

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 canoccur 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 11_{23}: 1_{25 }-_{ }17_{1}C(1_{25}) = (1,i 0 - 11, 0,^{ }0,^{ }(15),^{ }27 X) |--> 1_{26 }:_{ }(2P1)17_{1}- 0_{29}, 1 Adds P17 | | Q_{29 }:_{ }[(1_{25}):0 - 11 X] |<----------------| | Spill 1_{27 }: ...._{ }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 11_{0}, 11._{1}, ..., 11_{31}and leaving the loop on the last occasion. The 17 - 0 instruction is in 1_{26}so that 1_{28}can still be used for a 13 - 0 instruction.Example 2Example 2 of I.8 can be similarly shortened. 2_{17}: 2_{21}- 17_{1}, C(2_{21})= (3, 3 - 29, 0, 12, (4), 28, X) |--> 3_{15}: (6P1) 17_{1}- 0_{17}, 1 Adds P17 + P22 | | Q_{17}.: [(2_{21}) : 3 - 29 X] |<-------------------| | 3_{16}..... 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 3n (≤32) numbers, x_{i}, are given in A_{0}, A_{1}, ... . They are to be replaced by f(x_{i}). 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 2_{28}, does not disturb QS 18, our program might be as below. n is in 18_{3}at the start. /Example - 46 -## Technical Note No. M.S.38

3_{19}: 3_{21,22}- 18_{1,2}(2 m.c.) / 3_{28}: (10 P1 ) 18_{2}- 0_{30},1 <-----| < Adds P17 to instruction | \ before obeying it. Q_{30}[(3_{22}) : A_{r}- 16] | | 3_{23}: 3_{25}- 13 | Place link ______ | 2_{28}: |f(x)| | | 1_{30 }: (3_{25}) : 18_{3}- 0_{3},0 | Subtract P17 from counter | / 3_{26}: (10 P1) 18_{1}- 0_{29},1 | <Adds P17 to instruction | \before obeying it Q_{29}: [(3_{21}) : 13 - A_{r}] | | 3_{24}: 18_{3}- 28 | Test counter | \ | | \ nz | Zero | \---------->| | 3_{27}Exit The contents of 3_{21}, 3_{22 }and 3_{25}are C(3_{21}) = (3, 13 - A, 0, 0, (0), 25) obeyed Q_{29}C(3_{22}) = (3, A - 16, 0, 31, (0), 23) obeyed Q_{30}C(3_{25}) = (3, 18 - 0, 0, 3, (0), 26) obeyed Q_{30,}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 3_{22}, and the store instruction, in 3_{21}, 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 3_{19 }and 3_{21-28 }only.Example 4The same as Example 3 without the restriction on n. A possible program follows. Again, n is in 18_{3}at the start. /Example - 47 -## Technical Note No. M.S.38

3_{18}: 3_{21,22}- 18_{1,2}(2 m.c.) 3_{28}: (10 P1) 18_{2}- 0_{30}, 1 <----------| | Q_{30}[(3_{22}) : A_{r}- 16] | | 3_{20}: 3_{23}- 13 | | ______ | 2_{28}: |f(x)| | | 1_{30}: (3_{23}) 18_{3}- 0, 0 | | 3_{26 }: (10 P1) 18_{1}- 0_{29}, 1 | | Q_{29 }:[(3_{21}) : 13 - A_{r}] | | | | Spill | Spill on replacing A31 |------------------>| | |->3_{15}: 18_{3}- 28 | | | z / \ nz | | | 3_{27}exit \--->-------|---| | | | 3_{16}: 3_{29,30}-18_{1,2}(2 m.c.)<-| | | 3_{0 }: (8 P1) 18_{2}- 0_{2},_{1 }| Adds P5 to instruction | Q_{2}:[(3_{30}) (A + 1- 16] ||3_{24}16 - 13 | Adds P10 to instruction | 3_{31 }: (9 P1) 18_{1}- 0_{1}, 1 | | Q_{1}:[(3_{29}) 13 - (A + 1)] | | 3_{19}: 18_{1,2}- 3_{29,30}( 2 m.c.) |<----------------------------| where C(3_{21}) = (3, 13 - A, 0, 0, (15), 16) .. obeyed Q_{29}C(3_{22}) = (3, A - 16, 0, 31, (0), 20) obeyed Q_{30}C(3_{23}) = (3, 18 - 0, 0, 3, (0), 26) Link; obeyed in 1_{30}C(3_{29}) = (3, 13 - A, 0, 0, (15), 16) obeyed Q_{1 }C(3_{30}) = (3, A - 16, 0, 31, (0), 20) obeyed Q_{2}Notes: (i) As far as the test instruction in 3_{15}, everything is as in Example 3, (except for the placing of some instructions). (ii) The store instruction, in 3_{21}, has 15 in the Joe digits, to make use of spill-over after A_{31 }has been replaced by f(x) (iii) The instructions in 3_{29,30}at start are the same as those in 3_{21,22}. They will be changed to 13 - (A + 1) and (A + 1) -^{ }16 respectively and then replaced in 3_{29,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 3_{24}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 3_{24 }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 3_{16}. 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 3_{24}and 3_{19}- 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.10Optimum codingThe 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.11The double-length accumulatorAny 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 21_{2}) into the more signifi- cant half (in 21_{3}). 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 21_{3}into 21_{2}, whatever the state of TCB, and there can only be carry from 21_{2}into 21_{3 }when TCB is off.Operations in 21_{3}The state of TCB does not affect these operations.Example 19_{5}- 21_{3}C'(21_{3}) = C(9_{5}), whether TCB is off or on.Example 29_{5}- 22_{3}C'(21_{3}) = C(21_{3}) + C(9_{5}), whether TCB is off or on.Example 39_{5}- 23_{3}C'(21_{3}) = C(21_{3}) - C(9_{5}) 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 422_{3}- 21_{3}C'(21_{3}) = ½C(21_{3}), whether TCB is off or on. This is a shift down exactly like 23 - 14.Example 522_{3}- 9_{5 }C'(9_{5}) = ½C(21_{3}), whether TCB is off or on. The numbers in 21_{2}and 21_{3}are unaffected.Example 621_{3}- 22_{3}C'(21_{3}) = 2C(21_{3}), 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 21_{2}.Double-length operations in 21TCB is off in all the following examples because the numbers in 21 are all double-length.Example 79_{4,5}- 21_{2,3}C'(21) = C'(9_{4}), C'(21_{3}) = C'(9_{5}). (2 m.c.) Of course this result is also true if TCB is on.Example 89_{4,5}- 22_{2,3}C'(21) = C(21) + C(9_{4,5}). (2 m.c.) Double-length addition.Example 99_{4,5}- 23_{2,3}C'(21) = C(21) -- C(9_{4,5}). (2 m.c.) Double-length subtraction..Example 1022_{2,3}- 9_{4,5}C'(9_{4,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 1122 - 21 C'(21) = 2^{-n}C(21 ). (2n m.c, e.o.) The letters (e.o) mean "transfer starts in aneven minor cycle and ends in anodd 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 anoddminor cycle.Example 1221 - 22 C' (21) = 2^{n}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 anoddminor cycleExample 1320 - 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 21_{2}Example 149_{4}- 21_{2}C'(21_{2}) = C(9 ), whether TCB is off or on. Of course, C'(21_{3}) = 0(21_{3}).Example 159_{4}- 222 C'(21_{2}) = C(21_{2}) + C(9_{4}), whether TCE is off or on. But C'(21_{3}) = C(21_{3}) if TCB is on, onlymaybe if TCB is off.Example 169_{4}- 23_{2}C'(21_{2}) = C(21_{2}) - C(9_{4}), whether TCB is off or on. But C'(21_{3}) = C(21_{3}) if TCB is on, onlymaybe if TCB is off.Example 1722_{2}- 9_{4}C'(9_{4}) = C(21_{2}) if TCB is on, onlymaybe if TCB is off. The numbers in 21_{2}and 21_{3}are unaffected whatever the state of TCB.Example 1821_{2}- 22_{2}C'(21_{2}) = 2C(21_{2}), whether TCB is off or on, But C'(21_{3}) = C(21_{3}) if TCB is on, onlymaybe if TCB is off. It will be seen that destinations 22 and 23 can always be used for addition and subtraction in 21_{2}with TCB on, and they can also be used with TCB off if the programmer does not mind changing the content of 21_{3}. Operations in 21_{2}with TCB off must be explained further.Example 194 - 24 TCB off 31 - 21 (2 m.c.) "Ones" in both halves of 21 27 - 22_{2}Add P_{1}to 21_{2}. 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 21_{2}and 21_{3}, This means that carry from 21_{2}to 21_{3}must be allowed.Example 204 - 24 TCB off 27 - 21_{2}P_{1}to 21_{2}30 - 21_{3}0 to 21_{3}31 - 22_{2}Add "ones" to 21_{2}. TCB is off. This time we place the double-length integer 1 in 21 and add "ones" to 21_{2}. If we just allow carry from 21_{2}to 21_{3}the result is a P_{1}in 21_{3}, i.e. 2^{32}, whereas we should like the result to be 0. The addition has been 1 + (2^{32}- 1) = 2^{32}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 2^{32}-1.The method used when adding a number into 21- all zeros or all ones. Then a number is subtracted from 21_{2}with TCB off is to allow carry from 21_{2}into 21_{3}and to add a number into 21_{3}which is 32 copies of the sign digit of the number added_{2}with TCB off carry is allowed from 21_{2}into 21_{3}and a number is subtracted from 21_{3}- this number is again 32 copies of the sign digit of the number subtracted from 21_{2}. 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 214 - 24 TCB off 30 - 21 (2 m.c.) 0 in 21_{2}and 21_{3}27 - 23_{2}Subtract P_{1}from 21_{2}. 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 224 - 24 TCB off 30 - 21 (2 m.c.) 0 in 21_{2}and 21_{3}31 - 23_{2}Subtract "ones" from 21_{2}. 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 234 - 24 TCB off 29 - 23_{2}. 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 P_{32}from 21_{2}, but in fact it adds P_{32}to 21_{2}, so rounding off the double- length number in 21 to single-length. This instruction is very common at the end of multiplication subroutines.Example 244 - 24. TCB off 29 - 22_{2}. The converse effect to the previous example: P_{32}issubtractedfrom 21_{2}.Example 254 - 24 TCB off 21_{2}- 23_{2}The second instruction subtracts C(21_{2}) from (21_{2}) and leaves in 21_{2}. Also, if the number in 21_{2}had a P_{32}, (-P_{1}) is subtracted from 21_{3}; - 54 -## Technical Note No. M.S.38

but if the number in 21_{2}had no P_{32}, 0 is subtracted from 21_{3}. The total effect is to clear 21_{2}and to round off the double-length number in 21 in a single instruction.Example 26As 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 275 - 24 TCB on 22_{2}- 9_{4}½C(21_{2}) is put into 9_{4}; neither half of 21 is affected. The shift is a correctly signed arithmetical shift - the P_{31}digit of C'(9_{4}) is the P_{32}digit of C(21_{2}) and the P_{32}digit of C'(9_{4}) is the same - and the P_{1}digit of C(21_{2}) is truncated.Example 284 - 24 TCB off 22_{2}- 9_{4}The only difference from the previous example is in the P_{32}, digit of C'(9_{4}). It is now a copy of the P_{1}digit of C(21_{3}). It is difficult to see any application c this.Example 294 - 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 30The instruction 22_{3}- 21_{3}gives a truncated shift of one place, whatever the state of TCB. To get a rounded shift, call the number in 21_{3}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 22_{3}. The instruction 22_{3}- 23_{3}gives (a + b) in 21_{3}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 22_{2}- 23_{2}with TCB on gives a rounded shift of the number in 21_{2}.Example 31C(15) = r P_{17}where r<32. |-> 1_{3}1_{6,7}- 21_{2,3}(2 m.c.) [1, 9-16, 0,0,27 and 1, 16-9,0,0,(15)4] | | 1_{8}15 - 22 (2 m. c.) | | 1_{28}21_{2}- 0_{30}| | Q_{30}[1_{6}, 9_{r}- 16] | | 1_{27}21_{3}- 0_{29}| | Q_{29}[1_{7}, 16 - 9_{r-1}] | | |<---------------| Spill over, r=32 1_{4}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.12The multiplier and dividerDEUCE 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 P_{32}digit means that the number is greater than 2^{31}) 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 multiplierThe 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 21_{3}, and 21_{2}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 21_{3}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 2_{1}31 - 16 2_{3}31 - 21_{3}2_{5}30 - 21_{2}2_{8}0 - 24 (in m.c. 11) the multiplier takes the product of 11....11 and 11....11. These are both the positive integer 2^{32}-1, so the product obtained is (2^{32}-1)^{2}, i.e. 100...00,011....11. * If 21_{2}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 21_{2}is negative, however, the number in 16 is multiplied by a number which is not the content of 21_{3}. - 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 integersa and b are signed integers, say in 14 and 16. The subroutine to multiply them will start 30 - 21_{2}14 - 21_{3}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 (2^{32}+ a) because it takes the presence of the P_{32}digit in a to mean that a > 2^{31}, not that a is negative. So if a is negative and b is positive the multiplier produces (2^{32}+ a)b, and the subroutine must subtract 2^{32}b from the result. Conversely, if a is positive and b negative, the multiplier produces a(2^{32}+ b) and the subroutine must subtract 2^{32}a from the result. If both a and b are negative the multiplier produces (2^{32}+ a)(2^{32}+ b)= 2^{64}+ 2^{32}(a + b) + ab, so the subroutine must subtract 2^{32}(a + b) from the result given by the multiplier. This appears to give 2^{64}+ ab, not the required result, but as DS 21 only holds 64 binary digits the 2^{64}is a single digit beyond the more significant end of the result. The method used to subtract 2^{32}c from the double-length number in 21 is simply to subtract c from 21_{3}. The rule for sign-correction is: If either of a or b is negative, subtract the other from 21_{3}. - 58 -## Technical Note No. M.S.38

The complete subroutine for multiplying signed integers is 2_{20}30 - 21_{2}2_{23}14 - 21_{3}a to 21_{3}(b is already in 16) 2_{25}0 - 24 MULT starts in m.c.27 2_{28}13 - 1_{30}Plant link 2_{30}14- 27 Test sign of a / \ +/ \- 2_{26}30 - 13 2_{27}16 - 13 C!(13) = 0 or b as a is +ve, -ve \ / \ / 2_{29}16 - 27 Test sign of b / \ +/ \- 2_{21}30 - 25 2_{22}14 - 25 Add 0 or a as b is +ve, -ve Subtract sign \ / \ / Subtract sign correction \ / 2_{24}13 - 23_{3}in m.c.29 after MULT has ended. 1_{30}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 2_{30}is time wasting. The time between start- ing the multiplier and reaching the instruction in 2_{29}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 21_{3}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 2_{30}, 2_{26}and 2_{27}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 2_{18}30 - 21_{2}2_{21}14 - 21_{3}2_{23}0 - 24 in m.c.25 2_{26}21_{2}- 15 in m.c.28 2_{22}13 - 1_{30}Plant link 2_{20}16 - 27 / \ +/ \- (Correction for sign of b) 2_{24}30 - 23_{3}2_{25}14 - 23_{3}in m.c.27 \ / \ / 2_{27}15 - 23_{3}(Correction for sign of a) 1_{30}Link - 59 -