Babbage argued that he
. . . considered that a machine to execute the mere isolated operations of arithmetic, would be comparatively of little value
But
"On the otherhand the method of differences supplied a general method by which all Tables might be computed through limited intervals, by one uniform process. Again the method of differences required the use of Addition only. ..."
[Extract from Chapter V of Passages from the Life of a Philosopher (1864), by Charles Babbage.]
Ordinary arithmetic calculating machines, in Babbage's day, of the Leibnizian or Pascaline type, could only carry out individual calculations. They were suited merely for the computation of single sums involving addition, subtraction, multiplication or division: their use was limited to the solution of one-off numerical problems. A calculating machine, however, if one could be adapted specially to perform the Method of Differences, one of such a type would solve a very different kind of numerical problem, that of how to mass produce whole mathematical tables, quickly and efficiently, and with perfect accuracy. Such a machine might be arranged not only to calculate them but also to print them as well. Indeed these were Babbage's great insights. Perceiving the simplicity and facility of the Method of Differences and the arithmetic operation required to execute it, recognising that it was a very powerful and general technique, he realised that its principles could be very easily embodied in simple mechanical components. These insights led him, in 1821, directly to design and develop a Difference Engine, a machine in which all that was necessary to calculate all numerical tables was one based on the algorithms of the Method of Differences, one which only needed mechanisms for ADDITION repeated many times over. This was his conception of the purpose and nature of his invention. A clearer understanding therefore, of the Mathematics of the Method of Differences is essential if one is to comprehend fully Babbage's vision and gain a better picture of the mechanics of his creation, its operations, capabilities and limitations, and the manner in which it was expected to achieve its object.
By Babbage's time the Method of Differences had been in use for a long while and with much success for the manual calculation of mathematical and other types of numerical tables.[Compare the efforts made in 1801 of Prony and his team of mathematicians and calculators who constructed manually a very large set of tables known as the French Grand Tables using the Method of Differences.] It was a well-tried and firmly established technique of Numerical Analysis, and its theory was well understood. What made it an ideal principle for the automatic, mechanical computation of such tables was that, in its use, the same sequence of simple arithmetical operations is replicated over and over again. Hence a machine designed to imitate it only needed those mechanisms for repeating these same operations. In fact methods or algorithms for evaluating functions or solving equations by Recursion or Iteration, e.g. by the repetitive substitution of the approximate solution of an equation back into itself to obtain a better approximation, which terms are now applied to any repetitive technique, had been devised as early as the late 17th century, by Newton himself not long after he had discovered the Infinitesimal Calculus. But the Method of Differences itself did not become a clearly identifiable, separate branch of numerical mathematics until some time after Brook Taylor enunciated during the 18th century the famous theorem which bears his name (Taylor's Theorem), to which the Theory and Method of Finite Differences is firmly attached.
What is a "difference"? A "difference", written Df(x), is simply the difference between the values of a function taken at two different values of its variable, x. Df(x) = f(x1)-f(x2). A "differential" is much the same thing except that the difference between the two values of x used, x1 and x2, is reduced [gradually by a limiting process] by an infinitesimal (infinitely small) amount, df(x). A "differential" is thus an infinitesimal "difference". Conversely, a "difference" can be seen as a kind of finite "differential", one which uses an interval of a finite size instead of an infinitesimal. Because of this similarity, between the two calculi, of Differentials and of Differences, it will be found that they share many theorems in common.
The Method of Differences is thus a method of integrating "differences". Babbage's Difference Engine was a machine specially and specifically designed to perform this task as efficiently as possible.
The Method of Differences is a practical numerical technique. It can be used to calculate exactly the numerical values of any mathematical function that can be expressed as a simple polynomial (that is as the sum of a series of algebraic terms of the multiple powers of a variable quantity, x). The degree of a polynomial is defined as the value of the highest power of the variable x, that appears in the series. For instance:
f(x) = a0 + a1x + a2x2 + a3x3 is a polynomial with variable x and 3 coefficients a0, a1, a2 and a3. It is of the third degree.
In practice several applications which involve mathematical relationships, e.g. many equations of physics and astronomy, can be reduced to simple expressions containing only polynomials of a finite degree. Furthermore most common, everyday mathematical functions, for example Logarithms, Sines, Cosines etc., can themselves be expressed in the form of polynomials, which, although they consist of an infinite series, can be approximated, quite satisfactorily, to ones of a finite degree. Some more examples of polynomials:-
f(x)= 41 + x + x2 is a polynomial of degree 2.
Sin(x) = x + x3 /3! + x5 /5! ... is an infinite polynomial
Cos(x) = 1 - x2 /2! + x4 /4! ... is also an infinite polynomial.
What makes the Method of Differences a practical proposition for the interpolation of the numerical values of functions is a theorem which states that the nth difference of a polynomial of degree n is a constant, and that all its differences of a higher order are zero and can therefore be ignored. As a result, when one is dealing with the evaluation of polynomials, one need only work with a finite set of differences. As the Theory of Differences and the Differential Calculus are very closely interrelated, the significance of this theorem can be demonstrated quite easily by observing what happens to a simple polynomial when one is differentiated:-
e.g.
f(x) = x2 + x + 41 is a simple polynomial of degree 2
df(x)/dx = 2x + 1 is its first differential
d2f(x)/dx2 = 2 is its second differential
Note that in this example, the second differential is a constant having the value 2, and that all its other differentials of a higher order have a value of zero. As it is so with differentials, the same is also true of differences. Take the values of the function f(x) = x2 + x + 41 for fixed and equal intervals (equal to 1 in this instance) of values for D
Variable Table of the function
x x2+ x + 411 432 473 534 615 71
First Differences are obtained by subtracting adjacent values of the function in its table from one another; again, note that the values of variable x are still spaced at the same fixed and equal intervals: -
Variable Table of the function 1st Differences
x x2+ x + 41 D11 432 47 43 53 64 61 85 71 10
Second Differences are obtained by a similar process, by subtracting adjacent values of the First Differences from one another: -
variable table of the function 1st Diff 2nd Diff
x x2+ x + 41 Dl D21 43 4 22 47 6 23 53 8 24 61 105 71
It can be seen, from inspecting the above table, that the Second Differences for the function x2 + x + 41, when x is taken at fixed and equal intervals of 1, are constant and equal to 2; this observation will remain true no matter how far the table is extended.
The Mathematical Theory of Convergence defines the limits to which this approximation is possible. It should be noted, however, that this theory it was not particularly well understood in Babbage's time, but for the purpose of considering the mechanical features of the Difference Engine that need not concern us here.Now the feature that makes the Method of Differences special is that a complete reversal of the above procedure is allowed. Instead of starting with a table of values for a function distributed at a fixed interval and by repeated subtraction extracting the values of its various levels of differences, a process similar to Differentiation, one can do the complete opposite. One starts with the assumption that one is tabulating a polynomial function of the nth degree (2nd in this instance); consequently one may also assume that its nth difference is always a constant (2 in this case) and having been given or having ascertained starting values for the function itself and its n levels of differences one may calculate from these, by adding them together in the correct order repeatedly, a full table of values for the function at the fixed and specified interval, a process comparable to Integration. Thus given
f1 = 43
D1f1 = 4
D2fr = 2 and constant for all r
One can calculate that
f2 = f1 + D1f1 = 43 + 4 = 47
D1f2 = D1f1 + D2f1 = 4+2 = 6
and so on :-
variable table of the function 1st Diff 2nd Diff
x x2 + x + 41 D1 D21 43
2 47 4 2
3 53 6 2
4 61 8 2
5 71 10 2
6 83 12 2
7 97 14 2
. . . .
It will be found that this procedure can be used, in general, to generate in sequence, a full table of values for any function, for a given, fixed interval of values for x. In principle all one needs is the starting values of the function and its 1st to nth differences, and the assumption that the nth difference is a constant. Once these are specified then a complete table of values for any function and all its differences can be produced by iteration. If one is tabulating a polynomial function of the nth degree, then this will be found to be an exact process, otherwise it will be found that it produces a series of reasonably satisfactory approximations.
Notation for Differences and Various Important Relations:
A more formal notation was introduced above. A fuller explanation of it is given here:-
D is the Greek letter Delta; it stands for Finite Difference. DrU means the rth Finite Difference of a function U.
UZ represents the function to be tabulated; it is the zth value of this function in its table with a given, fixed interval. It could be written as D0Uz
D1Uz represents the zth value of the First Difference in the table; by definition it is equal to Uz+1-Uz
D2Uz represents the zth value of the Second Difference in the table; by definition it is equal to D1Uz+1 - D1Uz which is in turn equal to Uz+2-2Uz+1 +Uz.
DnUz represents the zth value in the table of the nth Difference. It is equal to Dn-1Uz+1 - Dn-1Uz
The important relation for the Method of Differences is this latter one
DnUz = Dn-1Uz+1 - Dn-1Uz
This can be re-arranged thus:-
Dn-1Uz+1 = Dn-1Uz + DnUz
which is a mathematical statement of the fundamental algorithm or basic unit of replication used by the Method of Differences. In words, it states that the next value in the table for the n-lth difference is equal to the current value of the n-lth difference plus the current value of the nth difference. All calculations performed using the Method may be represented by this one, general expression. In fact the uniformity of the mechanical parts used in DEl derives from the very reason that this expression is uniform with respect to all levels of differences.
Using the same notation, the theorem mentioned before can also be rewritten. The nth difference of a polynomial of degree n, which has already been noted is a constant, can be shown to be equal to
DnPn(x) = n!.an.hn
where Pn(x) is a polynomial of the nth degree with variable x; DnPn(x) is its nth difference; h is the interval of the table, an is the value of the coefficient of the term containing xn in the polynomial, and n! means n factorial or 1.2.3.. .n. This latter equation is a useful relation, one which should be remembered by those wishing to use the Method of Differences.
SEQUENCING
The order or sequence in which DEl was to perform its additions or integration of its various levels of differences is important as it affects which values for the differences are to be used as starting values, to be set up on each of the Difference Axes prior to the punching and calculation of a table. There are two general methods of sequencing:
Serial Sequencing:
For each Result Cycle [see Operating Cycles of DEl) Calculation on the Difference Engine can take place in the following order:
1st Difference adds to Result Axis: D0uz+1 = D0uz+ D1uz2nd Difference adds to 1st Difference: D1uz+1 = D1uz+ D2uz3rd Difference adds to 2nd Difference: D2uz+1 = D2uz+ D3uz4th Difference adds to 3rd Difference: D3uz+1 = D3uz+ D4uz5th Difference adds to 4th Difference: D4uz+1 = D4uz+ D5uz6th Difference adds to 5th Difference: D5uz+1 = D5uz+ D6uzIn which case the starting values will be these:
Table or Result Axis D0u0
1st Difference Axis D1u0
2nd Difference Axis D2u0
3rd Difference Axis D3u0
4th Difference Axis D4u0
5th Difference Axis D5u0
6th Difference Axis D6ur [Constant]
This method of sequencing requires 12 turns of the First Axis of the Engine for every result produced on the Table or Result Axis, 2 for each of the above additions. This was probably the method used by Babbage on his earlier models (ca 1823-1826) for DEl. Somewhat later, however, he discovered a much more efficient mode of sequencing, which he used in the design for all his subsequent versions of DEl:1st Difference Axis D1u0
2nd Difference Axis D2u0
3rd Difference Axis D3u0
4th Difference Axis D4u0
5th Difference Axis D5u0
6th Difference Axis D6ur [Constant]
Parallel Sequencing or 'Pipelining':
During each Calculation Sub-Cycle integration of differences takes place in two phases, each requiring two turns of the First Axis, i.e. a total of four turns of the first axis are needed for every result produced. During each phase three additions are performed in parallel:
Phase I
6th Difference adds to 5th Difference: D5uz+1 = D5uz+ D6uz
4th Difference adds to 3rd Difference: D3uz+1 = D3uz+ D4uz
2nd Difference adds to 1st Difference: D1uz+1 = D1uz+ D2uz
Phase II
5th Difference adds to 4th Difference: D4uz+1 = D4uz+ D5uz
3rd Difference adds to 2nd Difference: D2uz+1 = D2uz+ D3uz
1st Difference adds to Result Axis: D0uz+1 = D0uz+ D1uz
In this instance the starting values on the various Axes will be:-
Table or Result Axis D0u0 1st Difference Axis D1u-1
2nd Difference Axis D2u-1
3rd Difference Axis D3u-2
4th Difference Axis D4u-2
5th Difference Axis D5u-3
6th Difference Axis D6u-3 [Constant]
[NB the 6th Difference on DEl is always treated as a constant and thus its value is not affected by the Engine's sequencing]
Examples of the Method of Differences at work
A Table of the Squares of the Natural Numbers, f(x) = x2, may be produced by DEl using the following starting values:
U0 = 0, D1u0 = 1 and D2u0 = 2 (and constant).
From which, the following can be generated in sequence serially:
Ul = U0 + D1U0 = 0 + 1 = 1, D1u1 = D1u0 + D2u0 = 1 + 2 = 3.
U2 = U1 + D1u1 = 1 + 3 = 4, D1u2 = D1u1 + D2u1 = 3 + 2 = 5.
U3 = U2 + D1u2 = 4 + 5 = 9, D1u3 = D1u2 + D2u2 = 5 + 2 = 7.
etc.
The values for U0,U1,U2 U3 ... can be seen to be a sequence of the squares of the natural numbers 0, 1, 2, 3
A Table of the Cubes of the Natural Numbers, f(x) = x3, may similarly be constructed in sequence serially, given these starting values:
U0 = 0, D1u0 = 1, D2u0 = 6 and D3u0 = 6 (and constant)
Production of the remainder of the table is left as an exercise for the reader to perform.
Calculating Limit of Babbage' Difference Engine
Again using the same notation, the limit to the calculating power of Babbage's First Difference Engine can be stated quite simply in terms of the following expression:-
D7un = 0
This states that the 7th (and consequently any higher) difference for any function able to be tabulated by DEl will always equal to zero. DEl had 7 columns for calculating with, 6 of which each stored a 16 digit number representing the values of the 1st through to 6th differences, and the 7th column stored the results of the function being integrated; this latter was extended beyond the standard 16 to 20 digits. DEl could therefore have tabulated exactly the values for any function which could be effectively expressed as a simple polynomial of any degree up to and including the 6th power, and produce results up to 20 places of decimals. Only time effectively limited the number of iterations the machine could produce.
Negative NumbersDEl only worked with positive numbers; it could only add and store positive values. Nonetheless, the negative values of numbers could be represented and the process of subtraction performed through the use of an arithmetic artifice called Negative Complements
E.g. Suppose the value -137 needs to be used
Subtract 137 from 10,000,000,000,000,000 (i.e. 1016) The resulting number is 9,999,999,999,999,863This is called the Negative Complement of 137
If this latter number is added to any other number, e.g. 263, it will be seen that this has the effect of subtracting the original number, 137.
9,999,999,999,999,863 + 263 = l0,000,000,000,000,126
Drop the 1 in the highest place, ignore the zeros and what is left remaining is 126. 126 is, of course, equal to 263 minus 137, the required answer.
The use of Negative Complements introduced many unforeseen complications into the workings of DEl. Whilst in their simple application they seem to be equivalent to the use of negative numbers and behave more or less as one would expect, they are not fully representative of them in all their mathematical aspects. If one was not careful in or judicious with their application, mistakes could be made. For instance, the values of negative numbers could not be punched in their proper, canonical format by DEl [See Printing Part: Punching Department] that is as positive numbers with minus signs, nor could their values be passed properly via DEl's Intermediate and Oblique Axes arrangement: the required, additional leading 9s of such numbers could not be prefixed automatically by DEl during the transfer. [See Eating One's Own Tail]. It seems Babbage was not always fully aware of these difficulties, perhaps over trusting that it would probably all work out in the wash. As a result, some of the features he incorporated in DEl would not have worked at all or worked as fully as he expected.Taylor's Theorem and The Method of Differences
It was mentioned before that the Method of Differences was closely related to Taylor's Theorem. We shall now see how. Taylor's Theorem is usually stated in the following form:-
f(x+h) = f(x) + h.f'(x) + h2/2! . f''(x) + h3/3! . f'''(x) + ...
where
f(x) is any function of x, evaluated at the point x. h is any finite, fixed interval of x. f(x+h) is the function f(x) evaluated at the point at f'(x), f''(x), f'''(x), ... are the first, second, third, ... differentials of the function f(x) being evaluated.
The Theorem may be rewritten more concisely thus:-
f(x+h) = ehD.f(x)
where f(x), f(x+h) and h are as above
ex is the infinite series (1 + x + x2 /2! + x3 /3! + ...)
D. is the differential operator d./dx
thus D.y means dy/dx
Now First Differences may be defined thus:-
D1f(x) =f(x+h) - f(x) = (ehD. - 1) . f(x)
Similarly Second Differences may be defined thus:-
D2f(x) = (f(x+2h) - f(x+h)) -(f(x+h) - f(x))
= (f(x+2h) - 2.f(x+h) + f(x))
= (e2hD. -2ehD. + 1) . f(x)= (ehD. - 1)2 . f(x)
These formulae may be generalised thus:-
Dnf(x) = (ehD. - l)n . f(x)
This latter expression is known as Lagrange's [Brinkley's] Theorem. As such it would have been an extremely useful mathematical tool for the Superintendent of the Difference Engine to have kept at hand, had it gone into productive operation. It is easily remembered and would have provided him with a universal formula, by which all the other formulae required for calculating the starting values of the differences for any function, could have been worked out .
It is interesting to note that it appears in a footnote on one of the pages of the 'Preface' to the 'Memoirs of the Analytical Society', written by Babbage and Herschel when they were up at Cambridge together in 1813, some 8 years before Babbage beqan work on the Difference Engine.It may be proved by Induction
Its truth has been established for n = 1 and n = 2.
By definition:-
Dnfz = Dn-1fz+1 - Dn-1fz
Using Lagrange's Theorem this may be rewritten, thus:-
Dnfz = (ehD. - 1)n-1 .fz+1 - (ehD. - l)n-l.fz= (ehD. - 1) n-1 .(fz+1 - fz)
= (ehD. - 1)n-1 .(ehD. - 1).fz
= (ehD. - l)n . fz
Which is the desired form of the result.
Having established its truth for n=l and n=2, and demonstrated that the form of the expression for n may be derived from that of n-l, and having seen that they are of the same form, the truth of the theorem for all n results.
A more general expression for Lagrange's Theorem is thus
Dnfr = [ (ehD. - l)nerhD.] . f0
This gives an expression for the values of all differences relative to the base value of the table, f0.
The Practical Application of Lagrange's Theorem
Lagrange's Theorem can be used to calculate formulae for the starting values of any analytic function and its differences, for use when a table has to be generated using the Method of Differences. The following are for serial sequencing:-
a) Starting Value for the Function Itself (ehD. - 1)0 · f(x) = f(x)
b) Starting Value for First Difference D1f0 = (ehD. - 1)1 . f(x)
= (1 + hD. + h2D2./2! + h3D3./3! + ... -1).f(x)
= 0 + hf'(x) + h2/2! .f''(x) + h3/3!. f'''(x) ...
c) Starting Value for Second Difference D2f0 = (ehD. - 1)2 . f(x)
= (e2hD. - 2ehD. + 1) . f(x)
= (1 + 2hD. + 4h2 /2!D2. + 8h3/3!D3. + ... ) . f(x)
-2(1 + hD. + h2 /2!D2. + h3/3!D3. + ... ) . f(x)
+ f(x)
= 0 + 0 + 2h2f''(x) + 6h3f'''/3! f(x)
Similarly formulae for the starting values of the following differences can be determined by expanding Lagrange's Theorem. Intermediate steps are not shown.
d) Starting Value for Third Difference
D3f0 = (ehD. - 1)3 . f(x)= 0 + 0 + 0 + 2h3/3! . f'''(x) + 36h4/4!.f''''(x)
e) Starting Value for Fourth Difference
D4f0 = (ehD. - 1)4 . f(x)= 0 + 0 + 0 + 0 + 24h4/4!. f''''(x) + 240h5/5!. f'''''(x)
f) Starting Value for Fifth Difference
D5f0 = (ehD. - 1)5 . f(x)= 0+0+0+0+0 + 120h5/5!.f'''''(x) + 1800h6/6!.f''''''(x)
g) Starting Value for Sixth Difference
D6f0 = (ehD. - 1)6 . f(x)
= 0+0+0+0+0+0 + 720h6/6!.f''''''(x) + 15120h7/7!.f'''''''(x)
The Starting Values for 7th and Higher Differences are not necessary as D7f0 = 0 is the equation that defines the limit of the calculating power of Babbage's Difference Engine.
A table for the Coefficients used in the above expansions for the term hk/k!.fk(x) may be drawn up:-
Order of Difference
|
Coefficient Value for k
| |||||||
1
|
2
|
3
|
4
|
5
|
6
|
7
| ||
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
| |
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
| |
2
|
0
|
2
|
6
|
14
|
30
|
62
|
126
| |
3
|
0
|
0
|
6
|
36
|
150
|
540
|
1806
| |
4
|
0
|
0
|
0
|
24
|
240
|
1560
|
8400
| |
5
|
0
|
0
|
0
|
0
|
120
|
1800
|
16800
| |
6
|
0
|
0
|
0
|
0
|
0
|
720
|
15120
| |
7
|
0
|
0
|
0
|
0
|
0
|
0
|
5040
|
Value of Coefficient in Row r, Column c C [r,c] = r . (C [r,c-1] +C [r-1,c-1])
Example
Value of Coefficient in (Row 6, Column 7) = 6 . (720 + 1800) = 15120
Practical Example:
Suppose that a Table of the Natural Logarithms has to be tabulated, beginning with the value 1 and continuing up to 10, for intervals of 0.0001.
First construct a table of the differentials of the logarithmic function and their values for x=l
Value for x=1
The Function itself Ln(x) 0
First Differential x-l 1
Second Differential -l.x-2 -1
Third Differential 2.x-3 2
Fourth Differential -6.x-4 -6
Fifth Differential 24.x-5 24
Sixth Differential -120.x-6 -120
Seventh Differential 720.x-7 720
Now, using the formulae listed above, evaluate the starting differences, substituting h = 0.0001, the table's interval.
a) Starting Value for Function Itself
Ln(l) = 0.00000 00000 00000 00000 00000
b) Starting Value for 1st Difference
D1f0 = 0
+ (0.000l).l/1! + (0.000l)2.-l/2! + (0.000l)3.2/3!
+ (0.000l)4.-6/4! + (0.000l)5.24/5! + (0.0001)6.-120/6!
+ (0.0001)7.720/7!
= + 0.00000 00000 00000 00000 00000
+ 0.00010 00000 00000 00000 00000
- 0.00000 00050 00000 00000 00000
+ 0.00000 00000 00333 33333 33333
- 0.00000 00000 00000 02500 00000
+ 0.00000 00000 00000 00000 20000
- 0.00000 00000 00000 00000 00001 66666
+ 0.00000 00000 00000 00000 00000 00014 28571
= + 0.00009 99950 00333 30833 53332
c) Starting Value for 2nd Difference
D2f0 = 0 + 0
+ 2.(0.000l)2.-1/2! + 6.(0.000l)3.2/3!
+ 14.(0.0001)4.-6/4! + 30.(0.000l)5.24/5!
+ 62.(0.0001)6.-l20/6! + l20.(0.000l)7.720/7!
= + 0.00000 00000 00000 00000 00000
+ 0.00000 00000 00000 00000 00000
- 0.00000 00100 00000 00000 00000
+ 0.00000 00000 02000 00000 00000
- 0.00000 00000 00000 35000 00000
+ 0.00000 00000 00000 00006 00000
- 0.00000 00000 00000 00000 00103 33333 33333
+ 0.00000 00000 00000 00000 00000 01714 28571
= 0.00000 00099 98000 34994 00103 31619 04762
Without showing intermediate calculations, using the same method, the starting values for the higher differences can be shown to be equal to the following
D3f0 = + 0.00000 00000 01999 10029 99100
D4f0 = - 0.00000 00000 00000 59952 02599
D5f0 = + 0.00000 00000 00000 00023 97002
D6f0 = - 0.00000 00000 00000 00000 01198
A Table of Common Logarithms (Base 10), over the same range of values, with the same interval, may be obtained by multiplying each of the above starting values for the various levels of differences by
l/Ln(10) = + 0.43429 44819 03251 82765 11289
before commencing calculation of the table.
Formulae for the Starting Values of Differences for Parallel Sequencing
Of course, it has been shown that in his later versions of DEl Babbage used parallel sequencing. Without showing intermediate steps, a similar table of the coefficients in the expansions of the formulae for calculating suitable starting values for the differences of any analytic function can be shown to be equal to the following:-
A table for the Coefficients for the term hk/k!.fk(x) :-
Values of k
0 1 2 3 4 5 6
D0f0 1 0 0 0 0 0 0
D1f-1 0 1 -1 1 -1 1 -1
D2f-1 0 0 2 0 2 0 2
D3f-2 0 0 0 6 -12 30 -60
D4f-2 0 0 0 0 24 0 120
D5f-3 0 0 0 0 0 120 -360
D6f-3 0 0 0 0 0 0 720
Using the same example as above, that of the Table of Natural Logarithms, without showing intermediate calculations, the starting values for the various levels of differences for parallel sequencing can be shown to be equal to:-
Table or Result D0f0 = + 0.00000 00000 00000 00000 00000
1st Difference Axis D1f-1 = + 0.00010 00050 00333 35833 53335
2nd Difference Axis D2f-1 = - 0.00000 00100 00000 05000 00003
3rd Difference Axis D3f-2 = + 0.00000 00000 02000 30006 00100
4th Difference Axis D4f-2 = - 0.00000 00000 00000 60000 00200
5th Difference Axis D5f-3 = + 0.00000 00000 00000 00024 00600
6th Difference Axis D6fr = - 0.00000 00000 00000 00000 01200
Again a table of Common Logarithms (base 10) may be obtained by multiplying these differences by the factor given above.
Variations on the Standard Method of Differences
Once DEl has been set with starting values for differences on its 1st to 6th Difference Axes and also with a starting value for the function to be tabulated on its Result Axis, all that is necessary for one to do is turn the Driving Handle and the machine will do the rest.
For every Result Cycle (of either 6 or 10 turns of the First Axis, 4 of which form the Calculation Sub-Cycle; See Operating Cycles of DEl) DEl's Calculating Part
will first
Add the 6th Difference to the 5th
Add the 4th Difference to the 3rd
Add the 2nd Difference to the 1st
and then
Add the 5th Difference to the 4th
Add the 3rd Difference to the 2nd
Add the 1st Difference to the Result
once each. It has already been shown that this can be summarised by the following, a mathematical expression which describes the fundamental algorithm or basic unit of replication used by DEl in its calculations by the Standard Method of Differences:-
DnUn+1= DnUn + Dn+1Un
DEl, however, through the incorporation of some additional features or changes in its node of operation, is capable of a number of variations over and above the theme of the Standard Method of Differences. It can play more than one tune. These variations increase its flexibility and the range of types of calculation it is able to perform:
Variation 1: Manual Adjustment of Values held on Difference Axes
At certain moments during the Calculation Sub-Cycle DEl's Figure Wheels are not locked tight, but are held loosely and are capable of being turned by hand. Indeed this is necessary for one to be able to set up the starting values on them in the first place, before a new table commences. But it also means that, during operation of the Engine, whilst it is punching and calculating results, the digits on the Figure Wheels could also be adjusted at these times by hand by the operator. For instance, it is possible, in cases say, where the 6th Difference is not a true constant, to adjust its value at frequent intervals according to some regular rule as calculation on the Engine proceeds, thereby reflecting its variable nature. One of the uses which Babbage intended for the Alarm Bell System, which issues an audible warning whenever a previously set value has been reached by an Axis, was perhaps to remind the operator at what moments during the processing of a table when this was to be done. [See Calculating Part: Alarm System].
Variation 2: Addition of Multiple Values of Certain Differences
DEl's Calculating Part has a Barrels Department whose job it was to ensure that the sequence of operations was carried out in the set order. These Barrels have removable studs set around their curved surfaces which put various parts into and out of gear with one another, and they are themselves driven by wheels with removable teeth. [See Calculating Part: Barrels Department]. Furthermore in the Calculating Part's Transmission Gearing Department there are various Sector Wheels which can be exchanged for others which have a different number of teeth, or they can be repositioned so as to act earlier or later in the Cycle, if that is so desired. If these are set in their regular positions the machine performs the Standard Method of Differences. They, however, can be set to be in a variety of different positions, each of which results in a different sequence of operations taking place. For example, it is possible to adjust the machinery before the commencement of the calculation and punching of a table so as to arrange, during every Calculation Sub-Cycle, that the 3rd Difference will be added to the 2nd Difference 2, 3, 4 or more times every one time the 2nd Difference is added to the 1st Difference. There are many options open to the user of DEl regarding this. This mode of integration of differences produces a whole variety of different results and greatly extends the mathematical possibilities of DEl. In these cases the unit of replication in DEl can be summarised by the following expression:
DnUn+1 = DnUn+ a. Dn+1Un
where a is a whole number constant, but which may be different for different levels of differences but fixed for the calculation of a particular table.
Variation 3: "Eating its own Tail"
Certain elementary transcendental functions, viz, the circular and hyperbolic functions: sine, cosine, hyperbolic sine and hyperbolic cosine, each share a similar mathematical property which can be used to advantage when calculating tables of their values on Babbages Difference Engine. Namely, it is possible when compiling such tables, as each result is produced, for its value to be fed back automatically into the Engine again to participate in the generation of the value of the next. The procedure and mechanisms Babbage invented to carry this out he affectionately called Apparatus for Eating Its Own Tail" . It involved the use of a set of Intermediate and Oblique Axes attached to the front side of the Calculating Part of the Engine [see section on same].
How could this be so?
Before it has been argued that the Differential Calculus and the Calculus of Differences share many theorems and results in common. See what happens when the
hyperbolic sine function is differentiated.
f(x) = Sinh(x)
f'(x) = Cosh(x) 1st differential
f''(x) = Sinh(x) 2nd differential
Thus f''(x) = f(x)
In words: the value of the second differential is equal to the function itself. A very similar result can be shown to hold for differences. Consider three adjacent values in a table of hyperbolic sines spaced at an interval equal to k:
f0 Sinh(x-k)
f1 Sinh(x)
f2 Sinh(x+k)
Its First Differences are:
D1f0 = Sinh(x) - Sinh(x-k)
D1f1 = Sinh(x+k) - Sinh(x)
Its Second Differences are
D1f2 = Sinh(x+k) - 2.Sinh(x) + Sinh(x-k)
= Sinh(x)Cosh(x) + Cosh(x)Sinh(k) - 2.Sinh(x) + Sinh(x)Cosh(k) - Cosh(x)Sinh(k)
= 2.Sinh(x)Cosh(x) - 2.Sinh(x)
= 2.(Cosh(k)-l).Sinh(x)
That is to say the value of the second difference of the hyperbolic sine function is equal. to the function itself multiplied by a constant factor.
Consider the constant factor, 2.(Cosh(k)-1)
Cosh(k) = 1 +k2/2! +k4/4! + k6/6! ...
Therefore
2.(Cosh(k)-l) =
Which approximates to, if k is very small:
k2 + k4/12
the second term of which in the above series can be ignored, if k is extremely small.
Thus the second d ifferences of the hyperbolic sine function
D2f0 = k2.Sinh(x) = k2.f1
In words: a very accurate value for the second difference can be obtained by taking the current value of the result and multiplying it by the square of the interval. On the Difference Engine, as each result is calculated, the above formula suggests that its value can be used to provide directly the next value for the second difference to be used in the iteration.
But this supposes Multiplication. Multiplication of two numbers together, of course was not possible on DEl: it only had mechanisms for Addition. But was Addition DE1's sole arithmetic processing capability? No! Babbage invented supplementary mechanisms, viz, the Intermediate and Oblique Axes, whereby DE1 could: transfer the values of numbers stepped up or down by powers of 10 from one set of Difference Axes onto others. The stepping of a number up or downby powers of 10 is, of course, equivalent to multiplying or dividing by a power of 10. With this limited multiplication capability DEl was able to be employed usefully in the calculation of tables of the elementary transcendental functions.
For DE1 to work with this limited multiplication capability, when calculating a table of hyperbolic sines, the tables interval, k, would have to be suitably selected such that k2 was both a power of 10, as well as being small. With k = 0.01 k2 = 0.000001 (and an error in the factor of the order of k4/12 or 0.0000000000000833). Second differences for a table of the values of the hyperbolic sine function spaced at an interval of 0.001 could therefore be calculated and utilised by stepping each result, as it was obtained, down by 6 decimal places.
Thus as D2fr = k2.fr
if fr= 0.5 and k = 0.00l
then D2fr = 0.0000005
In words, the process is: take the current value of the result, step it down 6 decimal places and this gives one the next value of the 2nd difference to be used in the iteration sequence. No other formal multiplication was required. As long as the interval in the table was small it would take the errors a long time to accumulate before they would begin to affect the significant values of the result.
In actual fact, however, Babbages DEl, unlike his later series of Analytical Engines had no Reduction to Zero mechanisms. Its Registers or Axes could not be cleared of their results automatically and reduced to zero. The above algorithm, albeit that it seems to work, implies this, that the 2nd Difference would be cleared of its current value before being substituted with the new one. As that was not possible on DEl a slightly modified algorithm was required.
Of course
fr+1 = fr + D1fr by definition of what differences are.
But for the hyperbolic sine function
D2fr = k2. fr+1
and D2fr+1 = k2fr+2 = k2. ( fr+1 + D1fr+1)
Therefore D2fr+1 = k2 .( fr+1 + D1fr+1 ) = D2fr + k2.D1fr+1
In words: the next value for the second difference is obtained by adding to the current value of the second difference at the same time an amount equal to that of the first difference added to the result divided by the square of the interval of the table (i.e. stepped down appropriately). The Oblique and Intermediate Axes arrangement worked on DEl, not by transferring the absolute value each axis held but by transferring the amount by which each had been incremented and all the movements forced on it by the immediately adjacent and higher difference axis.
Initial values for the differences and sequencing was as follows
Initial Values:
Result Axis = f0
1st Difference Axis = D1f-1
2nd Difference Axis = D2f-1
All other Difference Axes = 0
Sequence of operations:
1. D1f0 = D1f-1 + D2f-1
2. f1 = f0 + D1f0
and simultaneously
D2f0 = D2f-1 + k2.D1f0
1. & 2. can repeat ad infinitum.
Similar functions or algorithms could be worked out for the hyperbolic cosine and the cuircular sine and cosine. But it would be discovered that the latter two functions negative values would have to be stepped down and transferred from the Result Axis onto the 2nd Difference for the formulae to work. It might be supposed that this could be done using negative complements [see before]. Not so! DE1 had no means of concatenating the extra 9s required to the 'head' of the transferred number automatically after the stepping down process had taken place. Therefore negative complemetns on DE1 would not allow this method to be used. Tables for Circular Sines and Cosines would have had to be calculated using the normal Method of Differences. Babbage, it appears, was not aware of the difficulties raised in this variation.
A Note of Warning
Having now presented a theoretical picture of the mathematical nature and purpose of the Difference Engine and some of Babbage's intentions for it, all that there remains is but a note of warning to would-be interpreters of the Engine, perhaps even, in retrospect, for Babbage himself, who did not always heed this. In translating mathematical methods to machinery, not everything that is expressed in the mathematical formulae etc. is necessarily able to be replicated in an analogous form in a machine. One cannot always assume that the Difference Engine embodies everything that the formulae for the Method of Differences contain. A detailed study of its actual mechanical operations are necessary to comprehend any in-built limitations that may manifest themselves during its use. And machines themselves have linkages not present in the mathematics. Of course, it is probable, that Babbage liked to think that his Calculating Machines were the full mechanical realisation of the mathematics involved. This way of thinking was more than likely a constructive way for him to conceive their structure and possibilities in the first place, and was useful and very suggestive for ideas. Nonetheless, machinery cannot always be a full and true analogy for mathematics, and one can fall into grave errors by making this assumption. Mathematics has more freedom and is more flexible. Babbage was guilty of making this mistake as well. Where significant differences from what is expected of the mathematics of a situation manifest themselves, these will be pointed out to the reader, particularly where Babbage himself fell into the same trap.
References
Brinkley's Theorem
Investigation of the general Term of an important Series in the inverse Method of finite Differences.
By the Rev. John Brinkley, D. D. F.R.S. and Andrews Professor of Astronomy in the University of Dublin.
Royal Society (London) (1807). Philosophical Transactions of the Royal Society of London: Giving Some Accounts of the Present Undertakings, Studies, and Labours, of the Ingenious, in Many Considerable Parts of the World. pp. 114–.
On Differences and Differentials of Functions of Zero
William R. Hamilton
The Transactions of the Royal Irish Academy, Vol. 17, (1831), pp. 235-236
Published by: Royal Irish Academy
Article Stable URL: http://www.jstor.org/stable/30078790
Alexander John Thompson (1933). Logarithmetica Britannica: Being a Standard Table of Logarithms to Twenty Decimal Places. CUP Archive. pp. 13–. ISBN 978-1-00-140689-3.
Lagrange Formula
Les Logarithmes de Briggs (1995)
www.univ-irem.fr/reperes/articles/21_article_145.pdf
Denis Roegel (2010) The great logarithmic and trigonometric tables of the French Cadastre, a preliminary investigation Page 63
No comments:
Post a Comment