Sunday, March 2, 2014

The Babbage Difference Engine #2 – A Basic Explanation

Contents

Overview

On a recent visit to the Computer History Museum in Mountain View California, I was impressed with a live demonstration of the Difference Engine #2. But, I didn’t have a clue as to what the engine was actually doing and set about to find out. This post represents what I found. Disclaimer: I’m not claiming that this is 100% accurate, but it’s close. For an in depth study of the Babbage Difference Engine #2, see Babbage Difference Engine #2 - How to Initialize the Machine - Including Initial Values.

In a Nutshell

In a nutshell, the Difference Engine #2 solves a seventh order polynomial: $$ f(x)=a_7x^7 + a_6x^6 + ... + a_1x + a_0 $$ The operator configures the engine (with values related to the coefficients of the polynomial) and after a few moments of cranking, out comes \( f(x) \). How does a Victorian-era calculating machine composed of 8,000 levers and gears do this? And, more importantly, why was it designed to do this? What inspired Charles Babbage to design the engine? (When he wasn’t fighting irksome street performers.)

Quick History

Babbage designed Difference Engine #2 between 1847 and 1849, but never built it. The engine in the Computer History Museum is one of two built from Babbage’s original design; building from Babbage’s plans started in the early 1990s. For more information about why and how the engine was built, see the Computer History Museum’s description, A Modern Sequel. There is a brief overview of Babbage’s Difference Engine #2 given in IEEE Annals of the History of Computing (2005) in the article The Construction of Charles Babbage's Difference Engine No. 2 by Doron Swade.

Why a Polynomial?

Why solve a polynomial? Polynomials are interesting in their own right, but in this case the polynomial is used as an approximation for another function, like a logarithm. During Babbage’s lifetime, tables of logarithms were very important in scientific calculations, particularly in the burgeoning fields of astronomy and navigation. Here are a couple efforts involving the production of logarithm tables:

In the rest of this discussion, we’ll deal with the natural logarithm \( ln(x) \).

back to the top

Using a Polynomial to Approximate a Logarithm

A logarithm can be can be approximated by a Taylor series: $$ ln(x) = (x-1) - (1/2)(x-1)^2 + (1/3)(x-1)^3 - (1/4)(x-1)^4 + ... $$

We can plot values of the fourth order Taylor series (Figure 1) and see that it is really only good over a limited range, say between 0.5 and 1.5.

Figure 1: Plot for the Fourth Order Taylor Series with \( ln(x) \) 


How does this help for calculating the logarithm of large numbers? We can calculate the logarithm of a larger number by breaking it into the product of a mantissa and an exponent. For example, an arbitrary number can be written as \( ln(x) = ln(m) + p ln(2) \). So for 5,342:

$$x=5342=0.6521*2^{13}$$ $$ln⁡(5342)=ln⁡(0.6521)+13*ln⁡(2)$$

The mantissa (0.6521) is in the range that our Taylor series approximation is good (at least for this demonstration) and we would only have to perform a simple multiplication and addition to get the final value of the natural logarithm of 5,432. We would need the value of \(ln⁡(2)\) for the calculation. This is all described to point out that we could look at a small range of values of the approximating series to the logarithm and be sure we could calculate values outside the range.

Sticking with four terms in the Taylor series, we can perform the expansion of the terms, rearrange and end up with:

$$ln⁡(x)=-x^4/4+(4x^3)/3-3x^2+4x-25/12$$

(You can expand using Wolfram Alpha’s expand function: expand (x-1) - ((x-1)^2)/2 + ((x-1)^3)/3 - ((x-1)^4)/4.)

back to the top

Using the Method of Differences for Polynomials

One way to calculate and tabulate polynomials is using the method of differences, which has the advantage that you can use simple addition and subtraction in a tabular form to calculate arbitrary values of a given polynomial. This method was well known in Babbage’s lifetime and performed by humans to produce results that appeared in logarithm and other tables of the time. Charles Babbage designed the Difference Engines (#1 and #2) to do this automatically and remove human error.

Tabulating here means for a given values of \(x\), find corresponding values of \( f(x) \) (or here, \( ln(x) \) ). As you will see below, this literally means, as you probably guessed, creating a table of values.

In a previous post, Museum of Computer History, Mountain View California, we talked about how the difference engine uses the concept of method of differences to turn the problem of finding values of a polynomial into a problem of constructing simple tables based only on addition and subtraction. The method of differences works by taking the difference of values of polynomial (\(f(x)\)), and then taking the difference of the differences, and so on, until you reach a point where there are no more differences. In effect, you are taking the derivative of the polynomial until you reach a constant value.

back to the top

Method of Differences for a Second Order Polynomial

Let’s start simple with the following second-order polynomial:

$$f(x) = 2x^2 - 3x + 2$$

For a step size of \( \Delta x=0.1 \) and and the three starting values in red, we can (forward) compute the values in green, and then we can (reverse) compute the values in blue. So, from three starting values, we can  eventually find any value of \( f(x) \). It may not seem like a big “win” because we could just plug any value (e.g., 101.3) of x in the quadratic equation and be done with it, right? But, when calculators (or other easy way to calculate values) were not available, this way of calculating a values was important.

In Table 1, \(d(x)\) is the difference of values of the \(f(x)\) and \(d'(x)\) is the difference of the differences.

Table 1: Example of Finite Differences of Second Order Polynomial

In Table 2, we show the flow of the calculations as:
Calculation 1 = 1.72 – 2 = -0.28
Calculation 2 = 1.48 - 1.72 = -0.24
Calculation 3 = -0.24 – (-0.28) = 0.04
Calculation 4=> value – (-0.24) = 0.04 => value = -0.20
Calculation 5 => value – 1.48 = -0.20 => value = 1.28

Table 2: Table 1 Repeated with Series of Calculations

You would then keep calculating “blue” values by starting from the right most column and working your way left and down (on a diagonal) to produce a new value of \(f(x)\).

For this polynomial, it’s easy to calculate the exact formula for \(d(x)\) and \(d'(x)\):

$$d(x)=f(x+\Delta x)-f(x)=2{\Delta}x^2 + 4x{\Delta}x-3{\Delta}x$$ $$d'(x)=d(x+{\Delta}x)-d(x)= 4{\Delta}x^2$$

Note that \(d(x)/{\Delta}x\) is the approximation of the derivative. Although not the point of this exercise, it shows that the method of differences is closely related to derivatives.

Other points to note:

  • It only takes three values to start the tabulation process. In general, it will take one more than the highest power of the polynomial.
  • Values of \({\Delta}x\) can be big or small, but once you choose one, you must keep it the same for the rest of the tabulation calculations.
  • The last column of a table of method of differences (if you do it correctly) results in a constant value. Think of taking the derivative of a function until no more powers are left.

back to the top

Method of Differences for a Third Order Polynomial

Let’s now take a third-order polynomial.

$$ f(x) = x^3 - x^2 - x $$

And, let’s pick a \({\Delta}x=2\) value that “skips” over an area of the graph where the function dips and then rises again. You might think that we have to pick a \({\Delta}x\) small enough to capture all features of the polynomial. But, it doesn’t matter for method of differences.

Figure 2: Third Order Polynomial \(f(x) = x^3 - x^2 – x\)

Here’s the difference table for \({\Delta}x=2\), starting at \(x=0\).

Table 3: Finite Difference Example for the Third Order Polynomial \(f(x) = x^3 - x^2 – x\).

Another thing to think about is we don’t need to store all the red values and green values. After we calculate the “triangle” of green values, we only need the one red value and the green values on the diagonal. This is not so important here because we keep all the values in the table, for demonstration purposes. But for the difference engine, or if you are writing a computer program, you would only want to keep the minimum number of values (table cells) required to get your next value of \(f(x)\). The circles in the following diagram show the table cells required to calculate \(f(8)\). Every time, we use a value in a circle to calculate the value to the left, we can move the circle down to the same table cell in the next row.

Table 4: Table 3 with Value Highlighted for Calculation of \( f(8) \).

back to the top

Method of Differences for a Fourth Order Polynomial

Let’s now go back to the fourth order Taylor series approximation for \(ln⁡(x)\):

$$ln⁡(x)=-(x^4)/4+(4x^3)/3-3x^2+4x -25/12$$

Here’s the difference table with \({\Delta}x=0.05\), starting at \(x=0\). Note that right most column is (as expected) constant but it takes four difference operations to get there. Also note that \(ln(0)\) is calculated correctly, but the \(ln(1.5) = 0.401042\) and the true value is \(0.405465\), showing rounding errors are starting to play a role. We won’t talk about rounding errors or precision much here, but it is a serious concern.

Table 5: Fourth Order Taylor Series, Finite Differences

back to the top

Scaling the Method of Differences

Up to this point we’ve considered simple polynomials with relatively simple coefficients. The difference engine solves polynomials with integer coefficients, therefore, to truly deal with real value (like decimals) some kind of scaling will be necessary. The difference engine can be programmed with integer coefficients represented with up to 31 digits.

Let’s say we multiply each coefficient of the fourth order Taylor series for ln(x) by 100,000 so we are dealing with this polynomial:

$$ln⁡(x)=-25000x^4+133333x^3-300000x^2+400000x -208333$$

Calculating the first few entries of the method of differences table, we see that all values in a row compare to Table 5 are just multiplied by 100000. So, we can see that we can use scaling to deal with decimal values.

Table 6: Scaling the Coefficients in the Method of Differences

back to the top

Mapping the Method of Differences to the Difference Engine #2

Let’s now move on to a seventh order polynomial:

$$ f(x)=a_7x^7 + a_6x^6 + a_5x^5 + a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 $$

From what we’ve seen above for the second, third, and fourth order polynomial examples, if we were to create a method of differences table, we would have a table of 8 columns. One column (col 8) would be the result value. If we keep the order of the columns as we did above and add labels to each column (e.g., “col 1”) we have something like what is shown in Table 7.

Table 7: Seventh Order Polynomial – Method of Differences Table with
Calculation Sequence and Mapping to Difference Engine

Following what we did above for the simpler polynomials, once we have the values for the red cells, we can use addition and subtraction to populate the green cells. Once we have the green cells, we would put the values in the cells marked as X1 – X7 as the configuration values in the difference engine.

Where do you put the values X1 – X7? You put them in the seven columns of the engine as shown in Image 1. Column 8 is the result column. Note that the values of X1 – X7 are based on the original coefficients but they are not equal to the coefficients.

Image 1: Gigapixel Image of the Babbage Difference Engine #2,
Annotated with Column Numbers for Method of Differences

back to the top

The Engine in Action: Information from a Recent Visit

With every calculation cycle (a certain number of turns on the crank on the right of Figure 3), col 8 gets a new value. This is the result.  While I didn’t confirm it directly, Col 1 stays the same (because it’s a constant), and col 2 through col 7 change to new values for the next calculation cycle.

On the day in January I visited the difference engine for a second time, I was able to get a little more information about how it works and that is captured in Images 2, 3, 4, and 5. 

Image 2 shows the polynomial used at the time to calculate the logarithm base 10 (not a natural log as above). The polynomial is not a Taylor series as we used above; it’s an interpolating polynomial that better fits the logarithm. For example, Image 3 shows an example calculation log10(1.3960) = 0.144885. If you enter the value of x = 1.3960 in the polynomial in Image 2, the result is 0.144885.

Image 4 and 5 show a curious thing that I was not expecting. It shows that the the result column (col 8) shows both the calculation and the value of x that was being calculated. Doing so helps the operators keep track of where they are, among other benefits. Note that only the fractional part of the x (the part to the right of the decimal point) is shown. The “1” in 1.3960 is left off.

Image 3 and 5 show col 8 and show the value of x (yellow) and the result (red). You read the results column from top to bottom. In the next section, we’ll go back to a simpler example to understand how the method of differences could be set up to keep track of x as well.

Left: Image 2 -The Interpolating Polynomial to Calculate the Logarithm; Right: Image 3 – Results Sheet

Left: Image 4 – The Current Value of X (Input into the Polynomial); Right: Image 5 – The Value of x and the Result in Column 8

Setting up a Counter in the Method of Differences Results Column

Let’s take \(f_1(x) = x\) and \( f_2(x) = (2*x^2 - 3x + 2)/1000\). \(f_1(x)\) is our "counter". \(f_2(x)\) is the same function we worked with above divided by 1,000 to scale it so that it returns values in a different range than \(f_1(x)\). Finally, let \( f_3(x) = f_1(x) + f_2(x)\). Table 8 shows the method of differences tables for each of these functions. It shows that the results column is essentially additive and the trick of scaling.

Table 8: Method of Differences Example Demonstrating
How to Add a Counter in the Results Column

Dealing with Negative Numbers

In all the example up to this point, we have used positive and negative numbers in the method of difference tables. However, the difference engine can only deal with positive integer values (of up to 31 digits). Seems like a limitation, but we can use the Method of complements to represent negative integers as positive ones in calculations. Specifically, we’ll use the method of complements with a radix of 10, which is called 10’s complement.

10’s complement can be explained as follows. Pick a power of ten (10, 100, 1000, etc.) that covers the range of positive and negative integers you want to work with and then use half of the range to represent positive integers and half to represent negative integers. For example, let’s say we have a math problem where we want to work with integers from -5,000 to 5,000. In this case, pick 10,000 and let 1 to 4,999 be represented by 1 to 4,999 and -4,999 to -1 be represented by 5,001 to 9,999. In effect, we are assigning half our range of positive integers to represent positive integers and half to represent negative integers. Continuing with this example, if you wanted to subtract 1,213 from 3,000 (or you could say add negative 1,213 to positive 3,000), you first find the 10’s complement of 1,213 which is 8,787 and then add (instead of subtract) 8,787 to 3,000 to get 11,787. By convention, you throw away the leading 1 to end up with 1,787. The method of complements is just a way to use addition to perform subtraction.

Okay, now let’s look at the following second order polynomial to show how to use 10’s complement in the method of differences:

$$f(x) = 100x^2 - 600x + 200$$

Let’s use a step size of \({\Delta}x=0.5\), and the same color scheme as above (red are initial values we provide and green are calculated values), so that the method of differences table looks like this.

Table 9: Method of Differences for \(f(x) = 100x^2 - 600x + 200\)

Consistent with our column numbering from above, let’s name the columns from right to left and pretend we are dealing with just a three column difference engine (i.e., a difference engine that could only calculate up to second order polynomials). For a second order polynomial, we know that we need to start the engine off with three numbers, in this case {-400, -225, 50} from columns 3 to 1. The value in col 1 will never change, it’s the constant. But the values in col 2 and col 3 will change. If we label c1 to c4 as the calculations to be performed (in that order) we can start calculating as follows:

c1 = 50 + (-225) = - 175
c2 = c1 + (-400) = - 575
c3 = 50 + c1 = - 125
c4 = c3 + c2 = - 700

So far, we’ve only repeated what we already know about the method of differences, and we are still using negative numbers. But, and here’s the trick, if we use the 10’s complement on our starting three numbers (assuming 10,000 as our total range of numbers), they three numbers can be represented as {9600, 9775, 50} – all positive. Now, we can run through the calculations for c1 to c4 again using these 10’s complement numbers and the rules for 10’s complement addition:

c1 = 50 + 9775 = 9825 (which is really -175)
c2 = c1 + 9600 = 19425 -> throw away leading 1 to get 9425 (which is really -575)
c3 = 50 + c1 = 9875 (which is really -125)
c4 = c3 + c2 = 9875 + 9425 = 19300 -> throw away leading 1 to get 9300 (which is -700)

So we can work with positive integers and only perform additions as we can continue calculating rows in the method of differences table. In this example, we would quickly realize that 10,000 as our range would not be enough to cover the integers we want to work with.

Labels: ,

1 comment:

All comments go through a moderation process. Even though it may not look like the comment was accepted, it probably was. Check back in a day if you asked a question. Thanks!

Subscribe to: Post Comments (Atom)