A difference engine is an automatic mechanical calculator designed to tabulate polynomial functions. It was designed in the 1820s, and was first created by Charles Babbage. The name difference engine is derived from the method of divided differences, a way to interpolate or tabulate functions by using a small set of polynomial co-efficients. Some of the most common mathematical functions used in engineering, science and navigation are built from logarithmic and trigonometric functions, which can be approximated by polynomials, so a difference engine can compute many useful tables.
The notion of a mechanical calculator for mathematical functions can be traced back to the Antikythera mechanism of the 2nd century BC, while early modern examples are attributed to Pascal and Leibniz in the 17th century.
In 1784 J. H. Müller, an engineer in the Hessian army, devised and built an adding machine and described the basic principles of a difference machine in a book published in 1786 (the first written reference to a difference machine is dated to 1784), but he was unable to obtain funding to progress with the idea. [1] [2] [3]
Charles Babbage began to construct a small difference engine in c. 1819 [4] and had completed it by 1822 (Difference Engine 0). [5] He announced his invention on 14 June 1822, in a paper to the Royal Astronomical Society, entitled "Note on the application of machinery to the computation of astronomical and mathematical tables". [6] 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. [7]
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 estimate. According to the 1830 design for Difference Engine No. 1, it would have about 25,000 parts, weigh 4 tons, [8] and operate on 20-digit numbers by sixth-order differences. In 1832, Babbage and Joseph Clement produced a small working model (one-seventh of the plan), [5] which operated on 6-digit numbers by second-order differences. [9] [10] Lady Byron described seeing the working prototype in 1833: "We both went to see the thinking machine (or so it seems) last Monday. It raised several Nos. to the 2nd and 3rd powers, and extracted the root of a Quadratic equation." [11] Work on the larger engine was suspended in 1833.
By the time the government abandoned the project in 1842, [10] [12] 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 unpredictable cost) of the machine itself. Babbage refused to recognize that predicament. [7] 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. [7]
The incomplete Difference Engine No. 1 was put on display to the public at the 1862 International Exhibition in South Kensington, London. [13] [14]
Babbage went on to design his much more general analytical engine, but later designed an improved "Difference Engine No. 2" design (31-digit numbers and seventh-order differences), [9] between 1846 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. [15] [16]
Inspired by Babbage's difference engine in 1834, Per Georg Scheutz built several experimental models. In 1837 his son Edward proposed to construct a working model in metal, and in 1840 finished the calculating part, capable of calculating series with 5-digit numbers and first-order differences, which was later extended to third-order (1842). In 1843, after adding the printing part, the model was completed.
In 1851, funded by the government, construction of the larger and improved (15-digit numbers and fourth-order differences) machine began, and finished in 1853. The machine was demonstrated at the World's Fair in Paris, 1855 and then sold in 1856 to the Dudley Observatory in Albany, New York. Delivered in 1857, it was the first printing calculator sold. [17] [18] [19] In 1857 the British government ordered the next Scheutz's difference machine, which was built in 1859. [20] [21] It had the same basic construction as the previous one, weighing about 10 cwt (1,100 lb ; 510 kg ). [19]
Martin Wiberg improved Scheutz's construction (c. 1859, his machine has the same capacity as Scheutz's: 15-digit and fourth-order) but used his device only for producing and publishing printed tables (interest tables in 1860, and logarithmic tables in 1875). [22]
Alfred Deacon of London in c. 1862 produced a small difference engine (20-digit numbers and third-order differences). [17] [23]
American George B. Grant started working on his calculating machine in 1869, unaware of the works of Babbage and Scheutz (Schentz). One year later (1870) he learned about difference engines and proceeded to design one himself, describing his construction in 1871. In 1874 the Boston Thursday Club raised a subscription for the construction of a large-scale model, which was built in 1876. It could be expanded to enhance precision and weighed about 2,000 pounds (910 kg). [23] [24] [25]
Christel Hamann built one machine (16-digit numbers and second-order differences) in 1909 for the "Tables of Bauschinger and Peters" ("Logarithmic-Trigonometrical Tables with eight decimal places"), which was first published in Leipzig in 1910. It weighed about 40 kilograms (88 lb). [23] [26] [27]
Burroughs Corporation in about 1912 built a machine for the Nautical Almanac Office which was used as a difference engine of second-order. [28] : 451 [29] It was later replaced in 1929 by a Burroughs Class 11 (13-digit numbers and second-order differences, or 11-digit numbers and [at least up to] fifth-order differences). [30]
Alexander John Thompson about 1927 built integrating and differencing machine (13-digit numbers and fifth-order differences) for his table of logarithms "Logarithmetica britannica". This machine was composed of four modified Triumphator calculators. [31] [32] [33]
Leslie Comrie in 1928 described how to use the Brunsviga-Dupla calculating machine as a difference engine of second-order (15-digit numbers). [28] He also noted in 1931 that National Accounting Machine Class 3000 could be used as a difference engine of sixth-order. [23] : 137–138
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. [34] This work led the Science Museum to construct a working calculating section of difference engine No. 2 from 1985 to 1991, under Doron Swade, the then Curator of Computing. This was to celebrate the 200th anniversary of Babbage's birth in 1991. In 2002, the printer which Babbage originally designed for the difference engine was also completed. [35] 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), [36] which had to be corrected. 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 could have worked using Georgian-era engineering methods. The machine contains 8,000 parts and weighs about 5 tons. [37]
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 slips in the manual typesetting process. [7] 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, 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, from May 2008 to January 2016. [37] [38] [39] [40] It has since been transferred to Intellectual Ventures in Seattle where it is on display just outside the main lobby. [41] [42] [43]
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 first and higher derivatives of the polynomial. [44]
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 is thus: [44]
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.
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:
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.
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
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:
x | p(x) = 2x2 − 3x + 2 | diff1(x) = ( p(x + 1) − p(x) ) | diff2(x) = ( diff1(x + 1) − diff1(x) ) |
---|---|---|---|
0 | 2 | −1 | 4 |
1 | 1 | 3 | 4 |
2 | 4 | 7 | 4 |
3 | 11 | 11 | |
4 | 22 |
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, can hold 8 numbers of 31 decimal digits each and can thus tabulate 7th degree polynomials to that precision. The best machines from Scheutz could store 4 numbers with 15 digits each. [45]
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 gets the value of the function at the start of computation . Col is the difference between and ... [46]
If the function to be calculated is a polynomial function, expressed as
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:
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 for all derivatives. Setting 0 as the start of computation we get the simplified Maclaurin series
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
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. [46] With the optimized polynomial, the initial values can be calculated as above.
The analytical engine was a proposed digital mechanical general-purpose computer designed by English mathematician and computer pioneer Charles Babbage. It was first described in 1837 as the successor to Babbage's difference engine, which was a design for a simpler mechanical calculator.
Charles Babbage was an English polymath. A mathematician, philosopher, inventor and mechanical engineer, Babbage originated the concept of a digital programmable computer.
In mathematics, the logarithm to baseb is the inverse function of exponentiation with base b. That means that the logarithm of a number x to the base b is the exponent to which b must be raised to produce x. For example, since 1000 = 103, the logarithm base of 1000 is 3, or log10 (1000) = 3. The logarithm of x to base b is denoted as logb (x), or without parentheses, logb x. When the base is clear from the context or is irrelevant it is sometimes written log x.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
A multiplication algorithm is an algorithm to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much research into the topic.
In elementary algebra, the quadratic formula is a closed-form expression describing the solutions of a quadratic equation. Other ways of solving quadratic equations, such as completing the square, yield the same solutions.
In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was an important area of study, which led to the development of the first mechanical computing devices.
In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals 32 and can be written as 3 × 3.
In mathematics and computer science, truncation is limiting the number of digits right of the decimal point.
In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation, in a process termed as direct addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated as part of a program's initialization phase (memoization), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid items in an array and, in some programming languages, may include pointer functions to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality. LUTs differ from hash tables in a way that, to retrieve a value with key , a hash table would store the value in the slot where is a hash function i.e. is used to compute the slot, while in the case of LUT, the value is stored in slot , thus directly addressable.
A mechanical calculator, or calculating machine, is a mechanical device used to perform the basic operations of arithmetic automatically, or (historically) a simulation such as an analog computer or a slide rule. Most mechanical calculators were comparable in size to small desktop computers and have been rendered obsolete by the advent of the electronic calculator and the digital computer.
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.
In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby. What is meant by best and simpler will depend on the application.
Martin Wiberg was a Swedish inventor. He enrolled at Lund University in 1845 and became a Doctor of Philosophy in 1850.
Pehr (Per) Georg Scheutz was a Swedish lawyer, translator, and inventor, who is now best known for his pioneering work in computer technology.
A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.
Allan George Bromley was an Australian historian of computing who became a world authority on many aspects of early computing and was one of the most avid collectors of mechanical calculators.
The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products.
Doron Swade MBE, born 1944, is a museum curator and author, specialising in the history of computing. He is especially known for his work on the computer pioneer Charles Babbage and his Difference Engine.
Note G is a computer algorithm written by Ada Lovelace that was designed to calculate Bernoulli numbers using the hypothetical analytical engine. Note G is generally agreed to be the first algorithm specifically for a computer, and Lovelace is considered as the first computer programmer as a result. The algorithm was the last note in a series labelled A to G, which she employed as visual aids to accompany her English translation of Luigi Menabrea's 1842 French transcription of Charles Babbage's lecture on the analytical engine at the University of Turin, "Notions sur la machine analytique de Charles Babbage". Lovelace's Note G was never tested, as the engine was never built. Her notes, along with her translation, were published in 1843.
In WikiSource and also reprinted in The works of Charles Babbage, Vol 2, p.119ff