In this post we will focus on a very specific algorithm called the Note G algorithm, written in 1843 by Ada Lovelace. Born in 1815, Ada Lovelace is celebrated as a visionary whose work laid the groundwork for modern computing. Among her most notable contributions is the Note-G algorithm, widely regarded as the first computer algorithm, even though the machine it was designed for—the Analytical Engine—was never built.
The Analytical Engine: A Vision Ahead of Its Time
The Analytical Engine was a mechanical general-purpose computer proposed by Charles Babbage. Although it remained a theoretical construct, the engine’s design was revolutionary. It was intended to perform complex calculations and could be programmed using punched cards, a concept that would later influence the development of early computers.
The Note-G Algorithm: The First of Its Kind
Ada Lovelace’s Note-G algorithm was designed to be implemented on the Analytical Engine. The algorithm was part of her translation and expansion of an Italian article on the engine, where she detailed how the machine could compute Bernoulli numbers. This work is significant because it represents the first explicit description of a step-by-step process for a machine to perform a complex calculation—the essence of what we now call an algorithm.
Diagram of an algorithm for the Analytical Engine for the computation of Bernoulli numbers, from Sketch of The Analytical Engine Invented by Charles Babbage by Luigi Menabrea with notes by Ada Lovelace
Bernoulli Numbers?
For those unfamiliar with the term, Bernoulli numbers are a sequence of rational numbers with deep connections to number theory. They appear in various areas of mathematics, including the expansion of trigonometric functions and the calculation of sums of powers of integers. The sequence starts with B₀ = 1, B₁ = -1/2, B₂ = 1/6, and so on, with each number defined by a specific recursive formula.
Lovelace’s algorithm to compute these numbers was ground breaking because it demonstrated that a machine could perform tasks that went beyond simple arithmetic, showcasing the potential for automated computation.
Testing the Note-G Algorithm
Let’s use our Analytical Engine emulator to test Ada Lovelace’s algorithm. The algorithm provided below is a direct translation of Ada Lovelace’s algorithm (See picture above). It is used to calculate Bernoulli Number 7( B7).
To work out the value of B7, the algorithms relies on the values of B1, B3 and B5.
| Bj | Fraction | Decimal |
| B1 | 1/6 | +0.166666666 |
| B3 | −1/30 | −0.033333333 |
| B5 | 1/42 | +0.023809523 |
As the Store of the analytical engine can only store integer values (whole numbers with no decimal), we are shifting the values being calculated by 12 digits.
For instance the output of our program should be read as follows: B7 = -33333333336 x 10-12 = 0.033333333336 ≈ -1/30
Charles Babbage’s Analytical Engine SimulatorOpen in new tab/window
Code Explanation
To transpose Ada Lovelace’s Note G algorithm into a set of cards/instructions to be processed by the analytical engine the program will first need to loads some values in the store using Number cards (N). (You can check at the end of this post for a full list of instructions that can be processed by the Analytical Engine emulator.)
N1 1 N2 2 N3 4 .Bernoulli numbers shifted by 12 digits N21 166666666667 N22 -33333333333 N23 23809523809 N24 0
Then the Note G algorithms contains 25 arithmetic operations clearly described on Ada Lovelace’s note provided below. Let’s look at the first operation:
For instance the first operation is a multiplication of variable V2 and V3. V stands for variable, each variable being stored using one column of the store. e.g. V2 refers to the 2nd column of the store. As indicated the result of this operation will be stored three times in column V4, V5 and V6.
This is how this operation would be coded using punched cards:
X .Load operation card for multiplication L2 .Load V2 (=2) L3 .Load V3 (=4) S4 .Store the result of V2xV3 = 2x4 = 8 in column 4 (V4) S5 .Store the result in column 5 (V5) S6 .Store the result in column 6 (V6)
We can now move to the next operation in the algorithm which is a subtraction:
With this operation we are subtracting V1 from V4 and storing the result in V4. (V4 = V4 – V1).This is how this operation would be coded using punched cards:
- .Load operation card for subtraction Z4 .Load V4 (=8) (and reset the column to 0) L1 .Load V3 (=1) S4 .Store the result of V4-V1 = 8-1 = 7 in column 4 (V4)
We can use this approach to transpose all 25 operations using the relevant punched cards. You can see the result in the emulator and use it to test the Note-G algorithm.
Full Code for Ada Lovelace’s Note G Algorithm:
.Note-G Algorithm .An algorithm to calculate Bernoulli Number B7 (-1/30) .Based on Ada Lovelace's Note - G algorithm N1 1 N2 2 N3 4 .Bernoulli numbers shifted by 12 digits N21 166666666667 .B1 N22 -33333333333 .B3 N23 23809523809 .B5 N24 0 .B7 .1 X L2 L3 S4 S5 S6 .2 - Z4 L1 S4 .3 + Z5 L1 S5 .4 / Z4 <12 Z5 S11' .5 Z11 L2 S11' .6 - Z13 Z11 S13 .7 L3 L1 S10 .8 + L2 Z7 S7 .9 / L6 <12 L7 S11' .10 X L21 L11 S12 L12 >12 L1 S12 .11 + Z12 Z13 S13 .12 - Z10 L1 S10 .13 - Z6 L1 S6 .14 + L1 Z7 S7 .15 / L6 <12 L7 S8' .16 X Z8 Z11 S11 L11 >12 L1 S11 .17 - Z6 L1 S6 .18 + L1 Z7 S7 .19 / L6 <12 L7 S9' .20 X Z9 Z11 S11 L11 >12 L1 S11 .21 X L22 L11 S12 L12 >12 L1 S12 .22 + Z12 Z13 S13 .23 - Z10 L1 S10 .13 -REPEAT- - Z6 L1 S6 .14 + L1 Z7 S7 .15 / L6 <12 L7 S8' .16 X Z8 Z11 S11 L11 >12 L1 S11 .17 - Z6 L1 S6 .18 + L1 Z7 S7 .19 / L6 <12 L7 S9' .20 X Z9 Z11 S11 L11 >12 L1 S11 .21 X L23 L11 S12 L12 >12 L1 S12 .22 + Z12 Z13 S13 .23 - Z10 L1 S10 .24 - Z24 L13 S24 P .25 L1 Z3 S3 Z6 Z7 B HCharles Babbage’s Analytical Engine SimulatorOpen in new tab/window
Analytical Engine Instruction Set
The table below describes the different instructions/punched cards the analytical engine would have been able to process:
| Opcode | Instruction | Example | Description |
| N | Number | N1 5 | Used to store a given number (e.g. 5) in the store at a specific location (e.g. 1) |
| L | Load | L2 | Load a value from the store, at a specified location (e.g. 2) to the Mill Ingress axis, leaving the store column unchanged. |
| Z | Load | Z2 | Load a value from the store, at a specified location/column (e.g. 2) to the Mill Ingress axis, resetting the store column to 0. |
| S | Save | S2 | Store the value currently in the Mill Egress axis to a given location/column in the Store. |
| + | Add | + | Add the values in the two Ingress Axes (ignoring the contents of the Primed Ingress Axis), and the result of this addition is stored in the Egress Axis. |
| – | Subtract | – | Subtract the values in the two Ingress Axes (ignoring the contents of the Primed Ingress Axis), and the result of this subtraction is stored in the Egress Axis. |
| x | Multiply | – | Multiply the values in the two Ingress Axes (ignoring the contents of the Primed Ingress Axis), and the result of this multiplication is stored in the Egress Axis. |
| / | Divide | / | The value in the first Ingress Axis is divided by the value in the second Ingress Axis. The quotient is placed on the Primed Egress Axis and the remainder on the Egress Axis. |
| < | Step up | <6 | Step up (left right) by n digits in the Ingress Axis. e.g. <3 to multiply the Ingress value by 1,000. |
| > | Step down | >6 | Step down (shift right) by n digits in the Ingress Axis. e.g. >3 to divide the Ingress value by 1,000. |
| CB+ | Back Always | CB+7 | To skip backward (and repeat) a given number of cards in the reader. |
| CB? | Back only if run-up lever is set | CB?7 | To skip backward (and repeat) a given number of cards in the reader if run-up lever is set. |
| CF+ | Forward Always | CF+7 | To skip forward a given number of cards in the reader. |
| CF? | Forward only if run-up lever is set | CF?7 | To skip forward a given number of cards in the reader if run-up lever is set. |
| P | P | Print the value on the mill axis that the most recent operation most recently modified (e.g. the Mill Egress axis after an arithmetic operation, the Ingress axis after a L instruction, etc.). | |
| B | Bell | B | Ring the bell to get the attention of the engine attendant. |
| H | Halt | H | Stop the engine. Stop the execution of the program. |
Read More…
Check the following two blog posts:
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE