Note G is a computer algorithm written by Ada Lovelace that was designed to calculate Bernoulli numbers using the hypothetical analytical engine. Note G is generally agreed to be the first algorithm specifically for a computer,[1] [2] [3] and Lovelace is considered as the first computer programmer as a result.[4] [5] [6] The algorithm was the last note in a series labelled A to G, which she employed as visual aids to accompany her English translation of Luigi Menabrea's 1842 French transcription of Charles Babbage's lecture on the analytical engine at the University of Turin, "Notions sur la machine analytique de Charles Babbage" ("Elements of Charles Babbage’s Analytical Machine").[7] Lovelace's Note G was never tested, as the engine was never built. Her notes, along with her translation, were published in 1843.
In the modern era, thanks to more readily available computing equipment and programming resources, Lovelace's algorithm has since been tested, after being "translated" into modern programming languages. These tests have independently concluded that there was a bug in the script, due to a minor typographical error, rendering the algorithm in its original state unusable.[8] [9]
In 1840, Charles Babbage was invited to give a seminar in Turin on his analytical engine, the only public explanation he ever gave on the engine.[10] During Babbage's lecture, mathematician Luigi Menabrea wrote an account of the engine in French.[11] A friend of Babbage's, Charles Wheatstone, suggested that in order to contribute, Lovelace should translate Menabrea's account.[12] Babbage suggested that she augment the account with appendices, which she compiled at the end of her translation as a series of seven "notes" labelled A-G. Her translation was published in August 1843, in Taylor's Scientific Memoirs,[13] wherein Lovelace's name was signed "A.A.L". In these notes, Lovelace described the capabilities of Babbage's analytical engine if it were to be used for computing, laying out a more ambitious plan for the engine than even Babbage himself had.
Lovelace's notes for the article were three times longer than the article itself.[14] In the first notes, she explores beyond the numerical ambitions that Babbage had for the machine, and suggests the machine could take advantage of computation in order to deal with the realms of music, graphics,[15] and language.[16]
She explains to readers how the analytical engine was separate from Babbage's earlier difference engine, and likens its function to the Jacquard machine,[17] in that it used binary punch cards to denote machine language. In note C, this point is furthered by the fact that simultaneous and iterated actions can be made by the machine, ensuring that any card or collection of cards can be used several times in the solution of a single problem, essentially anticipating modern methods of control flow and looping.[18] These ideas were brought to a head in the final note, G, where Lovelace sought to demonstrate an example of computation.
Note G only made use of only the four arithmetical operations: addition, subtraction, multiplication and division, the implementation of Babbage's vision:
It also uses Babbage's idea of storing information in columns of discs, each denoted by
V
Lovelace used a recursive equation to calculate Bernoulli numbers, wherein she used the previous values in an equation to generate the next one. Her method ran thus:[19]
Bn=
| n-1 | |
| -\sum | |
| k=0 |
| n! | |
| (n+1-k)! ⋅ k! |
Bk=
| n-1 | |
| -\sum | |
| k=0 |
\binom{n}{k}
| Bk | |
| n+1-k |
where
\binom{n}{k}
\displaystyle\binom{n}{k}=
| n! | |
| k!(n-k)! |
Bernoulli numbers can be calculated in many ways, but Lovelace deliberately chose an elaborate method in order to demonstrate the power of the engine. In Note G, she states: "We will terminate these Notes by following up in detail the steps through which the engine could compute the Numbers of Bernoulli, this being (in the form in which we shall deduce it) a rather complicated example of its powers."[20] The particular algorithm used by Lovelace in Note G generates the eighth Bernoulli number (labelled as
B7
B0
The table of the algorithm organises each command in order. Each command denotes one operation being made on two terms. The second column states only the operator being used. Variables are notated as "
V
| 2V | |
| {} | |
| 4 |
V0
| 1V | |
| {} | |
| 2 |
x
| 1V | |
| {} | |
| 3 |
| 1V | |
| {} | |
| 2 |
x
| 1V | |
| {} | |
| 3 |
V4
V5
V6
Column 5 states whether either of the variables used in the operation of the command has been changed. Enclosed in curly braces, two rows per command put the original variable on the left side of an equals sign, and the new variable on the other side - that is, if the variable has been changed, its superscript is incremented by one, and if not, it remains the same. (e.g. line three assigns the result of
| 1V | |
| {} | |
| 5 |
+
| 1V | |
| {} | |
| 1 |
V5
| 1V | |
| \begin{Bmatrix}{} | |
| 5 |
=
| 2V | |
| {} | |
| 5 |
| 1V | |
| \ {} | |
| 1 |
=
| 1V | |
| {} | |
| 1 |
\end{Bmatrix}
V5
V1
In column 6, "Statement of Results", the result assigned to the variable in column 4 is shown in its exact value based on the values of the two terms previously assigned. (e.g. on line 1 -
| 1V | |
| {} | |
| 2 |
x
| 1V | |
| {} | |
| 3 |
V2
2
V3
n
| 1V | |
| {} | |
| 2 |
x
| 1V | |
| {} | |
| 3 |
=2n
A
B
B7
B7=-1(A0+B1A1+B3A3+B5A5)
Beyond this, each successive column shows the values of a given variable over time. Each time a variable either changes, or has its value become relevant by token of its presence as one of the terms in the current command, its value is stated or restated in its respective column. Otherwise, it is marked with an ellipsis to denote its irrelevancy. This presumably mimics the computer's need for only relevant information, thereby tracking the value of a variable as the program parses.
The program sought to calculate what is known by modern convention as the eighth Bernoulli number, listed as
B7
B0
In operation 4, the division supposedly taking place is "
| 2V | |
| {} | |
| 5 |
÷
| 2V | |
| {} | |
| 4 |
| 1V | |
| {} | |
| 11 |
| 2n-1 | |
| 2n+1 |
As a matter of fact, the division is the wrong way round;
2n-1
V4
2n+1
V5
| 2V | |
| {} | |
| 5 |
÷
| 2V | |
| {} | |
| 4 |
| 2V | |
| {} | |
| 4 |
÷
| 2V | |
| {} | |
| 5 |
-\tfrac{25621}{630}
Lovelace's program can be implemented in a modern programming language, though due to the above stated error, if transcribed exactly it would return an incorrect final value for
B7
V[1] = 1 V[2] = 2 V[3] = n (n = 4 in Lovelace's program.) V[4] = V[4] - V[1] V[5] = V[5] + V[1] V[11] = V[5] / V[4] V[11] = V[11] / V[2] V[13] = V[13] - V[11] V[10] = V[3] - V[1] V[7] = V[2] + V[7] V[11] = V[6] / V[7] V[12] = V[21] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[6] = V[6] - V[1] V[7]= V[1] + V[7] //Finish LaterThe implementation in pseudocode highlights the fact that computer languages define variables on a stack, which obviates the need for tracking and specifying the current iteration of a variable. In addition, Lovelace's program only allowed for variables to be defined by performing addition, subtraction, multiplication or division on two terms that were previously defined variables. Modern syntax would be capable of performing each calculation more concisely. This restriction becomes apparent in a few places, for example on command 6 (
V13=V13-V11
V13
0-V11
V7=V2+V7
V7
V2
V7