Control of magnitudes of numbers is generally simple when solving differential equations. A great deal can be learned in this connection from standard techniques involving scale factors, in connection with the differential analyser.
In matrix and other calculations it is possible to adjust the magnitudes of the numbers being manipulated by introducing what is in effect a floating binary point except that instead of controlling the position of the binary point of every number we control only the position of the binary point of groups of numbers.
This type of programming is complicated when using the order code used at present in E.D.S.A.C. It seems better to make arrangements so that when a number exceeds the capacity of the machine the alarm bell does not ring, but control is transferred to a system of orders which can be programmed so as to adjust magnitudes and allow the computation to proceed.
At first sight one of the chief difficulties in programming complex problems on automatic computing machines like the E.D.S.A.C. would seem to be the fixed binary point. Repeated addition and multiplication will tend to make the resultant number either very large or very small. In the first case the alarm bell will ring; in the second case accuracy is lost. From a more general point of view it seems a disappointing limitation on a so-called automatic computing machine that it should stop when numbers exceed an upper limit. The ideal machine would automatically adjust the magnitudes of the numbers it contains so that the capacity of the machine is never exceeded. The programming required to do this with the present order code is clumsy and lengthy.
The main object of this note is to point out that the fixed binary point is not so troublesome as is commonly supposed. In many cases it is possible to arrange the programme so that the machine checks certain key numbers periodically during a computation and adjusts magnitudes where necessary. The essential features of this process are best illustrated by examples. After the discussion of examples it will be clear that the control of magnitudes on machines like the E.D.S.A.C. would be facilitated by including a new type of order in the order code.
In general it will be easy to control the magnitudes of numbers occurring in the solutions of differential equations.
A simple example will illustrate one possible method. Consider the solution, for positive x, of the equation:-
dy/dx = y ; y = 0.5 at x=0
the exact solution is y = 0.5 ex
Suppose we know the values of y from x = 0 to x = 0.4 at intervals of 0.1 in x and we extend the solution by the Adams-Bashforth process (see Table 1). The value of y for x = 0.5, and hence a new line of differences, can be calculated in the usual way. Similarly for x = 0.6. But when we come to x = 0.7 the value of y exceeds unity and the alarm bell would ring if the computation were carried out on E.D.S.A.C.
This could be avoided by telling the machine to compute the value of y for any given value of x; form differences; then go back and check the value of y; if the value of y is less than 0.8 (say) proceed to compute the value of y corresponding to x + 0.1, and so on; but if the value of y is greater than 0.8 halve the values of y and the appropriate differences before proceeding to the next step; record in some memory position that from this point onwards all the values of y must be multiplied by 2 to give the correct answer. This procedure is illustrated in Table 2.
Similarly, if we are solving
dy/dx = -y ; y = 0.5 at x=0 solution is y = e-x
the programming can be arranged so that whenever y falls below say 0.4 the appropriate quantities are automatically multiplied by 2 and y is doubled from this point onwards. In general, of course, care must be taken that when numbers are increased the apparent increase in accuracy introduced is not spurious, but this is another problem.
In the example given it was necessary to change only the magnitudes of the variables. If the equations are not homogeneous and linear, or if there are several independent variables, it will in general be necessary to change coefficients which will involve changing the equations themselves. Thus consider the solution of
dy/dx = y + x
If we have to reduce y by 2, i.e. set z = 0.5 y then the equation becomes
dz/dx = z + 0.5x
and the coefficient of x, which is contained in the programming is altered. Similarly, for non-linear equations. For example, if we set z = 0.5 y in
dy/dx = y2
this equation becomes
dz/dx = 2z2
These examples involve no difficulty in principle.
Now consider equations of order higher than the first. One method for numerical solution of the equations
d2z/dx2 = -k2z
is to write
dz/dx = w ; dw/dx = -k2z
and to solve these two equations simultaneously by step by step methods. Then if z has a maximum value of unity, w will have a maximum value of k and dw/dx will have a maximum value of k2. Clearly it is possible to arrange that all the numbers are of the same order of magnitude by writing
v = w/k ; y = kx
then the equations become
dz/dy = v ; dv/dy = -z
This is only a very particular example. The general question may be asked: Is it possible to write any system of differential equations as a first order system in such a way that the dependent variables are all of the same order of magnitude?
Experience with the differential analyser is interesting in this connection. Assume that any number of integrator tables are available. Then any system of equations can be solved by converting them into a first order system. The displacements of the integrator lead screws correspond to the dependent variables in these equations. In order to ensure that the accuracy of solution is as great as possible these integrator displacements must all be comparable with each other during the course of the solution. The maximum values must be near the maximum possible displacements and the minimum values should not be less than one-tenth of the maximum possible values except for short periods of time, for example, if the function is oscillating. In many problems it turns out that no matter how awkward the form of a system of differential equation, variables can be introduced such that all the quantities on the integrator displacements are comparable during the whole course of the solution. In the differential analyser this process is carried out by introducing suitable scale factors and is realised by using suitable gear ratios for connecting the shafts of the integrator tables. Scale factors ensure that the correct numerical coefficients exist in the first order equations relating variables and their derivatives. It may happen that it is not possible to maintain all the variables comparable throughout the whole course of the solution. In this case it is generally possible to find some simple way of changing scale factors (by changing gear ratios) periodically during the solution.
Translating these statements into the language of automatic computing machines, it will be possible to write any system of differential equations in terms of dependent variables which are comparable with each other over some range of the independent variable. In the same way as scale factors relate differential coefficients and variables on the differential analyser, it will be necessary to introduce factors relating differences of variables and the variables themselves. But an automatic computing machine has the advantage that it can control the factors during the computation and can be made to change the factors in a way determined by the progress of the solution. The controlling of eight integrators in a differential analyser so that the integrator displacements are comparable throughout a calculation is surprisingly easy. In an automatic computing machine when the allowable maximum to minimum value may be 100-1 or even more instead of 10-1, and factors can be changed automatically by the machine itself, the control of magnitudes in simultaneous first order differential equations should present little difficulty.
This discussion may not have been too clear if the reader is not familiar with the differential analyser. The main point is that the study of the use of scale factors on the differential analyser throws a considerable amount of light on the problem of controlling magnitudes of variables in systems of differential equations. The techniques used on the differential analyser can be applied to the control of magnitudes in automatic computing machines when solving differential equations.
From the discussion in section 2 it will be clear that the control of magnitudes in solving differential equations is relatively easy because a step by step process is used and the variation in magnitude of the variables and differences from one step to the next can be made as small as desired by decreasing the interval of integration. It is true of most iterative processes also that the numbers which appear at any stage are not widely different from those that appeared in the previous stage. But the situation is quite different for many computations. In general it is not easy to guess the size of the numbers that are likely to appear and to check their magnitude as the computation proceeds. Even in forming the sum a + b if we know nothing about a and b it is necessary to prove that
|a/4 + b/4| < 1
or some similar inequality before we can be sure that the operation a + b will not exceed the capacity of the machine.
A typical problem which may be encountered in calculations involving matrices is formation of a scalar product (Σai bi). The result may be several times greater than any individual term but usually the terms cancel each other due to random sign distribution. If the calculation is arranged so that the sum will never ring the alarm bell, accuracy will be lost in most cases. With the usual order code the number of orders required to check that a scalar product involving many terms will not exceed unity at any stage in its formation would require extra storage space and in large problems might be prohibitive.
Methods can be devised for some types of computation to ensure that all numbers are less than unity but, in general, maximum accuracy is not obtained. In addition, this is a severe restriction on the possible methods that can be used. For example, it is possible to solve linear equations by pivotal condensation, pivoting on the largest element at each step, so that all numbers are less than unity. But the accuracy is less than in methods like that of Choleski which employ scalar products which are formed in one sequence of operations. Also, owing to the limited memory of any machine, it may be desirable to solve the equations by a method which does not require that all the coefficients be held simultaneously in the machine. In this case it is extremely difficult with the usual order code to devise a method which will ensure that no numbers exceed unity without great loss in accuracy, as in this type of calculation the machine has to accept information piecemeal and carry out computations which will always lead to numbers less than unity regardless of the magnitudes of the infinite variety of coefficients which may be fed into the machine at a later stage in the solution. Before considering methods for overcoming these difficulties, note that in many cases it is possible to arrange a computation so that the numbers being manipulated are arranged in groups; during computation certain key numbers are checked periodically; when these key numbers fall outside certain upper and lower limits arrangements can be made to change the magnitude of each of the group of numbers as required. All members within one group are treated similarly, e.g. they are all halved or all doubled. The procedure can be illustrated by the first example given. in Section 2. In solving the differential equation, y and its differences were considered as one group of numbers; y is the key number. When y exceeds a definite value, the value of y and of the differences from this point onwards are halved. It is necessary only to keep a record of the positions where the division by 2 is carried out.
Similarly, when multiplying together two matrices A (m x n) and B (n x p) the columns of B can be considered as p groups of numbers whose magnitudes will be controlled. For the time being ignore the fact that if a number exceeds unity the machine will ring the alarm bell and stop. Suppose that when a number exceeds unity the machine can ask itself At what stage of the computation has a number exceeded unity?. If two matrices are being multiplied the answer can be found immediately When multiplying the ith row of A with the jth column of B. Then we can programme the machine to carry out the following operation:-
Reduce the jth column of B by half; record this fact; erase the partial scalar product of the ith row and the jth column that has been formed up to this point; halve all the products in the jth column of the product matrix and start forming the i-jth term again.
This procedure is represented schematically in Figure 1.
The basic idea of the two examples of magnitude control which have been described in detail may be summarised by saying that we operate with a floating binary point, except that instead of recording the floating binary point of every single number we record only the position of the binary point of groups of numbers, the relative magnitude of numbers within the group remaining the same.
In the E.D.S.A.C. a continuous check is automatically kept on the magnitude of the number in the accumulator. If it ever exceeds unity the machine is stopped and an alarm sounded. The procedure described at the end of Section 3 could be carried out by altering this so that when the number exceeded unity control was transferred to a specified storage location x. If it was ever desired to stop the machine in these circumstances, x could contain the order Z already existing in the E.D.S.A.C. order code.
But if the calculation is complicated, the situation may be more difficult. For example, if we had to form AB + C, where A, B and C are matrices, there are two points at which numbers can exceed unity; in the multiplication or in the addition. We describe one possible method of dealing with this situation. Suppose that the orders for dealing with numbers exceeding unity during the multiplication are in memory position y onwards and for numbers exceeding unity during addition they are in memory position z onwards. Then programme so that when carrying out the multiplication processes, the order in position x is Clear the accumulator and the order in position x + 1 is If the Number in the accumulator is greater than or equal to zero, transfer control to position y. When carrying out addition replace the number y in the order in position x + 1 by the number z. Then when the number in the accumulator exceeds the unity the machine will automatically select the appropriate procedure. The machine is programmed so that it distinguishes between mistakes in the multiplication and mistakes in addition.
In parts of the computation where it is not possible to make the machine change the orders of magnitude, the order in memory position x is replaced by Ring the alarm bell. The important thing of course is to ensure that the programming has covered all possibilities, so that the machine will change orders of magnitude in a particular way only if the machine has exceeded unity for the reason that has been allowed for. This may require ingenuity in programming.
Although it is true that the magnitude of numbers can be changed automatically by the existing order code without the introduction of new orders the advantages of including a special order to facilitate the control of magnitude are:
A new type of order will be particularly advantageous for machines with only a single accumulator like E.D.S.A.C. Since this note was written I have been informed by Mr. John Todd that an order similar to that described has been included in E.D.V,A.C.
Magnitudes which fall below a certain limit can be dealt with by the same methods as for numbers exceeding unity. The distinction is that in this case the check does not need to be carried out before the operation is performed which simplifies the problem considerably. It seems hardly worth while including a special order to do this.
The question of control of the magnitude of numbers, is connected with the problem of the most desirable upper limit to adopt. Most computing machines have unity as the upper limit. The reason usually given is that the product of any two numbers will never exceed the capacity of the machine, but since the sum and quotient of two numbers can exceed unity and the repeated multiplication of numbers less than unity will certainly result in loss of accuracy, the argument does not seem to be conclusive. It seems plausible that it will be easier to keep the orders of magnitude of numbers near unity in a long calculation if the upper limit of numbers in the machine is 2.