Difference engine
From Free net encyclopedia
- For the novel by Bruce Sterling and William Gibson, see The Difference Engine
Image:BabbageDifferenceEngine.jpg A difference engine is a historical, mechanical special-purpose computer designed to tabulate polynomial functions. Since logarithmic and trigonometric functions can be approximated by polynomials, such a machine is more general than it appears at first.
Contents |
History
The first of these devices was conceived in 1786 by J. H. Mueller. It was never built.
Difference engines were forgotten and then rediscovered in 1822 by Charles Babbage, who proposed it in a paper to the Royal Astronomical Society entitled "Note on the application of machinery to the computation of very big mathematical tables."[1] 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 (introduced by accident or perhaps as a protection against unauthorized use), 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.)
Method of differences
Image:050114 2529 difference.jpg The principle of a difference engine is Newton's method of differences. It may be illustrated with a small example. Consider the quadratic polynomial
- p(x) = 2x2 − 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 first column contains the values of the polynomial, the second column contains the differences of the two left neighbors in the first column, and the third column contains the differences of the two neighbors in the second column:
| p(0)=2.0 | ||
| 2.0−1.72=0.28 | ||
| p(0.1)=1.72 | 0.28−0.24=0.04 | |
| 1.72−1.48=0.24 | ||
| p(0.2)=1.48 | 0.24−0.20=0.04 | |
| 1.48−1.28=0.20 | ||
| p(0.3)=1.28 | 0.20−0.16=0.04 | |
| 1.28−1.12=0.16 | ||
| p(0.4)=1.12 |
Notice how the values in the third column are constant. This is no 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 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 rightmost column value of 0.04. Then we continue the second column by subtracting 0.04 from 0.16 to get 0.12. Next we continue the first column by taking its previous value, 1.12 and subtracting 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, subtract that from the second column's value 0.12 to get 0.08, then subtract 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 subtract. 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.
See also
External links
- The London Science Museum exhibition on the Difference Engine
- Meccano Difference Engine
- Difference Engine in Legode:Differenzmaschine
es:Máquina diferencial fi:Differenssikone ja:階差機関 pt:Máquina diferencial ru:Разностная машина Чарльза Бэббиджа