Finite Differences as a Mechanical Computation Method

A table of a cubic can be extended one row at a time with nothing but addition. Sample $f(x) = x^3 - 2x + 1$ at unit intervals and the values are 1, 0, 5, 22, 57, 116, 205. The first differences are $-1, 5, 17, 35, 59, 89$; the second, $6, 12, 18, 24, 30$; the third, $6, 6, 6, 6$. Three rounds of subtraction have reduced a cubic to a constant. From the last row of that block, holding 205, 89, 30 and 6, the next value follows from three additions: $30 + 6 = 36$, $89 + 36 = 125$, $205 + 125 = 330$, which is $f(7)$. No multiplication appears anywhere in the extension.

The recurrence and the constant that ends it

A polynomial of degree $n$ is fully determined by its value and its first $n$ forward differences at a single point, and its $n$-th difference is constant. That constant is the whole trick. Advancing the table means adding the constant into the difference below it, that difference into the one below it, and so on down to the tabular value. Each new row costs $n$ additions and no multiplications, and the cost per row does not change as the table grows.

The constant is also small compared with the value. For $f(x) = ax^7$ the seventh difference is $5040a$, so the constant column of a seventh-order table holds four significant digits of a number that has room for thirty-one. The tabular column carries the value itself, which grows like $x^7$, and that column sets the range of the table long before the differences do.

Avoiding multiplication was worth this trouble because mechanical multiplication is not one operation. Multiplying by a multi-digit value is a loop of shifted additions with carries between them, and Babbage’s Analytical Engine needed separate mechanisms for it, which the Science Museum’s technical description calls irreducibly more time-consuming than the repeated additions of a difference engine.

def difference_table(f, degree, x0=0):
    row = [f(x0 + i) for i in range(degree + 1)]
    table = [row]
    while len(table[-1]) > 1:
        prev = table[-1]
        table.append([b - a for a, b in zip(prev, prev[1:])])
    return table

def advance(col):
    """col[0] is the tabular value, col[k] the k-th difference."""
    nxt = [col[k] + col[k + 1] for k in range(len(col) - 1)]
    nxt.append(col[-1])             # the constant difference never changes
    col[:] = nxt
    return col[0]

col = [row[0] for row in difference_table(lambda x: x**3 - 2*x + 1, 3)]
print(col)                                       # [1, -1, 6, 6]
print(advance(col), advance(col), advance(col))  # 0 5 22

The block is a model of the paper recurrence, not of the engine. Every new value is formed from values held before the step, which is what makes the sequence a repeated prefix sum. The engine reaches the same series by the phased additions described below, with a compensating offset written into the setup.

Eight columns of thirty-one figure wheels

Difference Engine No. 2 has eight vertical columns of figure wheels, thirty-one wheels to a column, 248 wheels in the calculating section. The rightmost column holds the seventh difference, the sixth sits to its left, and the tabular value sits on the leftmost column beside the printer. Units are at the bottom of each column, so a carry travels upward one wheel at a time.

An addition is not one motion either. The source wheel is driven towards zero and the receiving wheel is incremented by the same amount through an intermediate sector wheel, a process the technical description calls giving-off. The sector is what holds the given-off value: it is meshed to both wheels, turns as the source returns to zero, and is reduced to zero again later in the cycle once the receiving wheel is locked, which puts the original value back on the source for the next row. While a receiving wheel passes through 9 its external nib arms a warning latch, and a separate carriage phase later in the cycle increments the wheel above it. Giving-off, warning, carriage and restoration: four operations, thirty-one digit positions, per pair of columns.

A figure wheel has forty teeth, and one tooth pitch of 9 degrees corresponds to one decimal digit. Each wheel carries four identical runs of the digits 0 to 9, so a digit can sit at any of four angular positions, and a wheel turns through no more than 81 degrees before its zero stop halts it.

Nothing in a toothed wheel is inherently discrete. It can come to rest between two digits, and in that position its value is undefined. The design turns that into a detector: locks engage four times per cycle, and a wheel deranged by more than 2¼ degrees obstructs the lock as it is inserted, so the crank seizes. The technical description quotes Babbage’s claim that the engine will break, jam but never deceive.

Two half-cycles instead of seven serial additions

On paper the method is strictly serial. The seventh difference updates the sixth, the sixth updates the fifth, and each addition waits on the one above it, so a seventh-order table costs seven dependent additions per row. The engine does not work that way. It splits the calculating cycle into two half-cycles: the four odd difference columns, the 7th, 5th, 3rd and 1st, are added to the even columns in the first half, and the even columns, the 6th, 4th, 2nd and the tabular column, which is built like an even column, are added to the odd ones in the second. Carries complete inside each half-cycle, so every column pair works at once.

The cycle is divided into fifty time units, each corresponding to 7.2 degrees of the crank’s 360-degree turn. The technical description compares the arrangement to pipelining: a seventh-order table is produced in two addition times rather than seven, all participating columns stay busy rather than two at a time, and the cycle time stops depending on how many differences are in use. The 7:2 figure is the description’s accounting, on the assumption that one addition with carries takes a single time unit; it is not a timing of the built machine.

The price is paid at setup. Initial values are entered by hand on the figure wheels from a pre-computed table, and because the halves interleave, the values on alternate columns must be offset from the plain difference table. The series produced is the same; the entry procedure is not. The carry mechanism is what bounds the cycle, since every addition in a half-cycle must finish its carries before the next half-cycle starts. The constant column is a special case: it only ever gives off and never receives, and the technical description records that the carry mechanism for the seventh difference axis was left out of the built engine.

What an inexact value costs downstream

Error moves in one direction only, upward in the difference order, and the amplification is binomial. A unit error in the $k$-th difference at some row appears in the tabular value $m$ rows later as $\binom{m}{k}$, because advancing the table is a repeated prefix sum. The result is a delay followed by a cliff: the injected digits sit below the last place printed until the binomial term is large enough to reach it. A unit error in the seventh difference of a 31-digit table stays inside the tabular column for tens of thousands of rows: $\binom{m}{7}$ first reaches $10^{31}$ at $m = 90{,}679$. On the sixteen-digit, six-order 1830 design of Difference Engine No. 1 the same error reaches $10^{16}$ after 1,393 rows. An error in the first difference, by contrast, grows by exactly one unit per row.

from math import comb

# tabular offset m rows after a unit error in difference k
def amplified(k, m):
    return comb(m, k)

for m in (100, 1000):
    print(m, [amplified(k, m) for k in range(8)])

The machine’s error detection does not cover this ground. A jam reports a wheel out of position; a setup value transcribed incorrectly is added into the table with perfect mechanical fidelity, at full precision, for as long as the crank is turned.

Rounding has the same shape. Rounding the printed tabular value on each row injects error at the lowest order, where $\binom{m}{0} = 1$: it persists but does not grow. Rounding a difference column injects error higher up, where it does grow, and the growth accelerates with every row that follows. That asymmetry is why the method suits integer-valued problems and fixed-point work with headroom, and why a table of a transcendental function is built by fitting a polynomial to a bounded interval, choosing the degree so the neglected term stays inside the accuracy budget, and restarting at the interval boundary rather than running one table indefinitely.

Where the columns run out

Thirty-one digits bound the argument range as much as the differences do. A table of $x^7$ fills the tabular column at about $x = 26{,}800$, since $10^{31/7}$ is roughly $2.7 \times 10^4$.

The parts count is the other bound. The 1830 design of Difference Engine No. 1 called for sixteen digits and six orders of difference, about 25,000 parts divided evenly between the calculating section and the printer, an estimated four tons, and about eight feet of height, according to the Computer History Museum; the Science Museum’s technical description gives 24,000 parts for the machine Clement was engaged to make. Construction halted in 1832 after the dispute with Clement and government funding ended in 1842. The surviving 1832 demonstration piece is one-seventh of the engine, about 2,000 parts, and still turns.

Difference Engine No. 2 was designed for 31 digits and seven orders of difference, and Babbage’s drawings call for about 8,000 parts, roughly a third of Number 1. The Science Museum’s technical description dates the design 1846 to 1849; the museum’s object record gives 1847 to 1849. The London engine, built to those drawings with metal first cut in 1986, the calculating section finished in 1991 and the printing and stereotyping apparatus in 2002, also runs to about 8,000 parts. The printer is coupled to the calculating section rather than fed from a buffer: thirty of the thirty-one result digits are transferred and printed during the calculating cycle that produces them, the top digit is dropped, and the stereotyping punches impress the same digits into plaster to make a printing plate.

The remaining structural limit is that the engine can tabulate polynomials and nothing else. The setup table, the interval and the degree are all chosen outside it, by a person with paper. Replacing the fixed difference columns with general arithmetic is what the Analytical Engine does: multiplication and division become mechanisms in their own right, at a cost the difference engine avoids by never needing them. The difference engine trades generality for producing a row of a table with seven additions, and the trade holds only while the function arrives as a polynomial with exact initial values.