Ada Lovelace and The Analytical Engine
Published: 09-03-2015 | Author: Juliet Kemp | Text only version of this article
Table of Contents
This article was originaly published in Linux Voice, issue 1, April 2014.This issue is now available under a Creative Commons BY-SA license. In anutshell: you can modify and share all content from the magazine (apart fromadverts), even for commercial purposes, providing you credit Linux Voice as theoriginal source, and retain the same license.
This remix is converted manually to Markdown and HTML for ease of archiving andcopy-pasting.
Other converted Linux Voice articles can be found here.
Use the Linux Voice time machine to take a trip to Victorian England, and visitone of the pioneers of the computer age.
Ada Lovelace and The Analytical Engine
Back in the 19th century, if you wanted to do complicated mathematicalcalculations you had to do them by hand. To speed things up, you could buyprinted tables of specific calculations such as logarithms but as these too werecalculated by hand, they were full of errors.
Enter Charles Babbage, mathematician, philosopher, engineer and inventor, who inthe early 1820s designed a Difference Engine to do these calculationsautomatically. The Difference Engine could only add up, so it wasn't a general-purpose 'computer'. It also never existed in Babbage's time, although part of aprototype was constructed. Babbage fell out with his engineer and ran out offunding, so construction stalled around 1833 and was finally abandoned in 1842.
Meanwhile, in 1834 Babbage began to design a more complex machine called theAnalytical Engine. This would be able to add, subtract, multiply, and divide,and it is the Analytical Engine that can be considered as the first general-purpose computer.
Or could, if it had ever existed: Babbage built a few pieces of prototype, andcarried on refining the design until his death in 1871, but never found fundingfor the full thing.
But despite its lack of concrete existence, other mathematicians were interestedin it, including Louis Menebrae, and Ada Lovelace, who was already correspondingwith Babbage.
Augusta Ada King, Countess of Lovelace
Ada Lovelace was the daughter of Lady Annabella Byron, who was deeplyinterested in mathematics, and Lord Byron. What would she have thought of theperson who's produced Engine code that draws a cat?
Ada Lovelace had had extensive mathematical training as a child. She first metBabbage in 1833, aged 17, and corresponded with him on mathematics and logic.Around 1841 Luigi Menabrae wrote a 'Sketch' of the Analytical Engine, describingits operation and how one might use it for a calculation. Lovelace was asked totranslate it into English; not only did she do that, but at Babbage's requestshe added her own extensive Notes, which went much further than Menabrae had.
Lovelace probably saw more in the Analytical Engine than Babbage himself had.She suggests, for example that it might act upon 'other things beside number',and that it might be possible to compose music by representing it in terms ofthe Engine's notation and operations. This jump from a mathematical engine toone that could act on symbols of any sort was visionary and well ahead of hertime.
The Notes, importantly, contained the first computer algorithm a series of stepsof operations to solve a particular (in this case mathematical) problem. This iswhat any computer program does, and is what makes Ada the first computerprogrammer, even if she was never able to run her program on a real machine.
Installing the Analytical Engine
Although no physical Analytical Engine exists (the Science Museum in London hasa working replica of the Difference engine), Fourmilab Switzerland have anemulator available. It runs on Java, so all you need to run it is a JDK.Download the emulator object code fromwww.fourmilab.ch/babbage/contents.html, unzip it, and type
java aescard.ae from that directory to run the card file
The emulator is the best guess, based on Babbage's drawings and papers over theyears, of how the Engine would have worked. You can also use it as an applet,for which you'll have to download and compile the source code, but we couldn'teasily get this to compile. The applet gives a more visual interface.
Basic operations and a first program
The Analytical Engine consisted of the Mill (where processing was done) and theStore (where numbers and intermediate results were held). The Store had 1000registers (a far bigger memory than the first 'real' computers had), and theMill could take in two numbers, conduct an operation on them, and output asingle number.
The Engine would also run a printing device for output, to avoid errors intranscription. It would be operated by punch cards, as were used in Jacquardlooms to weave complex patterns.
To use the emulator, then, we type in punch-card-type instructions to be run oneat a time. For ease, you can put any number of cards into a single text file.
There are three types of punch cards:
- Operation Cards Tell the Mill to add/subtract/multiply/divide, and can also move the chain of cards forwards or backwards (like a jump or loop instruction).
- Number Cards Supply numbers to the Store as necessary.
- Variable Cards Transfer values between the Mill and the Store.
For engineering reasons Babbage intended these to have three separate hoppers,but in the emulator they go in a single stream. (This is also how Menabrea andLovelace expressed their example programs.)
The emulator 'cards' also allow some flexibility in format. Numbers aren'tright-justified and there's no need for leading zeros, as there would be in areal punch card.
A number card looks like this:
This sets column 1 in the Store (which has 0-999 columns) to the value 3.
The Mill has two
Ingress Axes and an
Egress Axis (plus two auxiliary axesfor division, which we'll look at shortly). Once an operation is selected, theMill will keep doing that until another is selected.
The Operations cards are:
- x or *
- / or the divison sign
which all do what you'd expect.
Finally, the Variable Cards transfer things in and out of the Mill:
L: Transfer from Store to Mill Ingress Axis, leaving Store column intact.
Z: Transfer from Store to Mill Ingress Axis, zeroing Store column.
S: Transfer from Mill Egress Axis to Store column.
The letter is followed by a number specifying the Store column.
A program on the Analytical Engine consists of a chain of cards; each text linein an emulator file is a single card. You submit a card chain to the Attendant,who will check it for errors and 'requests for actions' (such as insertingmanually generated loops and subroutines). The chain of cards is then mounted onthe Engine and processed.
Let's give it a go! Since The Analytical Engine doesn't lend itself to
HelloWorld, we'll add 2 and 2.
Save this as
N000 2N001 2+L000L001S002P
This code puts 2 in column 0 of the Store, 2 in column 1 of the Store, sets theoperation to add, transfers column 1 and then column 2 to the Ingress Axes(whereupon the operation will be applied), then the result back to the Store incolumn 2.
P prints the result of the last operation to standard output. Run it with
javaaes card1.ae to see what happens.
The Analytical Engine emulator running a test card (in the Vim window), whichsubtracts 38888 from 0.
In fact, you could miss out the second line, and transfer the value from Storecolumn 0 twice, and it will automatically be transferred into both Ingress Axes.So this will work fine:
N000 2+. About to put values into MillL000L000S001P
Replacing the first
Z000 won't work, as this zeros the Storecolumn after transfer.
This card also includes a comment line. Comments begin with a space or a dot incolumn 1 of the card.
To do more operations, you need to replace both values on the Ingress Axes -they are discarded after their use in a computation. Each time two arguments goin, the current calcuation is applied.
Menabrae and simultaneous equations
Menabrae in his Sketch described an algorithm to solve a pair of simultaneousequations. He divided the process of solving the equations into a series ofindividual operations, and tabulated them as Analytical Engine operations.
This is handily arranged so that all the multiplications happen, then thesubtractions, then the divisions, minimising the number of Operations cards.
Let's translate this into Analytical Engine code. See the LV website for thewhole thing; I'll look at the structure and a couple of operations here.
Here are our sample equations:
2x + y = 73x - y = 8
First, we put all the numbers (2, 1, 7; 3, -1, 8) into the Store. Then,following Menabrae's calculations, cards 1-6 do all the multiplying and storethe results. Cards 7-9 are subtractions.
Then cards 10 and 11 generate and print the results. (I've described eachoperation as a 'card', as Lovelace does, although in the terms of the emulator,each line is a card.)
Card 10 - gives x value
Card 11 - gives y value
If you're debugging, it's useful to print at every step.
Division is a little more complicated than other operations. The format isroughly the same, but dividing uses the Primed Egress Output. Specifically, theremainder from the operation goes on the regular Egress Output, and the quotient(which is usually what you want) goes on the Primed Egress Output.
You get at this by using an apostrophe. (Very large numbers can also use thePrimed Ingress Axis.) Run this with
java aes simeqcard.ae and you should gettwo numbers output: 3 (the x value) and 1 (the y value).
The dividing shown works fine if you have integer results or only need integerprecision. But what if you want a greater precision?
The Analytical Engine uses fixed point arithmetic: like a slide rule, itcalculates only in whole numbers, and it is the programmer's responsibility tokeep track of decimal places.
So there is a "step up" and a "step down" operation, which shifts the decimalpoint either to the right (stepping up x times, or multiplying by 10x) or to theleft (stepping down, or dividing by 10x).
We just need to change the last two cards:
Card 10 - gives x value
Card 11 - gives y value
We must put the decimal point back in to the output ourselves, by manuallydividing by 100,000 (105).
Ada and the Bernoulli numbers
The most interesting part of Ada Lovelace's notes on the Menabrae paperdescribes how to calculate the Bernoulli numbers (a set of numbers of deepinterest to theoretical mathematicians) using the Engine.
Her diagram of the process is too complicated to reproduce here, but can be seen(with the rest of the Notes) at www.fourmilab.ch/babbage/sketch.html.
It can, however, be translated into code for the Analytical Engineemulator.Download the full code from the LV website; here we'll look at thestructure and ideas.
Ada Lovelace's equation for deriving the Bernoulli numbers.
The non-zero Bernoulli numbers are usually referred to by modern mathematiciansas B2, B4, B6, etc. However, Ada Lovelace refers to them as B1, B3, etc. I willrefer to them here by the modern numbers (so subtract one if you're comparingwith the Notes directly).
There are many ways to derive them, but the equation that Lovelace uses isshown, left. Note that the very last Bernoulli number has no accompanyingA-equation. What we're trying to calculate.
The important point is that from A2 onwards, each following A-value takes thepreceding one and multiplies by another two terms. This makes it possible toconstruct an iterative process to calculate each succeeding term.
Onwards then to the code!
Following Lovelace's diagram, we will put in an already-calculated version ofB2, B4, and B6, and will calculate B8, so
n is 4.
As Lovelace was keen to point out, in a 'real' calcuation the Engine itselfwould have already calculated these values on a previous round of the program,so they're stored in a later register.
The first section of the code, then, sets up our numbers. Register 3 holds our
n, and registers 21-23 the first 3 Bernoulli numbers, multiplied by 10,000 (toallow for later dividing, as discussed above).
Cards 1-6 calculate -1/2 x (2n - 1)/(2n + 1). The last three are the mostinteresting:
Card 4: (2n - 1) / (2n + 1)
Card 5: 1/2 * (2n - 1) / (2n + 1) Y
Card 6: -1/2 * (2n - 1) / (2n + 1) Y
In Card 4, we step the first value up 5 places before dividing, to avoid arounding error.
In Card 5, we take the value stored in the previous step and overwrite it, sinceit won't be needed again.
In Card 6, we take advantage of the fact that any unused register reads 0, toget a minus number by subtracting register 11 from zero. Effectively thisswitches the sign of the value in step 5, but we store this result in register13.
7 subtracts one from
n. This isn't used in the code as it stands, but it is anotional counter to keep track of whether we need to do another round ofcalcuation.
If we were calculating B2 (so n = 1), then card 7 would give the result 0, andwe would be done. Otherwise, it should add 1 to n and go round again.
Lovelace presupposed that the Analytical Engine would have a way of detecting aspecific result and acting accordingly. (The emulator provides an alternationcard to do exactly this.)
Steps 8-10 produce (2n / 2) * B2 (the latter being stored already).
Card 11 adds the value from the first stage (A0), and card 12 again checkswhether we're finished yet.
The intriguing part is the next stage, cards 13-23. This is the section thatcould be repeated almost exactly for any stage of the process, however manynumbers you wanted to calculate. What you need to calculate each time is:
2n . (2n - 1) . (2n - 2) ... / 2 . 3 . 4 ...
This is equivalent to
2n / 2 . (2n - 1)/3 . (2n - 2)/4 ...
The first time we go through the loop, when calculating A3, we can forget about2n / 2 as we already calculated that on card 9, and saved it in location 011.
So we work out 2n - 1 (card 13) and 2 + 1 (card 14), divide them and save theresult (card 15; note again that we step up 5 decimal places), and then multiplyit with A0 and save this new value in location 11.
We then repeat the exercise, with cards 17-20, with (2n - 2) / 4, multiply itwith the previous result, and overwrite location 011 again. So, once again, ourA-value is stored in location 11.
In card 21, we multiply with our pre-saved value for B4, then add the wholesequence up and save it in location 13. Card 23 once again checks for 0. At thispoint, all we need to do is to run cards 13-23 all over again.
Because we saved 2n - 2 as our 'new' 2n, in location 6, applying cards 13-16produces the result (2n - 4)/ 5, just as we want.
And the same again for cards 17-20, with (2n - 5) / 6 multiplied in this time.The only change is that in card 21, we have to grab B6 from its location ratherthan B4.
Then we add it all together again. In the code, these second-time-around cardsare labelled 13B-23B.
Card 13: 2n - 1 Y
Card 14: 2 + 1 Y
Card 15: (2n - 1) / (2 + 1)
Card 16: (2n / 2) * ((2n - 1) / 3) Y
Card 17: 2n - 2 Y
Card 18: 3 + 1 Y
Card 19: (2n - 2) / 4 Y
Card 20: (2n / 2) * (2n - 1)/3 * (2n - 2)/4 Y
Card 21: B(4) * [Card 20]
Card 22: A0 + B2A2 + B4A4 Y
There's only one new thing to notice, which is that in cards 20 and 21 we haveto step our result from the multiplication back down by five decimal places, aswe're multiplying two stepped-up values together.
The final step is 24, in which we add our saved value from step 23 to a zeroregister, to give our calculated Bernoulli number. In actual fact, we should besubtracting this from zero to get the sign of the number correct, but Lovelaceexplicitly chose to ignore this. Once the result is output, remember that you'llalso need to manually put in the decimal point, five places to the left. So ourresult is -0.03341.
This is not far off the 'official' -0.033333333. Try altering the accuracy ofour calculations (remember also to alter the accuracy of the stored Bernoullinumbers) to improve the accuracy of the result.
The Analytical Engine emulator also supports looping code, using conditional andunconditional cycle (backing) cards, and straightforward backing/advancingcards; and an if/then clause with the alternation card.
See the website for more details, and have a go at rewriting the provided codeto loop over one Bernoulli number at a time, up to a given n, generating theresult and storing it for the next loop around.
Remember that you'll need to calculate A0, A2, and B2 separately, as here (cards1-12), before you can get into the real 'loop' part. As the emulator is Turing-complete you can also, as Lovelace suggested, produce anything you can translateinto Engine-operations; or, as we now think of it, assembly language. In theoryyou could even write a compiler in Engine code
Tags: ada, ada-lovelace, analytical-engine, bernoulli, difference-engine, linux-voice, linux-voice-issue-1-2014, math, tutorials
Juliet Kemp is a scary polymath, and is the author of O'Reilly's Linux SystemAdministration Recipes