View source for Note G

{{Short description|Computer algorithm}}

[[File:Diagram_for_the_computation_of_Bernoulli_numbers.jpg|thumb|Note G, originally published in ''Sketch of The Analytical Engine Invented by Charles Babbage'']]
'''Note G'''{{efn|name=fullname|Fully titled "Diagram for the computation by the Engine of the Numbers of Bernoulli", but is [[Biology:Synecdoche|synecdochally]] known by "Note G"}} is a computer [[Algorithm|algorithm]] written by [[Biography:Ada Lovelace|Ada Lovelace]] that was designed to calculate Bernoulli numbers using the hypothetical [[Analytical engine|analytical engine]]. Note G is generally agreed to be the first algorithm specifically for a computer,<ref>{{Cite web |last=Demming |first=Anna |title=Ada Lovelace |url=https://www.newscientist.com/people/ada-lovelace/ |access-date=2022-06-01|website=New Scientist |language=en-US}}</ref><ref>{{Cite book |last=Krysa |first=Joasia |url=https://www.academia.edu/30945704 |title=Ada Lovelace - There Never was a Note G}}</ref><ref name=":6">{{Cite magazine |date=2013-10-15 |title=Ada Lovelace, the First Tech Visionary |url=http://www.newyorker.com/tech/elements/ada-lovelace-the-first-tech-visionary |access-date=2022-06-02 |magazine=The New Yorker |language=en-US}}</ref>{{Sfn|Hertz|2009|p=59}} and Lovelace is considered as the first [[Programmer|computer programmer]] as a result.<ref>{{Cite web |date=2009-03-27 |title=Celebrating Ada Lovelace: the 'world's first programmer' - Short Sharp Science - New Scientist |url=https://www.newscientist.com/blogs/shortsharpscience/2009/03/ada-lovelace-day.html |access-date=2022-06-01|archive-url=https://web.archive.org/web/20090327073325/https://www.newscientist.com/blogs/shortsharpscience/2009/03/ada-lovelace-day.html |archive-date=2009-03-27 }}</ref><ref name=":0">{{Cite web |title=Ada Lovelace {{!}} Babbage Engine {{!}} Computer History Museum |url=https://www.computerhistory.org/babbage/adalovelace/ |access-date=2022-06-01|website=www.computerhistory.org}}</ref><ref name=":5" /><ref name=":7">{{Cite web |date=2015-10-13 |title=Ada Lovelace: The First Computer Programmer |url=https://www.mentalfloss.com/article/53131/ada-lovelace-first-computer-programmer |access-date=2022-06-02 |website=Mental Floss |language=en-US}}</ref> 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 [[Social:French language|French]] transcription of Charles Babbage's lecture on the analytical engine at the [[Organization:University of Turin|University of Turin]], "Notions sur la machine analytique de Charles Babbage" ("Elements of Charles Babbage’s Analytical Machine").<ref name=":5">{{Cite web |title=Ada Lovelace {{!}} Biography, Computer, & Facts |url=https://www.britannica.com/biography/Ada-Lovelace |access-date=2022-06-01|website=Encyclopedia Britannica |language=en}}</ref>{{Sfn|Stein|1984|p=44}} Lovelace's Note G was never tested, as the engine was never built. Her notes, along with her translation, were published in 1843.<ref name=":0" /><ref name=":5" />

In the [[History:Modern era|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 [[Software bug|bug]] in the script, due to a minor typographical error, rendering the algorithm in its original state unusable.<ref name=":11">{{Cite web |title=What Did Ada Lovelace's Program Actually Do? |url=https://twobithistory.org/2018/08/18/ada-lovelace-note-g.html |access-date=2022-06-01|website=twobithistory.org}}</ref><ref>{{Cite web |title=Ada Lovelace and the Story of Note G |url=https://www.nycmedialab.org/innovationmonitor/ada-lovelace-and-the-story-of-note-g |access-date=2022-06-01|website=NYC Media Lab |language=en-US}}</ref>

== Origin ==
[[File:Ada Lovelace portrait.jpg|alt=Ada Lovelace|thumb|Ada Lovelace]]
In 1840, Charles Babbage was invited to give a seminar in [[Place:Turin|Turin]] on his analytical engine,<ref name=":2" /> the only public explanation he ever gave on the engine.<ref name=":1">{{Cite magazine |title=Charles Babbage left a computer program in Turin in 1840. Here it is. |language=en-US |magazine=Wired |url=https://www.wired.com/beyond-the-beyond/2017/05/charles-babbage-left-computer-program-turin-1840/ |access-date=2022-06-01|issn=1059-1028}}</ref> During Babbage's lecture, mathematician Luigi Menabrea wrote an account of the engine in French.<ref name=":2">{{Cite web |title=How Ada Lovelace's notes on the Analytical Engine created the first computer program |url=https://www.sciencefocus.com/future-technology/how-ada-lovelaces-notes-on-the-analytical-engine-created-the-first-computer-program/ |access-date=2022-06-01|website=BBC Science Focus Magazine |language=en}}</ref> A friend of Babbage's, [[Biography:Charles Wheatstone|Charles Wheatstone]], suggested that in order to contribute, Lovelace should translate Menabrea's account.<ref name=":2" /><ref name=":4">{{Cite web |title=Mathematical Treasure: Ada Lovelace's Notes on the Analytic Engine {{!}} Mathematical Association of America |url=https://www.maa.org/press/periodicals/convergence/mathematical-treasure-ada-lovelaces-notes-on-the-analytic-engine |access-date=2022-06-02 |website=www.maa.org}}</ref> 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,<ref name=":2" /> in Taylor's Scientific Memoirs,<ref name=":4" /><ref name=":3">[https://www.scss.tcd.ie/coghlan/repository/J_Byrne/A_Lovelace/J_Fuegi_&_J_Francis_2003.pdf Lovelace & Babbage and the Creation of the 1843 ‘Notes’]</ref> wherein Lovelace's name was signed "A.A.L".<ref name=":2" />{{efn|name=misprint|In the memoir, her initials were misprinted as "A. L. L."<ref name=":4" />}} 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.<ref name=":6" /><ref name=":3" />{{Sfn|Stein|1984|p=46}}

Lovelace's notes for the article were three times longer than the article itself.<ref name=":9">{{Cite web |last= |first= |date=April 2, 2014 |title=Ada Lovelace |url=https://www.biography.com/scholar/ada-lovelace |access-date=2022-06-02 |website=Biography |language=en-us}}</ref> 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,<ref>{{Cite ODNB |last=Toole |first=Betty Alexandra |url=http://www.oxforddnb.com/view/10.1093/ref:odnb/9780198614128.001.0001/odnb-9780198614128-e-37253 |title=Byron, (Augusta) Ada [married name (Augusta) Ada King, countess of Lovelace] (1815–1852), mathematician and computer pioneer |date=2004-09-23 |volume=1 |language=en |doi=10.1093/ref:odnb/37253|isbn=978-0-19-861412-8 }}</ref> and language.<ref name=":7" /><ref>{{Cite web |title=Ada Lovelace - Biography, Facts and Pictures |url=https://www.famousscientists.org/ada-lovelace/ |access-date=2022-06-02 |language=en-US}}</ref><ref name=":8" />

{{Blockquote|text=Again, it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine. Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.|author=Ada Lovelace|title=Notes upon the memoir "Sketch of The Analytical Engine Invented by Charles Babbage" by the translator Ada Augusta, Countess of Lovelace|source=Note A}}

She explains to readers how the analytical engine was separate from Babbage's earlier [[Difference engine|difference engine]],{{Sfn|Woolley|1999}} and likens its function to the [[History:Jacquard machine|Jacquard machine]],<ref>{{Cite web |date=2016-10-11 |title=Celebrating Ada Lovelace |url=https://mitpress.mit.edu/blog/celebrating-ada-lovelace |access-date=2022-06-02 |publisher=MIT Press |language=en}}</ref> in that it used binary [[Engineering:Punched card|punch cards]] to denote [[Machine code|machine language]]. In note C, this point is furthered by the fact that simultaneous and [[Iteration|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,<ref name=":8" /> essentially anticipating modern methods of [[Control flow|control flow]] and looping.<ref name=":9" /><ref>{{Cite web |date=2021-02-26 |title=Ada Lovelace |url=https://kids.nationalgeographic.com/history/article/ada-lovelace |access-date=2022-06-02 |website=History |language=en}}</ref> These ideas were brought to a head in the final note, G, where Lovelace sought to demonstrate an example of [[Computation|computation]].

Note G only made use of only the four [[Arithmetic|arithmetical operations]]: addition, subtraction, multiplication and division, the implementation of Babbage's vision:

{{Blockquote|text=Under the impossibility of my here explaining the process through which this end is attained, we must limit ourselves to admitting that the first four operations of arithmetic, that is addition, subtraction, multiplication and division, can be performed in a direct manner through the intervention of the machine. This granted, the machine is thence capable of performing every species of numerical calculation, for all such calculations ultimately resolve themselves into the four operations we have just named.|author=Charles Babbage|title="Sketch of The Analytical Engine Invented by Charles Babbage"|source=}}It also uses Babbage's idea of storing information in columns of discs, each denoted by <math>V</math> (for [[Variable (computer science)|variable]]) and a subscript number denoting which column is being referred to.

== Function ==
Lovelace used a [[Recurrence relation|recursive equation]] to calculate Bernoulli numbers,<ref name=":2" /> wherein she used the previous values in an equation to generate the next one. her method ran thus:<ref name=":10">{{Cite web |title=Ada Lovelace's Note G {{!}} Project Lovelace |url=https://projectlovelace.net/problems/ada-lovelaces-note-g/ |access-date=2022-06-01|website=projectlovelace.net}}</ref>

:<math>B_n = -\sum_{k=0}^{n-1} \frac{n!}{(n+1-k)!\cdot k!} </math>

:<math>B_k = -\sum_{k=0}^{n-1} \binom{n}{k} \frac{B_k}{n+1-k}</math>

where <math>\binom{n}{k}</math> is a [[Binomial coefficient|binomial coefficient]], 
:<math>\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}</math>.

Bernoulli numbers can be calculated [[Bernoulli number#Definitions|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."<ref name=":8">{{Cite web |title=Sketch of The Analytical Engine |url=https://www.fourmilab.ch/babbage/sketch.html |access-date=2022-06-02 |website=www.fourmilab.ch}}</ref> The particular algorithm used by Lovelace in Note G generates the eighth Bernoulli number (labelled as <math>B_7</math>, as she started with <math>B_0</math>.)<ref name=":10" />

=== Notation ===
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. [[Variable (computer science)|Variables]] are notated as "<math>V</math>",{{efn|name=variableclarification|These variables technically refer to columns of discs, at Babbage's suggestion that that is how they ought to be notated.<ref name=":8" />}} 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, <math>^2V_4</math> refers to the second assignment of variable number 4. Any variables hitherto undefined have a superscript of 0.) The variables are numbered starting from <math>V_0</math>. The third column tells the computer exactly what command is taking place, (For example, on line 1, the command performed is "<math>^1V_2 \times ^1V_3</math>" - 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 <span style="font-family:Times New Roman;"><strong><math>^1V_2 \times ^1V_3</math></strong></span> is assigned to variables <math>V_4</math>, <math>V_5</math>, and <math>V_6</math>.)

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 <math>^1V_5+^1V_1</math> to the second iteration of the variable <math>V_5</math>, and the fifth column reflects this by noting;

:<math>\begin{Bmatrix}^1V_5 = ^2V_5 \\ ^1V_1 = ^1V_1 \end{Bmatrix}</math>

<math>V_5</math> has changed, but <math>V_1</math> 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 - <math>^1V_2 \times ^1V_3</math> - <math>V_2</math> was set at the beginning to be <math>2</math>, and <math>V_3</math> was set to be the [[Variable (mathematics)|variable]] <math>n</math>. Therefore, <math>^1V_2 \times ^1V_3=2n</math>, in [[Mathematical notation|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 <math>A</math> and <math>B</math> variables, which are multiplied successively to find the final value, <math>B_7</math>, thus:<ref name=":11" />

:<math>B_7=-1(A_0+B_1A_1+B_3A_3+B_5A_5)</math>

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|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 [[Parsing|parses]].<ref name=":11" />

=== Method ===
The program sought to calculate what is known by modern convention as the eighth Bernoulli number, listed as <math>B_7</math>, as Lovelace [[Zero-based numbering|begins counting from]] <math>B_0</math>.<ref name=":10" />

=== Error ===
In operation 4, the division supposedly taking place is "<math>^2V_5 \div ^2V_4</math>", to be stored in variable <math>^1V_{11}</math>. However, the "Statement of results" says that the division should be:

:<math>\frac{2n-1}{2n+1}</math>

As a matter of fact, the division is the wrong way round; <math>2n-1</math> is the second iteration of <math>V_4</math>, as can be seen in operation 2. Likewise, <math>2n+1</math> is the second iteration of <math>V_5</math>, as can be seen in operation 3. Thus, operation 4 should not be <math>^2V_5 \div ^2V_4</math>, but rather <math>^2V_4 \div ^2V_5</math>. This bug means that if the engine were ever to run this algorithm in this state, it would fail to generate Bernoulli numbers correctly, and would find its final goal value {{pars|s=150%|the eighth Bernoulli number, <math>-\tfrac{1}{30}</math>}} to be <math>-\tfrac{25621}{630}</math>.

=== Modern implementations ===
Lovelace's program can be implemented in a modern [[Programming language|programming language]], though due to the above stated error, if transcribed exactly it would return an incorrect final value for <math>B_7</math>. The original program generalised in [[Pseudocode|pseudocode]] follows as thus:
<pre>
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 Later
</pre>
The implementation in pseudocode highlights the fact that computer languages define variables on a [[Stack (abstract data type)|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|addition]], [[Subtraction|subtraction]], [[Multiplication|multiplication]] or [[Division (mathematics)|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 (<math>V_{13} = V_{13}-V_{11}</math>). Here Lovelace defines a hitherto undefined variable (<math>V_{13}</math>) by itself, thereby assuming that all undefined variables are automatically equal to 0, where most modern programming languages would return an error or list the variable as [[Null pointer|null]]. What she intended was "<math>0-V_{11}</math>", but had constrained herself to only using variables as terms. Likewise, in command 8 (<math>V_7 = V_2 + V_7</math>), the strict notation of two-term arithmetic becomes cumbersome, as in order to define <math>V_7</math> as 2, Lovelace assigns its value (0) to itself plus <math>V_2</math> (2). It is due to this restrictive notation that <math>V_7</math> is defined thus.

== Notes ==
{{reflist|group=lower-alpha}}

== References ==
{{Reflist}}

== Sources ==
{{Refbegin}}
* {{Cite journal |last=Stein |first=Dorothy K. |date=1984 |title=Lady Lovelace's Notes: Technical Text and Cultural Context |url=https://www.jstor.org/stable/3826758 |journal=Victorian Studies |volume=28 |issue=1 |pages=33–67 |jstor=3826758 |issn=0042-5222}}
* {{Citation | last=Woolley | first=Benjamin |date=February 1999 | title= The Bride of Science: Romance, Reason, and Byron's Daughter | publisher = Pan Macmillan | place = AU | url= https://books.google.com/books?id=K8-sQgAACAAJ | access-date= 7 April 2013 | isbn = 978-0-333-72436-1}}
* {{Cite journal |last=Hertz |first=Paul |date=2009 |title=Art, Code, and the Engine of Change |url=https://www.jstor.org/stable/40598953 |journal=Art Journal |volume=68 |issue=1 |pages=58–75 |doi=10.1080/00043249.2009.10791336 |jstor=40598953 |s2cid=194010431 |issn=0004-3249}}
{{Refend}}

[[Category:Algorithms]]

{{Sourceattribution|Note G}}