Difference engine

For the novel by William Gibson and Bruce Sterling, see The Difference Engine.
The London Science Museum's difference engine, the first one actually built from Babbage's design. The design has the same precision on all columns, but when calculating polynomials, the precision on the higher-order columns could be lower.

A difference engine is an automatic mechanical calculator designed to tabulate polynomial functions. The name derives from the method of divided differences, a way to interpolate or tabulate functions by using a small set of polynomial coefficients. Most mathematical functions commonly used by engineers, scientists and navigators, including logarithmic and trigonometric functions, can be approximated by polynomials, so a difference engine can compute many useful tables of numbers.

The historical difficulty in producing error-free tables by teams of mathematicians and human "computers" spurred Charles Babbage's desire to build a mechanism to automate the process. It is considered to be the world's first computer.

History

Wikisource has original text related to this article:
Closeup of the London Science Museum's difference engine showing 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).
Per Georg Scheutz's third difference engine

J. H. Müller, an engineer in the Hessian army, conceived of the idea of a difference machine. This was described in a book published in 1786, but Müller was unable to obtain funding to progress with the idea.[1][2][3]

On 14 June 1822, Charles Babbage proposed the use of such a machine in a paper to the Royal Astronomical Society, entitled "Note on the application of machinery to the computation of astronomical and mathematical tables".[4] This machine used the decimal number system and was powered by cranking a handle. The British government was interested, since producing tables was time-consuming and expensive and they hoped the difference engine would make the task more economical.[5]

In 1823, the British government gave Babbage £1700 to start work on the project. Although Babbage's design was feasible, the metalworking techniques of the era could not economically make parts in the precision and quantity required. Thus the implementation proved to be much more expensive and doubtful of success than the government's initial bargain. By the time the government abandoned the project in 1842, Babbage had received and spent over £17,000 on development, which still fell short of achieving a working engine. The government valued only the machine's output (economically produced tables), not the development (at unknown and unpredictable cost to complete) of the machine itself. Babbage did not, or was unwilling to, recognize that predicament.[5] Meanwhile, Babbage's attention had moved on to developing an analytical engine, further undermining the government’s confidence in the eventual success of the difference engine. By improving the concept as an analytical engine, Babbage had made the difference engine concept obsolete, and the project to implement it an utter failure in the view of the government.[5]

Babbage went on to design his much more general analytical engine, but later produced an improved "Difference Engine No. 2" design, between 1847 and 1849. Babbage was able to take advantage of ideas developed for the analytical engine to make the new difference engine calculate more quickly while using fewer parts.[6] Inspired by Babbage's difference engine plans, Per Georg Scheutz built several difference engines from 1855 onwards, one of which 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.[7]

Construction of two working No. 2 difference engines

During the 1980s, Allan G. Bromley, an associate professor at the University of Sydney, Australia, studied Babbage's original drawings for the Difference and Analytical Engines at the Science Museum library in London.[8] This work led the Science Museum to construct 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 2001. 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 (possibly introduced as a protection in case the plans were stolen),[9] 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 as to 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.)

The printer's primary purpose is to produce stereotype plates for use in printing presses, which it does by pressing type into soft plaster to create a flong. Babbage intended that the Engine's results be conveyed directly to mass printing, having recognized that many errors in previous tables were not the result of human calculating mistakes but from error in the manual typesetting process.[5] The printer's paper output is mainly a means of checking the Engine's performance.

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 was on exhibit at the Computer History Museum in Mountain View, California until 31 January 2016.[10][11][12] [13]

Operation

The Mountain View machine in action

The difference engine consists of a number of columns, numbered from 1 to N. The machine is able to store one decimal number in each column. The machine can only 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.

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, one iteration (i.e., one full set of addition and carry operations) happens for each rotation of the main shaft. Odd and even columns alternately perform an addition in one cycle. The sequence of operations for column n is thus:

  1. Count up, receiving the value from column n+1 (Addition step)
  2. Perform carry propagation on the counted up value
  3. Count down to zero, adding to column n-1
  4. Reset the counted-down value to its original value

Steps 1,2,3,4 occur for every odd column, while steps 3,4,1,2 occur for every even column.

While Babbage's original design placed the crank directly on the main shaft, it was later realized that the force required to crank the machine would have been too great for a human to handle comfortably. Therefore, the two models that were built incorporate a 4:1 reduction gear at the crank, and four revolutions of the crank are required to perform one full cycle.

Steps

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:

Subtraction

The engine represents negative numbers as ten's complements. Subtraction amounts to addition of a negative number. This works in the same manner that modern computers perform subtraction, known as two's complement.

Method of differences

Fully operational difference engine at the Computer History Museum in Mountain View, California

The principle of a difference engine is Newton's method of divided differences. If the initial value of a 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. For example, consider the quadratic polynomial

p(x) = 2x^2 - 3x + 2 \,

with the goal of tabulating the values p(0), p(1), p(2), p(3), p(4), and so forth. 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:

xp(x) = 2x2 − 3x + 2diff1(x) = ( p(x + 1) − p(x) )diff2(x) = ( diff1(x + 1) − diff1(x) )
02−14
1134
2474
31111
422

The numbers in the third values-column are constant. In fact, by starting with any polynomial of degree n, the column number n + 1 will always be constant. This is the crucial fact behind the success of the method.

This table was built from left to right, but it is possible to continue building it from right to left down a diagonal in order to compute more values. To calculate p(5) use the values from the lowest diagonal. Start with the fourth column constant value of 4 and copy it down the column. Then continue the third column by adding 4 to 11 to get 15. Next continue the second column by taking its previous value, 22 and adding the 15 from the third column. Thus p(5) is 22 + 15 = 37. In order to compute p(6), we iterate the same algorithm on the p(5) values: take 4 from the fourth column, add that to the third column's value 15 to get 19, then add that to the second column's value 37 to get 56, which is p(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 this example (the last elements in the first and second columns). To tabulate polynomials of degree n, one needs sufficient storage to hold n numbers.

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

Initial values

The initial values of columns can be calculated by first manually calculating N consecutive values of the function and by backtracking, i.e. calculating the required differences.

Col 1_0 gets the value of the function at the start of computation f(0). Col 2_0 is the difference between f(1) and f(0)…[14]

If the function to be calculated is a polynomial function, expressed as

f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 \,

the initial values can be calculated directly from the constant coefficients a0, a1,a2, …, an without calculating any data points. The initial values are thus:

Use of derivatives

Many commonly used functions are analytic functions, which can be expressed as power series, for example as a Taylor series. The initial values can be calculated to any degree of accuracy; if done correctly the engine will give exact results for first N steps. After that, the engine will only give an approximation of the function.

The Taylor series expresses the function as a sum obtained from its derivatives at one point. For many functions the higher derivatives are trivial to obtain; for instance, the sine function at 0 has values of 0 or \pm1 for all derivatives. Setting 0 as the start of computation we get the simplified Maclaurin series

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

The same method of calculating the initial values from the coefficients can be used as for polynomial functions. The polynomial constant coefficients will now have the value

a_n \equiv \frac{f^{(n)}(0)}{n!}

Curve fitting

The problem with the methods described above is that errors will accumulate and the series will tend to diverge from the true function. A solution which guarantees a constant maximum error is to use curve fitting. A minimum of N values are calculated evenly spaced along the range of the desired calculations. Using a curve fitting technique like Gaussian reduction an N-1th degree polynomial interpolation of the function is found.[14] With the optimized polynomial, the initial values can be calculated as above.

See also

References

  1. ↑ Johann Helfrich von Müller, Beschreibung seiner neu erfundenen Rechenmachine, nach ihrer Gestalt, ihrem Gebrauch und Nutzen [Description of his newly invented calculating machine, according to its form, its use and benefit] (Frankfurt and Mainz, Germany: Varrentrapp Sohn & Wenner, 1786); pages 48-50. The following Web site (in German) contains detailed photos of Müller's calculator as well as a transcription of Müller's booklet, Beschreibung …: http://www.fbi.fh-darmstadt.de/fileadmin/vmi/darmstadt/objekte/rechenmaschinen/mueller/index.htm . An animated simulation of Müller's machine in operation is available on this Web site (in German): http://www.fbi.fh-darmstadt.de/fileadmin/vmi/darmstadt/objekte/rechenmaschinen/mueller/simulation/index.htm .
  2. ↑ Michael Lindgren (Craig G. McKay, trans.), Glory and Failure: The Difference Engines of Johann Müller, Charles Babbage, and Georg and Edvard Scheutz (Cambridge, Massachusetts: MIT Press, 1990), pages 64 ff.
  3. ↑ Swedin, E.G. & Ferro, D.L. (2005). Computers: The Life Story of a Technology. Greenwood Press, Westport, CT. Retrieved 2007-11-17.
  4. ↑ O'Connor, John J.; Robertson, Edmund F. (1998). "Charles Babbage". MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland. Retrieved 2006-06-14.
  5. 1 2 3 4 Campbell-Kelly, Martin (2004). Computer: A History of the Information Machine 2nd ed. Boulder, Co: Westview Press. ISBN 978-0-8133-4264-1.
  6. ↑ Snyder, Laura J. (2011). The Philosophical Breakfast Club. New York: Broadway Brooks. ISBN 978-0-7679-3048-2.
  7. ↑ Raymond Clare Archibald: Martin Wiberg, his Table and Difference Engine, Mathematical Tables and Other Aids to Computation, 1947(2:20) 371–374. (online review) (PDF; 561 kB).
  8. ↑ IEEE Annals of the History of Computing, 22(4), October–December 2000.
  9. ↑ Babbage printer finally runs, BBC news quoting Reg Crick Accessed May 17, 2012
  10. ↑ "At the Museum". Retrieved 2009-07-28.
  11. ↑ Terdiman, Daniel (April 9, 2008). "Charles Babbage's masterpiece difference engine comes to Silicon Valley". CNET News. Retrieved 2008-04-28.
  12. ↑ "The Computer History Museum Extends Its Exhibition of Babbage's Difference Engine No. 2". press release. Computer History Museum. March 31, 2009. Retrieved 2009-11-06.
  13. ↑ Difference Engine Leaves Computer History Museum, Mark Moack, Mountain View Voice, January 29, 2016
  14. 1 2 Thelen, Ed (2008). "Babbage Difference Engine #2 – How to Initialize the Machine -". Retrieved 2009-01-11.

Further reading

External links

Wikimedia Commons has media related to Difference engines.
This article is issued from Wikipedia - version of the Thursday, March 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.