|
HOME >
Difference Engines |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Difference Engines |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
The
motivation at the beginning of the 19th century for the design of Charles
Babbage's
difference engines was the desire to be able to create absolutely
accurate mathematical tables. Tables of standard mathematical
functions such as sines, cosines, logarithms etc. were essential to
astronomy and navigation (which at the time depended heavily on
astronomical observations). Published tables were full of
errors, either from mistakes made in the calculations themselves, or
introduced in the typesetting and printing process. Many ships were
lost because of the resulting errors in navigation. In a perhaps
apocryphal statement when reviewing with John Herschel the errors in a
newly computed set of tables, Babbage is supposed to
have exclaimed "I wish to God these calculations could be done by
steam!"
The method
of
differences is a technique for calculating tables, in which the
vast majority
of the calculation involves nothing more than simple addition or
subtraction. The function to be tabulated is first approximated over
some range by a polynomial.
The degree of the polynomial depends on the desired accuracy of the
table to be calculated, and on the range of the function being spanned
by a
single polynomial approximation.
The method was first applied by Baron Gaspard de Prony in France in the 1790's to produce the manuscripts for 18 volumes of tables of logarithms and trigonometrical functions calculated to between 14 and 29 decimal places. A few expert mathematicians determined the most appropriate formulas to use for the calculations, then a second group of lesser mathematicians used the formulas to compute sets of initial values for a third, much larger group of people, only skilled in simple arithmetic to do the vast bulk of the work. This third group was divided into two sets to perform the same calculations independently. Finally the second group was employed again to check the results by comparing the results from the two sets of calculations. Babbage realized that the entire work of the third group could be eliminated by machinery, and further that since the calculations would be automatic, without the possibility of human error, much of the work of the second group could be dispensed with as well. Consider the simplest example; computing a table of values of the function n^2. In the table below, successive values of n are listed in the first column. The corresponding values of n^2 are in the second column. The column headed D1 contains the first differences, i.e. the difference between successive pairs in the N^2 column, while the D2 column contains the second differences, i.e. the differences between successive pairs in the D1 column. Note that the entries in the D2 column are constant. It is a general result, that for a polynomial of degree n, the nth difference will be constant. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Knowing this, and given just the first row of the table we can now reconstruct the rest of the table, for arbitrary values of n, with nothing but addition. Obviously the next entry in the D2 column is the constant 2. To get the next entry in the D1 column, just add the value from the same row of the D2 column to the current entry in the D1 column. Likewise to get the next entry in the N^2 column, just add the value from the same row in the D1 column to the current entry in the N^2 column. To see why this works mathematically, suppose we know the value of n^2 for some value of n. Then to get the next value, we must calculate (n+1)^2. If we consider the difference between this and n^2 (whose value we already know) we get:
which is an expression of degree one less than the value we are trying to compute. Now just iterate the process. Assume we know the value of 2n +1 for some value of n, then the next value of D1 will be 2(n+1) + 1, and computing the difference from the previous value (which again we already know), we have:
So, if we know for n = 0 that n^2 = 0 and 2n + 1 = 1 (which are trivial to compute), we have the first row of the table and the rest follows from simple addition. For a slightly more complex example, let's now go through the same steps for the function n^3. Here our table will be: |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
We see that three orders of difference are required to get to a constant (since this is a third order polynomial). In this case the third order difference is the constant 6. As before the next entry in the D2 column is obtained by adding the value in the D3 column to the current D2 entry, the next D1 entry is obtained by adding the value in the D2 column to the current D1 entry, and the next value in the N^3 column by adding the value in the D1 column to the current N^3 entry. The mathematical explanation is derived as above, but this time with one extra step required. Assume we know n^3 for some n and compute the expression for the next value of n, i.e. (n+1)^3. Now form the first difference:
Thus D1 is a second order polynomial. Proceeding as before:
a first order polynomial, and, finally:
a constant. Finally, to show there is nothing special about simple squares and cubes, consider the more general polynomial n^3 - 2n^2 +3n -2. Following the usual steps we would have, in this case:
So, starting from these formulas, for n = 1, our polynomial n^3 - 2n^2 +3n -2 has the value 0, and the differences are D1 = 4, D2 = 8, and D3 = 6. So, constructing the table, our first row will contain these values, and the rest of the table can be filled out as before:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| We see
that the general case of an
nth degree polynomial requires n differences to evaluate by this
method, and that, once we have found the initial values for the first
row of the table, the only arithmetical operation required to compute a
table of arbitrary length is simple addition. It is thus possible to
envision a machine which holds n columns of digits (to represent n
distinct numbers) with mechanism such that on each cycle of the
machinery, the number in each column is added in turn to the adjacent
column. At the conclusion of each cycle the number on the last column
is the next value of the polynomial under evaluation. This is the basic
principle of the difference engine. As noted earlier, Babbage considered it equally important that not only were the results computed automatically, but also that there be no possibility of errors in transcription when transferring to printing plates. His designs therefore also included machinery to automatically impress results (suitably formatted) directly onto offset printing plates for subsequent use in the printing process with no human intervention. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|