Note G

Note G is a computer algorithm traditionally attributed to Ada Lovelace that was designed to calculate Bernoulli numbers using the hypothetical analytical engine designed by Charles Babbage. The algorithm was the last note in a series labelled "A" to "G", which were employed as visual aids to accompany Lovelace's English translation of Luigi Menabrea's 1842 French transcription of Charles Babbage's only lecture on the analytical engine. Her translation, along with her substantial notes on the possibilities of the analytical engine, were published in 1843¹. In Babbage's 1864 memoir he discusses the creation of the various notes with Lovelace, including note "G". He provided the mathematical formulas for the calculation of the Bernoulli numbers, which Ada converted into a step-by-step table of instructions for the analytical engine; she also spotted a bug for him : Historians like Allan G. Bromley have noted several dozen sample programs prepared by Babbage between 1837 and 1840 (all substantially predating the illustrative notes), though they were never published and were substantially simpler , which has led to, in popular culture, Note G being generally considered to be the first algorithm specifically for a computer, and Lovelace is considered as the first computer programmer.…

Note G is a computer algorithm traditionally attributed to Ada Lovelace that was designed to calculate Bernoulli numbers using the hypothetical analytical engine designed by Charles Babbage. The algorithm was the last note in a series labelled "A" to "G", which were employed as visual aids to accompany Lovelace's English translation of Luigi Menabrea's 1842 French transcription of Charles Babbage's only lecture on the analytical engine. Her translation, along with her substantial notes on the possibilities of the analytical engine, were published in 1843. In Babbage's 1864 memoir he discusses the creation of the various notes with Lovelace, including note "G". He provided the mathematical formulas for the calculation of the Bernoulli numbers, which Ada converted into a step-by-step table of instructions for the analytical engine; she also spotted a bug for him : Historians like Allan G. Bromley have noted several dozen sample programs prepared by Babbage between 1837 and 1840 (all substantially predating the illustrative notes), though they were never published and were substantially simpler , which has led to, in popular culture, Note G being generally considered to be the first algorithm specifically for a computer, and Lovelace is considered as the first computer programmer. The program described in Note G was not tested in Babbage's or Lovelace's lifetime, as the analytical engine was never built. In the modern era, the algorithm has been tested using modern computing methods and revealed to have a software bug in it due to two variables being swapped in a division operation. B_n &= -\sum_{k=0}^{n-1} \frac{n!}{(n+1-k)!\cdot k!} B_k \\ &= -\sum_{k=0}^{n-1} \binom{n}{k} \frac{B_k}{n+1-k} \end{align} where \binom{n}{k} is a binomial coefficient, \displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} . Bernoulli numbers can be calculated in many ways, but the author deliberately chose an elaborate method in order to demonstrate the power of the engine. In Note G, Lovelace 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." The particular algorithm used in Note G generates the eighth Bernoulli number (labelled as B_7 , as it started with B_0 .) 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 ", where the superscript before it represents the amount of different values the variable has been assigned to, and the subscript after it represents the ordinal assignment of the variable, that is which variable it is. (For example, {}^2V_4 refers to the second assignment of variable number 4. Any variables hitherto undefined have a superscript of 0.) The variables are numbered starting from V_0 . The third column tells the computer exactly what command is taking place, (For example, on line 1, the command performed is " {}^1V_2 \times {}^1V_3 " - the first iteration of variable 2 is multiplied by the first iteration of variable 3.) and only incorporates one operation between two terms per line. Column 4 - "Variables receiving results" takes note of where the result of the operation in column 3 should be stored. In this way, any variables in this column have their superscript number incremented by one each time. (e.g. on line 1, the result of {}^1V_2 \times {}^1V_3 is assigned to variables V_4 , V_5 , and V_6 .) 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 to the second iteration of the variable V_5 , and the fifth column reflects this by noting; \begin{Bmatrix}{}^1V_5 = {}^2V_5 \\ {}^1V_1 = {}^1V_1 \end{Bmatrix} V_5 has changed, but V_1 hasn't. 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 \times {}^1V_3 - V_2 was set at the beginning to be 2 , and V_3 was set to be the variable n . Therefore, {}^1V_2 \times {}^1V_3 = 2n , in mathematical notation.) This column is ostensibly not computed by the engine, and appears to be more to aid clarity and the reader's ability to follow the steps of the program. (For example, line 5 has a fraction being divided by two, which is notated as it being multiplied by a half, probably for coherence and the typographical complexity of a nested fraction.) It also makes use of separate variable notation outside of the program, the A and B variables, which are multiplied successively to find the final value, B_7 , thus: B_7=-1(A_0+B_1A_1+B_3A_3+B_5A_5) 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. V[1] = 1 V[2] = 2 V[3] = n /* n = 4 in Lovelace's program. */ /* Start */ V[4], V[5], V[6] = V[2] * V[3] 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] /* Variables are initially zero, cf. below. */ 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] WHILE V[10] > 0: V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[8] = V[6] / V[7] V[11] = V[8] * V[11] V[6] = V[6] - V[1] V[7] = V[1] + V[7] V[9] = V[6] / V[7] V[11] = V[9] / V[11] V[12] = V[22] * V[11] V[13] = V[12] + V[13] V[10] = V[10] - V[1] V[24] = V[13] + V[24] V[3] = V[1] + V[3] The 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 as soon as in operation 6 ( V_{13} = V_{13}-V_{11} ). Here Lovelace defines a hitherto undefined variable ( V_{13} ) by itself, thereby assuming that all undefined variables are automatically equal to 0, where most modern programming languages would return an error. What she intended was " 0-V_{11} ", but had constrained herself to only using variables as terms. Likewise, in operation 8 ( V_7 = V_2 + V_7 ), the strict notation of two-term arithmetic becomes cumbersome, as in order to define V_7 as 2, Lovelace assigns its value (0) to itself plus V_2 (2). It is due to this restrictive notation that V_7 is defined thus.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369520548 under CC BY-SA 4.0; modifications have been made.