9 Jul 2019

Carry: Babbage's Engines

Yesterday's post Carry: From Logarithms to Mechanical Calculators talked about how carrying was done in the mechanical and electromechanical calculators of my youth. The most famous mechanical calculators ever designed have to be Charles Babbage's Difference Engine and Analytical Engine. Of course, Babbage had to solve the carry problem for these machines, too.

The Difference Engine

The motivation for building and financing Babbage's difference engine was those log tables I mentioned in yesterday's post. They had to be generated, and they were notoriously difficult to get right. Calculating them was very boring and error-prone. Other tables, such as sines and cosines, or astronomical tables, suffered from the same problem. The difference engine was created to automatically calculate the values of the tables, and to avoid transcription errors, it actually had a printer, too. This actually created not just a printout but a printing plate that could be used in a press to print the books of tables.

For the anniversary of Babbage's birth, the Science Museum in London built a difference engine from the original plans to see if it worked. It did. If you visit and are lucky, you might see it being operated. I visited and took the above photo, but it wasn't my lucky day and it was not being operated (by hand, it has a huge crank).

Nathan Myhrvold, the ex-CTO of Microsoft, decided he wanted one, too, and funded the construction of the printer, which actually has more parts than the engine itself. In return, the Science Museum built him a second one (and a printer, of course). It was in the lobby of the Computer History Museum in Mountain View for a time and I saw it operating there. It's impressive. Apparently, it is now in the lobby of his company Intellectual Ventures in Seattle.

The difference engine used 20 digit numbers. One of the most complicated parts of it is the carry mechanism. It used ripple carry like the adding machine in the video in yesterday's post. If a digit rolls from 9 to 0, it sets a trigger, and in the carry phase of the operation, it will add 1 in the next position. This, in turn, might set the trigger for the next digit, too. With twenty digits, it took a lot of precision engineering for the carry to ripple from the units wheel all the way to the 20th wheel in a single rotation of the carry mechanism. That's the problem with ripple carry, the worst case is very slow.

Here's a video that will tell you more than you want to know about how the difference engine carry worked:

The Analytical Engine

Babbage moved on to the Analytical Engine. If it had been built, this would have been the first programmable digital computer, albeit built out of brass gears and powered by a steam engine. But it had the idea of a program, even stored on the punched cards used to hold the pattern for automatic looms. It had memory, loops, and conditionals, the basic building blocks of any processor even today. It would also have been totally impossible to program in practice, requiring three sets of coordinated punched cards, one to load data, one to move data, and one to set the calculations.

Famously, the first person to work out how to program this beast was Ada Lovelace. Since the engine was never built, she never had to discover how many mistakes she had in her program, like Maurice Wilkes famously did when they first started to try and program EDSAC at Cambridge. Ada Lovelace Day is the second Tuesday in October, so maybe I'll cover her accomplishments that day, unless Cadence has a major announcement I have to cover.

The Analytical Engine used 50 digit numbers. Babbage realized that ripple carry would be very slow and unreliable. So he designed what he called the "anticipating carriage." He considered it his proudest achievement. He said it was:

teaching the Engine to foresee, and to act on that foresight.

If a wheel is on 9 and a carry occurred, then it was not only that wheel that needed to be incremented by 1, but also the next one. That's how carry worked. But when there were lots of 9s in a row, he wanted a mechanisim to increment them all simultaneously, not require the carry to ripple from one digit to the next. Mechanical rods moved into place so that in the worst case of adding 1 to 99999 (with up to 50 nines), the machine would immediately select the correct wheel to add 1 to without waiting for the carries to be performed on all the intermediate wheels. This meant that the time to do the carry was constant and didn't require 50 wheels to be handled one after the other. Instead of a ripple carry, this was what today we'd call a carry-lookahead adder.

Here's a video of how the anticipating carry works:

You might think that electronics is so fast that handling carries in a clever manner is no longer required. Tomorrow, we'll look into that.

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.

Tags:

Breakfast Bytes Blogs

Carry: Babbage's Engines

The Difference Engine

The Analytical Engine