Difference engine

The Difference Engine was an automatic, mechanical calculator designed to tabulate polynomial functions. Both logarithmic and trigonometric functions can be approximated by polynomials, so a difference engine can compute many useful sets of numbers.

1 History
2 Operation
- 2.1 Timing
3 Method of differences
4 Initial values and Pipeline Method
- 4.1 Use of derivatives
5 Trivia
6 References
7 Further reading
8 See also
9 External links

History

Closeup of the London Science Museum's difference engine.

Per Georg Scheutz's third Difference engine

J. H. Müller, an engineer in the Hessian army conceived the idea in a book published in 1786, but failed to find funding to progress this further.^[1]

In 1822, Charles Babbage proposed the use of such a machine in a paper to the Royal Astronomical Society on 14 June entitled "Note on the application of machinery to the computation of astronomical and mathematical tables" ^[2]. This machine used the decimal number system and was powered by cranking a handle. The British government initially financed the project, but withdrew funding when Babbage repeatedly asked for more money whilst making no apparent progress on building the machine. Babbage went on to design his much more general analytical engine but later produced an improved difference engine design (his "Difference Engine No. 2") between 1847 and 1849. Inspired by Babbage's difference engine plans, Per Georg Scheutz built several difference engines from 1855 onwards; one was sold to the British government in 1859. Martin Wiberg improved Scheutz's construction but used his device only for producing and publishing printed logarithmic tables.

Based on Babbage's original plans, the London Science Museum constructed a working Difference Engine No. 2 from 1989 to 1991, under Doron Swade, the then Curator of Computing. This was to celebrate the 200th anniversary of Babbage's birth. In 2000, the printer which Babbage originally designed for the difference engine was also completed. The conversion of the original design drawings into drawings suitable for engineering manufacturers' use revealed some minor errors in Babbage's design, which had to be corrected. Once completed, both the engine and its printer worked flawlessly, and still do. The difference engine and printer were constructed to tolerances achievable with 19th century technology, resolving a long-standing debate whether Babbage's design would actually have worked. (One of the reasons formerly advanced for the non-completion of Babbage's engines had been that engineering methods were insufficiently developed in the Victorian era.) In addition to funding the construction of the output mechanism for the Science Museum's Difference Engine No. 2, Nathan Myhrvold commissioned the construction of a second complete Difference Engine No. 2, which will be on exhibit at the Computer History Museum in Mountain View, California from 10 May 2008 through April 2009. ^[3]

Operation

The difference engine consists of a number of columns, numbered from 1 to N. Each column is able to store one decimal number. The only operation the engine can do is add the value of a column n + 1 to column n to produce the new value of n. Column N can only store a constant, column 1 displays (and possibly prints) the value of the calculation on the current iteration. Subtraction can be accomplished through the use of the Method of complements, or ten's complement arithmetic, which works in exactly the same manner that modern computers perform subtraction, known as two's complement.

The engine is programmed by setting initial values to the columns. Column 1 is set to the value of the polynomial at the start of computation. Column 2 is set to a value derived from the first and higher derivatives of the polynomial at the same value of X. Each of the columns from 3 to N is set to a value derived from the $(n-1)$ first and higher derivatives of the polynomial.

Timing

In the Babbage design, each iteration creates a new result, and is accomplished in four steps corresponding to four complete turns of the handle shown at the far right in the picture below. The four steps are:

Step 1. All even numbered columns (2,4,6,8) are added to all odd numbered columns (1,3,5,7) simultaneously. An interior sweep arm turns each even column to cause whatever number is on each wheel to count down to zero. As a wheel turns to zero, it transfers its value to a sector gear located between the odd/even columns. These values are transferred to the odd column causing them to count up. Any odd column value that passes from "9" to "0" activates a carry lever.

Step 2. Carry propagation is accomplished by a set of spiral arms in the back that poll the carry levers in a helical manner so that a carry at any level can increment the wheel above by one. That can create a carry, which is why the arms move in a spiral. At the same time, the sector gears are returned to their original position, which causes them to increment the even column wheels back to their original values. The sector gears are double-high on one side so they can be lifted to disengage from the odd column wheels while they still remain in contact with the even column wheels.

Step 3. This is like Step 1, except it is odd columns (3,5,7) added to even columns (2,4,6), and column one has its values transferred by a sector gear to the print mechanism on the left end of the engine. Any even column value that passes from "9" to "0" activates a carry lever.

Step 4. This is like Step 2, but for doing carries on even columns, and returning odd columns to their original values.

If you enlarge the picture above, you can see some of the number wheels and the sector gears between columns. The sector gears on the left show the double-high teeth very clearly. The sector gears on the middle-right are facing the back side of the engine, but the single-high teeth are clearly visible. Notice how the wheels are mirrored, with counting up from left-to-right, or counting down from left-to-right. Also notice the metal tab between "6" and "7". That tab trips the carry lever in the back when "9" passes to "0" in the front during the add steps (Step 1 and Step 3).

Method of differences

The London Science Museum's difference engine, built from Babbage's design. The design has the same precision on all columns, but when calculating converging polynomials, the precision on the higher-order columns could be lower. The Engine is not a replica, there never was one built during Babbage's lifetime, therefore this is the first one, the original.

As the differential engine cannot do multiplication, it is unable to calculate the value of a polynomial. However, if the initial value of the polynomial (and of its finite differences) is calculated by some means for some value of X, the difference engine can calculate any number of nearby values, using the method generally known as the method of finite differences.

The principle of a difference engine is Newton's method of divided differences. It may be illustrated with a small example. Consider the quadratic polynomial

p(x) = 2x² − 3x + 2

and suppose we want to tabulate the values p(0), p(0.1), p(0.2), p(0.3), p(0.4) etc. The table below is constructed as follows: the second column contains the values of the polynomial, the third column contains the differences of the two left neighbors in the second column, and the fourth column contains the differences of the two neighbors in the third column:

x	p(x) = 2x² − 3x + 2	diff1(x) = ( p(x+1) - p(x) )	diff2(x) = ( diff1(x+1) - diff1(x) )
0.00	2.00	-0.28	0.04
0.10	1.72	-0.24	0.04
0.20	1.48	-0.20	0.04
0.30	1.28	-0.16
0.40	1.12

Notice how the values in the fourth column are constant. This is no mere coincidence. In fact, if you start with any polynomial of degree n, the column number n + 1 will always be constant. This crucial fact makes the method work, as we will see next.

We constructed this table from the left to the right, but now we can continue it from the right to the left down a diagonal in order to compute more values of our polynomial.

To calculate p(0.5) we use the values from the lowest diagonal. We start with the third column constant value of 0.04 and copy it down the column. Then we continue the second column by adding 0.04 to -0.16 to get -0.12. Next we continue the first column by taking its previous value, 1.12 and adding the -0.12 from the second column. Thus p(0.5) is 1.12-0.12 = 1.0. In order to compute p(0.6), we iterate the same algorithm on the p(0.5) values: take 0.04 from the third column, add that from the second column's value -0.12 to get -0.08, then add that from the first column's value 1.0 to get 0.92, which is p(0.6).

This process may be continued ad infinitum. The values of the polynomial are produced without ever having to multiply. A difference engine only needs to be able to add. From one loop to the next, it needs to store 2 numbers in our case (the last elements in the first and second columns); if we wanted to tabulate polynomials of degree n, we'd need enough storage to hold n numbers.

Babbage's difference engine No. 2, finally built in 1991, could hold 7 numbers of 31 decimal digits each and could thus tabulate 7th degree polynomials to that precision. The best machines from Scheutz were able to store 4 numbers with 15 digits each.

Initial values and Pipeline Method

The Babbage Difference Engine is designed to calculate a new result using a "pipeline method" which requires an initial setup involving "staggered steps". To demonstrate these concepts, consider the following polymomial:

   R = X³ -2X² + 1

Compute the first N+1 results (R) where N is the highest exponent in the polynomial, starting at any value of X. In this case, we'll start at X = 1 and calculate four consecutive results:

X     Result    Diff1    Diff2   Diff3
1       0         1        8       6
2       1         9       14       6
3      10        23
4      33

This table also shows the differences between consecutive values in a column written into the column to its right. Thus, Diff1(n) = Result(n+1) - Result(n), Diff2(n) = Diff1(n+1) - Diff1(n), and Diff3(n) = Diff2(n+1) - Diff2(n). For a third-order polymonial, Diff3 is a constant, which can be propagated down that column.

The initial values for a pipeline are Result(2), Diff1(2), Diff2(1), and Diff3(1). These values are highlighted in bold in the table above. Aligning them in a straight line, and applying a four-step Babbage cycle:

Step  Result    Diff1    Diff2   Diff3
         1        9        8       6       Initial values for this cycle.
  1    c 0        0      c 4       0       Add Diff1 to Result, Diff3 to Diff2, c=carry
  2     10        9       14       6       Propagate carries, restore Diff1 & Diff3.
  3      0     c 13        0       6       Send Result to printer, add Diff2 to Diff1
  4     10       23       14       6       Propagate carry, restore Result & Diff2

Several carries can occur in any add, but in this example, only one occurs for any number. In Step 1, 9+1 = 0 with a carry, and, 6+8 = 4 with a carry. Step 2 increments the next higher digit for each carry, yielding 10 and 14. Note that applying a carry can cause another carry on the incremented value, as when 9 becomes 0 with a carry. That's why the carry mechanism is a spiral, to pass generated carries up to higher levels. The carry for Diff1 on Step 3 is from 4+9 = 3. The 1 from 14 becomes the 1 in 13. When step 4 occurs, the carry is applied to the 1, and it becomes 2, so 13 becomes 23.

At the end of the four steps, we have a new set of staggered steps, which are shown in italic in the calculation table. Repeat the four steps beginning with 10, 23, 14, 6 replacing 1, 9, 8, 6. You'll get: 33, 43, 20, 6, with 33 and 43 on the X=4 level, 20 and 6 on X=3 level. Every repetition of these four steps obtains and prints another Result.

Use of derivatives

A more general and in many cases more useful method is to calculate the initial values from the values of the derivatives of the function at the start of computation. Each value is thus represented as power series of the different derivates. The constants of the series can be calculated by first expressing a function as a Taylor series i.e. a sum of its derivatives. Setting 0 as the start of computation we get the Maclaurin series

$\sum_{n=0}^{\infin} \frac{f^{(n)}(0)}{n!} (x)^{n}.$

Calculating the values numerically, we get the following serial representations for the initial values of the columns:

Let $f , f' , f'' , f''' , f'''' ...$ be the values of the function and its derivatives at the start of computation

Col $1_0$ = $f$
Col $2_0$ = $f' + 1/2f'' + 1/6f''' + 1/24f'''' + 1/120f''''' + ...$
Col $3_0$ = $f'' + f''' + 14/24f'''' + 23/120f''''' + ...$
Col $4_0$ = $f''' + 36/24f'''' + 171/120f''''' + ...$
Col $5_0$ = $f'''' + 378/120f''''' + ...$

Trivia

A kind of robot that calls itself "the Difference Engine" appears in the issues 28 through 30 of the Marvel Comic book Runaways, in a storyline set in 1907 New York City.

References

↑ Swedin, E.G. & Ferro, D.L. (2005). "Computers: The Life Story of a Technology". Greenwood Press, Westport, CT. Retrieved on 2007-11-17.
↑ "Charles Babbage". The MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland (1998). Retrieved on 2006-06-14.
↑ "Computer History Museum unboxes a Babbage difference engine". Retrieved on 2008-04-28.

Difference engine

Contents