Welcome!

Once upon a time, computing was something that was done in a person’s mind, on paper, and with rudimentary calculating devices. But not too rudimentary! The abacus was a calculating tool that has been used since ancient times in China, Mesopotamia, Egypt, Greece, Rome, and Japan.

Image: Wikipedia

The abacas shown above is a “Bi-Quinary Abacus,” with two sections with ten columns of beads, top and bottom. In the top, there are two beads, which can be slid into three different positions – all three beads up, two up and one down, or both beads down. If a bead is down, it is counted, if it is up, it is not counted.

Beads in the top section each represent the number “5”. The bottom section columns each contain five beads, where some of the beads are up, and others are down. A bead is always either up or down. Each bead in the bottom section represents the number “1”. Beads are counted in the bottom section if they are up, and not counted if they are down.

The position of the column acts as a place value, in the same way that decimal numbers work. The right-most column is the 10^0 (“ones”) column. The next column to the left is the 10^1 (“tens”) column. The next column to the left is the 10^2 (“hundreds”) column. The rest of the columns continue in the same manner, with the left-most column representing the 10^9 (“billions”) column.

To determine what the abacus is set to, each column can be read directly, though there might be overflow into other columns, much like carrying in decimal. For now, let’s look at each column on the abacus above in order to see its value:

Starting from the left:

We can demonstrate the use of the abacus with the abacus simulator. Play around with the simulator to see how calculations work.

Don’t overthink the calculation! For each column, simply count the number of “down” beads in the top section and multiply by 5 (this will almost always be 0 or 1 beads, meaning either 0 or 5 count). Then add the number of “up” beads in the bottom section. The resulting value is the digit for the corresponding place in the number. If you only use up to a single bead in the top (5) and up to 4 beads in the bottom (4), then the total will always be between 0 and 9, and this determines the value of the column. Here is the table simplified a bit:

You can use both beads down from the top, which may produce a carry for a column. Indeed, a single bead down from the top and five beads from the bottom would also produce a carry.

For example, if the right-most column had 2 beads down in the top and 3 beads up in the bottom, that column would be equal to $(5 \times 2) + 3$, or $13$. But, this doesn’t fit into a single column (which must be 9 or lower), so the last column ends up with 3 and an extra 1 (really, 10) gets added to the next column. If the next column to the left had 0 beads down in the top and 2 beads up in the bottom, then that column would be $1 + 0 + 2$ or $3$, where the extra 1 came from the column to the right (the carry).

Challenge: Click on the button below, which produces a random 10-digit number. Then, set the abacus to that number by hand. Don’t use the “Set Abacus” input, and instead, click on the beads themselves to set the values.

The easiest way to set the number is to ignore the top bead in the top section. But, if you want a bigger challenge, try to use the top bead in a column (worth another 5) to carry to the next column, and try to set the same again with one or more carries.

Generate Number for Abacus:

What this seminar is about

The abacus was invented over four thousand years ago, which means that humans have been using machines to help them with numerical calculations for millenia. This seminar is going to introduce computing machines and (possibly more importantly) computing ideas that have brought us to our current state in the world, where computing is built in to our every-day lives.

Over the next six weeks, we are going to investigate the following topics:

1. Charles Babbage’s Computing machines from the 1800s, and Ada Lovelace, the “world’s first programmer”
2. Binary Representation and Logic Gates
3. Turing Machines, Uncomputable Functions, and P-vs-NP
4. Cryptography – how to send secure information
5. Networking – how computers communicate with each other
6. Artificial Intelligence

Don’t worry if you do not know what some of those topics mean – we will go over them in detail and explain why all of them are some of the many “great ideas in computer science!”

Let’s jump right in and discuss the first person to build a computing machine that performed more than simple addition: Charles Babbage.

Charles Babbage

• Charles Babbage was a mathematician, philosopher, inventor and mechanical engineer. He is one of the most fascinating figures in the history of computing.
• Captivated by the idea that he could produce mathematical tables “by steam,” Babbage designed two early computing machines—the Difference Engine and the vastly more powerful Analytical Engine—that anticipated many of the features found in modern computers.
• Neither machine was completed within Babbage’s lifetime. The Science Museum in London made a full-scale replica of the Difference Engine for the bicentennial of Babbage’s birth in 1991.

The Difference Engine Prototype

• Babbage completed a working model of his Difference Engine in 1832, which he had on display at his popular soirées in London.
• The machine was made of metal gears, and had a hand crank to perform one step at a time in a calculation. It was very cool looking!
• The machine was amazingly complex and was built to calculate with amazing precision:
  • The machine was over three meters long, and over two meters high
  • It can calculate and tabulate the result of any “7th order polynomial” (e.g., a 2nd order polynomial would be $x^2 + 5x + 1$
  • The machine could calculate results to 31 decimal places! It could represent numbers as big as $9,999,999,999,999,999,999,999,999,999,999$, which you would read as “Nine decillion, nine hundred ninety-nine nonillion, nine hundred ninety-nine octillion, nine hundred ninety-nine septillion, nine hundred ninety-nine sextillion, nine hundred ninety-nine quintillion, nine hundred ninety-nine quadrillion, nine hundred ninety-nine trillion, nine hundred ninety-nine billion, nine hundred ninety-nine million, nine hundred ninety-nine thousand, nine hundred ninety-nine”
• Babbage certainly thought big! The 31-digit precision was partly because he wanted to be able to make tables such as trigonometric and logarithmic tables, and having that much precision made the tables better. Also, Babbage was trying to impress the British Government and the Royal Astronomimcal Association, and this much precision would have done that.
• The machine printed a hard-copy of the output onto paper, and also printed a copy into soft material that you could make into a printing plate to print multiple copies.
• The model shown above was given to the London Science Museum by Babbage’s son.

How did the Babbage Difference Engine work, and what did it do?

• Babbage’s Difference Engine used the “method of finite differences” to calculate the results of polynomial expressions.

• Suppose you want to produce a table of squares:

• You can see that the second differences are constant ($2$). The values $0$, $1$, and $2$ (the left hand side of the calculation) can be used as input to Babbage’s Difference Engine, and every time the crank was used, it the next value would be calculated.

• We have a Difference Engine simulator that you can use to try out the difference engine. When you load the page, it is already initialized with $0$, $1$, and $2$. Try out the “Crank” button to see the table of squares calculation.

• What if we wanted to do the same thing for a table of cubes?

• We would thus seed the simulator with the values $0$, $1$, $6$, and $6$ and we would have our table of cubes.

• Mathematically, we are calculating this:

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

• To determine what we need to seed the machine with, we produce a simple table of values, calculating $y$ at each value:

• Once the differences stop changing, you can seed the machine. Above, the third difference is always $6$, so we know we can seed the machine with the first value of $f(x)$ (which is $0$), and the first, second, and third difference: $0$, $1$, $6$, $6$.

• How would you program the Difference Engine to calculate the terms in the sequence generated by the following polynomial:

$$f(x) = x^2 - 5x + 10$$

$x$	$f(x)$	first difference	second difference
$0$	$10$	$6 - 10 = -4$	$-2 - -4 = 2$
$1$	$6$	$4 - 6 = -2$	$0 - -2 = 2$
$2$	$4$	$4 - 4 = 0$	$2 - 0 = 2$
$3$	$4$	$6 - 4 = 2$	$4 - 2 = 2$
$4$	$6$	$10 - 6 = 4$
$5$	$10$

• Notice that the second difference is always $2$.
• We can therefore initialize the machine with $10$, $-4$, and $2$ and we can calculate subsequent values of the equation:

and after we crank the machine six times:

• If we wanted to get the machine to start the calculation on $x = 0$, we would have to do our calculation starting with $x = -1$:

$x$	$f(x)$	first difference	second difference
$-1$	$16$	$10 - 16 = -6$	$-4 - -6 = 2$
$0$	$10$	$6 - 10 = -4$	$-2 - -4 = 2$
$1$	$6$	$4 - 6 = -2$	$0 - -2 = 2$

• We can now seed the machine with $16$, $-6$, and $2$.

Trigonmetric Sines?

• Consider the following table, which shows the value of $\sin \theta$ for values of $\theta$ between $30\degree$ and $31\degree$ in increments of $0.1\degree$:

• How would you code this calculation on the Difference Engine?

Ada Lovelace

• Augusta Ada Byron, the daughter of the English poet Lord Byron and his wife Anne, was encouraged to pursue her interests in science and mathematics at a time when few women were allowed to study those subjects. At the age of 17, Ada met Charles Babbage and became fascinated by his machines. Ada was convinced of the potential of Babbage’s Analytical Engine and wrote extensive notes on its design, along with several complex mathematical programs that have led many people to characterize her as the first programmer. In 1980, the U.S. Department of Defense named the programming language Ada in her honor.

• This is a nice video about Ada Lovelace.

The Analitical Engine

• As Babbage built prototypes of his Difference Engine, he began to envision a much more powerful computing device he called the Analytical Engine.
• Babbage’s initial notes on the Analytical Engine appear in 1837, but the most complete description appears in a 1842 paper by Luigi Federico Menabrea, who was reporting on a lecture Babbage gave in 1840. Ada Lovelace (see below) translated Menabrea’s paper from French into English and provided notes that were three times longer than the original.
• The essential difference between the Difference Engine and the Analytical Engine is that the Analytical Engine was designed to be programmable, allowing users to perform any sequence of calculations. The programs were encoded on punched cards in the manner of the Jacquard loom, which Ada and her mother had seen in their visits to the English industrial areas.

The Jacquard Loom

• Video about the Jacquard Loom

• Here are some products of the Jacquard Loom (the first is an image of Jacquard himself!)

The the Analytical Engine simulator

To demonstrate Babbage’s Analytical Engine, we are going to use another simulator. The simulator models the analytical engine, though it does not have the 50-decimal digit precision that Babbage’s design had. It does, however, have the same functionality. There are two main parts to the machine, the mill and the store.

The Mill and Store:

Analytical Engine Deep Dive:

The Analytical Engine Details:

Computerphile video on the Analytical Engine:

The Store

• Each column holds a single integer as in the Difference Engine.
• Numbers in the Analytical Engine are signed.
• Each column has a numeric address: v0, v1, v2, v3, and so on.

• The op indicator holds the current operation (+, –, ×, ➗)
• The mill has five columns:
  • I1 and I2 are the input values 
  • E is the output value 
  • I1' and E' are used to store extra digits for the × and ➗ operations
  • The runup indicator is set when the result of an operation changes sign.

Instructions for the Analytical Engine

The first Load always puts the value loaded from memory into the I1 register. The second Load puts the value loaded from memory into the I2 register. On the second Load, the machine immediately preforms the operation and puts the output into the E register (or the E' register for overflow.

Here is a program to add two numbers:

N 0 25 # First number is in v0
N 1 17 # Second number is in v1
	
+      # Set machine for addition
L 0    # Load first number into I1
L 1    # A second load does the add
S 2    # Store result in v2
P 2    # Print the result

Challenge: Write an Analytical Engine program to multiply the numbers 123, 2, and 100 together and then print the output. See if you can do it using only two registers, v0 and v1. For a more advanced challeng, write the program to use only a single register!)

N 0 123
N 1 2
x # set the engine to multiply
L 0
L 1
S 0 # store 123 x 2 into register 0
N 1 100
L 0
L 1
S 1 # store the final result into register 1
P 1 

N 0 123
x
L 0
N 0 2
L 0 # do the multiplication
N 0 100
L 0
S 0 # store 123 x 2 into register 0
L 0
S 0 # store the final result into register 1
P 0 

Adding Control Operations

• When using the B, F, ?B, and ?F operations, it is important to note that because the line has already been read, going backwards by $n$ number of lines includes the line just read, and going forward $1$ line will jump over the instruction after the F instruction.

Let’s take a look at creating a program to calcuate a table of squares. We could do it in a similar wway to the difference engine, by calculating differences, but we can also use the multiplication operator, as well.

We want this output:

Here is a basic algorithm for the program:

• We need to be able to load a $1$ to use to add $1$ to a number, s we will save it in v0.
• We need to keep track of the number we are squaring. We will keep that number in v1.
• If we set the operator to multiply, and load the number we want to square twice, the square result will be put into the E register. We can save it and print it.
• We then increment our numeber to square by 1.
• We repeat the process all over for the new number.

N 0 1 # put a 1 in v0
x # set the engine to multiply
L 1 # load from v1
L 1 # load from v1 again, and multiply
S 2 # store the result in v2
P 2 # print the stored value
+ # set the machine to add
L 0 # Load the value 1 from v0
L 1 # Load from v1, and add
S 1 # store the incremented value to v1
B 10 # jump back to line 2

Challenge: Write an Analytical Engine program to print the numbers from 1 to 10, and then stop.

N 0 1
N 1 1 # the value 1 to use as a constant
N 2 11 # the counter to know when to stop
P 0
+
L 0
L 1
S 0 # now v0 has been incremented by 1
-
L 0
L 2
?B 9

Multiplication and Division

• Babbage recognized that multiplying two integers produces a result that typically has twice the number of digits that appear in the original values.
• To take account of this fact, the multiplication operation for the Analytical Engine produces its result in a pair of columns. Column E shows the low-order digits of the product, which are the digits on the right that include the units value. Column E′ shows the high-order digits.
• The division operation uses two columns to store the dividend. You set up the division by loading the low-order digits into column I1 and the high-order digits (if any) into column I1′ (to do this, use the L' address instruction). As long as you know that the numbers won’t exceed the number of digits in a column, you can ignore E′ and I1′ altogether. Many modern computers have similar functionality, though it is rarely used.

Here is an example program that utilizes the extended multiplication and division operations:

N 0 10000002 # 10 million and 2
N 1 20
x
L 0
L 1 # result is 200000040
    # E' should contain 2
    # E should contain 00000040
S' 2
S 3
P 2
P 3

# now let's reverse the process, and divide
# 200000040 by 20
/
L' 2
L 3
L 1
S 2
P 2

Challenge: Calculate Factorials with the Analytical Engine

• How would you program the Analytical Engine to calculate the factorial of a number supplied as data using a number card?

N 0 5 # the input number
N 1 1 # the output
N 2 1 # a 1 to use for subtraction
*
L 0
L 1 # multiply 
S 1
-
L 0
L 2 # decrement by 1
S 0
L 0
L 2
?F 1
B 12
P 1

What about decimal numbers?

• You might be wondering about how to use the analytical engine to calculate values that have decimals. For example, how would you calculate the area of a circle with radius 5? You need $\pi$, but you can’t have non-integer values on the machine!

• What we can do is to simply use what we call “fixed-point” arithmetic. We can create an integer value from $\pi$ by multiplying by a power of 10. For example, let’s say we wanted to multiply by $10,000$. As long as we keep track of the calculation and know to divide by $10,000$ after the calculation is complete (this just means moving the decimal place to the left by 5), we can perform the calculation:

N 0 5 # radius of 5
N 1 314159 # pi, scaled
*
L 0
L 0 # square the radius
S 0 # store back in v0
L 0
L 1 # multiple r^2 * pi
S 0 # store the result in v0
P 0

The output of the machine is:

07853975

and we can move the decimal place to the left by 5 to get 78.53975, which is the correct answer.

• But, what if we wanted to calculate the area if the radius was 5.23428? We could scale this, as well, but we would need the machine to have more digits – we can do this on our simultor!

• The simulator allows us to increase the number of digits up to 50 (Babbage’s original idea). Let’s increase it to 25 and run the following program:

N 0 523428 # radius of 5.23428, scaled
N 1 314159 # pi, scaled
*
L 0
L 0 # square the radius
S 0 # store back in v0
L 0
L 1 # multiple r^2 * pi
S 0 # store the result in v0
P 0

• We get the result:

0000000086072299874294256

• Because we scaled by $10^5$ three times in three multiplications, we need to shift our decimal place to the left 15 places to get the correct value:

86.072299874294256

• This level of precision is actually better than modern computers calculate on a regular basis!

Ada Lovelace’s First Program

• In 1842, Ada Lovelace wrote a program for the Analytical Engine, and it is the reason that she is considered “the world’s first programmer.”
• The program computes Bernoulli Numbers:

• Here is Lovelace’s description of the program:

• The program is tricky to understand (and has a bug!), but here is a great description of the program with some more history.

• Author Sydney Padua wrote a book, The Thrilling Adventures of Lovelace and Babbage: The (Mostly) True Story of the First Computer that tells the story as a graphic novel: