next up previous
Next: The logical operations Up: Alan Turing's Manual for Previous: Examples of programmes on

The multiplier and the double length accumulator

We shall now begin to describe the various respects in which the full machine differs from the reduced machine. Most of these differences are essentially independent. One may satisfactorily learn the effect of each difference as if added to the reduced machine in the absence of the others, and having learnt these effects will be in a position to manage the whole machine.

We begin by considering the effect of adding a multiplier to the machine. If we regard a standard number as consisting of forty binary digits then the product of two such numbers will occupy eighty digits. For this reason it is necessary to have an eighty digit accumulator. This decision in itself requires us to adopt a more sophisticated attitude to our numbers and our rows of digits. In the reduced machine it was almost possible to regard the long lines as representing integers, but it was necessary to admit that they were really to be reckoned modulo $2^{40}$. Long lines with a `1' in the most significant place could be regarded as representing negative numbers, provided that it is accepted that positive numbers greater than $2^{39}-1$ cannot be represented. With the double length accumulator similar considerations apply with greater complexity. Numbers held in the store must be reckoned modulo $2^{40}$ as before, but numbers in the accumulator must be reckoned modulo $2^{80}$.

In order to be able to express these matters clearly it is necessary to have notations which draw the essential distinctions, though these distinctions may appear pedantic, and though in a majority of applications the notation is not needed in all its detail. We distinguish therefore between `rows of digits' and numbers. I do not think that either of these expressions needs much elaboration. By numbers I shall mean real numbers. The content of any part of the machine will be a row of digits or an assembly of such rows, and not a number (with the exception of the multiplicand). Additions and multiplications are however performed on numbers and not rows of digits. However, in order that the processes of the machine may be described in terms of these operations it is necessary to be able to relate rows of digits to numbers, and vice-versa.

It would be sufficient in theory to be able to connect one number with each row, in such a way that all rows got different numbers. In practice four possible conventions present themselves particularly forcibly. We assume that our row of digits is of length $R$ and the $r$th digit is $\epsilon_{r-1}$.

We shall use all of these conventions, both in connection with the store lines, and with the accumulator. To convert a row into a number according to one of these conventions one writes respectively $+$, $\pm$, $f+$, or $f\pm$ as a suffix after the content of the row.

As regards the converse process, that of defining rows of digits in terms of numbers it will suffice to be able to take any sequence of consecutive digits from the binary expansion of a number. Accordingly we say that for any real number $\alpha$, and integers $m$, $n$ for which $n \ge m$, $\{\alpha\}_m^n$ is the row of digits forming the coefficients of the $m$th to the $n$th powers of two in the binary expansion of $\alpha$. If possible this expansion is to be terminating.

A number of statements are made below in illustration of these conventions.

  1. $\tp{//G}_+ = 13 \times 2^{11}$
    $\tp{//G}_\pm = -3 \times 2^{11}$
    $\tp{//G}_{f+} = {{13} \over {16}}$
    $\tp{//G}_{f\pm} = {{-3} \over {16}}$
  2. $\vert(\{\alpha\}_{-20}^{-1})_+ - \alpha\vert < 2^{-20}$ provided $0 < \alpha < 1$
    $(\{1\}_{-20}^{-1})_+ = 0$
  3. $\vert\{[\tp{/C}]_+[\tp{@C}]_+\}_{40+}^{79}[\tp{:C}]_+
- \{[\tp{/C}]_+[\tp{:C}]_+\}_{40+}^{79}[\tp{@C}]_+ \vert < 2^{40}$
A further convention which may be used in this connection is the use of the symbol $\Theta$. This is somewhat analogous to the use of $O$, $o$ in analysis. One uses $O(f(x))$ to mean `some function $\phi(x)$ such that there exists a positive $K$ satisfying $\vert\phi(x)\vert < Kf(x)$ for all sufficiently large $x$'. There is also an understanding that the functions $\phi$ and constants $K$ may be different at every appearance of $O$. The use of $\Theta$ is similar. $\Theta(x)$ means simply `some quantity $\alpha$ satisfying $\vert x\vert < \alpha$' and again may be different on every appearance. Thus for instance from $\Theta(1) = {1 \over 2}\Theta(1)$ one cannot conclude $\Theta(1)=0$ for the two appearances of $\Theta(1)$ might have the values $1 \over
4$ and $1 \over 2$. Using this convention 2) above could be written

${\{\alpha\}_{-20}^{-1}}_+ = \alpha + \Theta(2^{-20})$ provided $0 < \alpha < 1$

In terms of these conventions we may explain the properties of the multiplier as follows. To describe the state of the Mark II machine we give the states of the stores and control as in the reduced machine, but the accumulator is an eighty digit one. We also have to describe the state of the `multiplicand'. This is considered to be an integer which may take any value from $-2^{39}$ to $2^{39}-1$. In this respect the multiplicand is exceptional. The contents of all other parts of the machine are considered as rows of digits. Having explained this a number of further function symbols should become intelligible, viz. those marked m in the list below.

[The appendices to the manual do contain a list of instructions (in fact, two; one as part of a quick-reference sheet), but oddly, neither is marked as described. From those lists, the function symbols directly relevant to the multiplier are as follows, where D denotes the value of the multiplier:

Function symbol Equations
/C ${\tt\bf D}' = {\tt\bf S}_+$
/K ${\tt\bf D}' = {\tt\bf S}_\pm$
${\tt\bf A}' = \{{\tt\bf A}_+ - {\tt\bf D}{\tt\bf S}_+\}_0^{79}$
/D ${\tt\bf A}' = \{{\tt\bf A}_+ - {\tt\bf D}{\tt\bf S}_\pm\}_0^{79}$
/N ${\tt\bf A}' = \{{\tt\bf A}_+ + {\tt\bf D}{\tt\bf S}_+\}_0^{79}$
/F ${\tt\bf A}' = \{{\tt\bf A}_+ + {\tt\bf D}{\tt\bf S}_\pm\}_0^{79}$
There are several additional function symbols whose properties can only be explained (or must be redefined) with reference to the 80-bit accumulator of the real machine, as opposed to the 40-bit accumulator of Turing's ``reduced machine''. If we define ${\tt\bf L}=\{{\tt\bf A}\}_0^{39}$ and ${\tt\bf M}=\{{\tt\bf A}\}_{40}^{80}$, then these are as follows:
Function symbol Equations
/E ${\tt\bf S}' = {\tt\bf M}$
/A ${\tt\bf S}' = {\tt\bf M}$, ${\tt\bf A}^{'} = \{{\tt\bf L}_+\}_0^{79}$
/S ${\tt\bf S}' = {\tt\bf L}$
/I ${\tt\bf L}' = {\tt\bf M}$, ${\tt\bf M}^{'} = {\tt\bf L}$
/U ${\tt\bf S}' = {\tt\bf L}$, ${\tt\bf A}^{'} = \{{\tt\bf M}_+\}_0^{79}$
T/ ${\tt\bf A}' = \{{\tt\bf S}_+\}_0^{79}$
TA ${\tt\bf S}' = {\tt\bf L}$, ${\tt\bf A}^{'} = \{0\}_0^{79}$
T: ${\tt\bf A}' = \{0\}_0^{79}$
TI ${\tt\bf A}' = \{{\tt\bf A}_+ + {\tt\bf S}_+\}_0^{79}$
${\tt\bf A}' = \{{\tt\bf S}_\pm\}_0^{79}$
TN ${\tt\bf A}' = \{{\tt\bf A}_\pm - {\tt\bf S}_\pm\}_0^{79}$
TF ${\tt\bf A}' = \{- {\tt\bf S}_\pm\}_0^{79}$
TC ${\tt\bf A}' = \{{\tt\bf A}_\pm + {\tt\bf S}_\pm\}_0^{79}$
TK ${\tt\bf A}' = \{2{\tt\bf S}_\pm\}_0^{79}$
Further supplementary tables of function codes will be added after subsequent sections, except where the relevant instructions are specifically described in the original text.]

We may allow certain abbreviations as admissible, viz.

(a) Where it is clear that a row of digits is meant, and the number $N$ of these digits is known one may write $U$ for $\{U\}_0^N$, where $U$ is an expression representing a real number, e.g., the equation for /F may be abbreviated from ${\tt\bf A}' = \{{\tt\bf A}_+ + {\tt\bf D}{\tt\bf S}_\pm\}_0^{79}$ to ${\tt\bf A}' = {\tt\bf A}_+ + {\tt\bf D}{\tt\bf S}_\pm$.

(b) When it is evident that a real number is meant, and it is irrelevant whether a suffix $+$ or $\pm$ is used (or irrelevant whether $f+$ or $f\pm$ is used) one may omit the suffix (or use $f$ only) e.g. the equation for /F may be abbreviated further to ${\tt\bf A}'={\tt\bf A}+ {\tt\bf D}{\tt\bf S}_\pm$.

[Turing makes little use of the notation introduced here in the rest of the manual, except briefly towards the end when discussing systematic errors in programs.]

next up previous
Next: The logical operations Up: Alan Turing's Manual for Previous: Examples of programmes on
Robert S. Thau 2000-02-13