Lovelace's program for Bernouilli numbers

Description (MathML demo)

In 1842, Ada Lovelace published a program indented to be executed on Charles Babbage's analytical machine. This program is described in her note G and allows to calculate Bernouilli numbers. For that purpose, she relied on the following series: $$\frac{x}{e^x - 1} = 1 - \frac{x}{2} + {B_1\frac{{x^2}}{2}} + {B_3\frac{{x^4}}{4!}} + {B_5\frac{{x^6}}{6!}} + {B_7\frac{{x^8}}{8!}} + {B_9\frac{{x^10}}{10!}} + \cdots$$ where the coefficients $B_i$'s are the Bernouilli numbers, starting at $B_1 = \frac{1}{6}$.

For any integer $n \geq 1$, she considered the following recurrence relation: $$B_{2n-1} = -\left(A_{n,0} + \sum_{i=0}^{n-2} A_{n,2i+1}B_{2i+1}\right)$$ where $A_{n,0} = -\frac{1}{2}\frac{2n-1}{2n+1}$ and for each integer $0 < i < n$ $$A_{n,2i+1} = {\prod_{j=0}^{i-1} \frac{2n-j}{2+j}} = \frac{{2n} {(2n-1)} {(2n-2)} \ldots {(2n-i+1)}}{2 \cdot 3 \cdot 4 \cdot \ldots {(i+1)}}$$

Finally, she noted that $A_{n,1} = \frac{2n}{n}$ and used the following recurrence relation: $$A_{n,2(i+1)+1}=A_{n,2i+1} \times \frac{2n-i}{2+i}$$

Her famous program for $n=4$ is organized as follows:

1. $B_1, B_3, B_5$ have already been calculated and stored in result variables.
2. Operations 1-7 calculate $A_{n,0}$.
3. Operations 8-12 calculate $A_{n,1}$ and then $A_{n,0} + A_{n,1}B_1$.
4. Operations 13-23 are executed to calculate $A_{n,3}$ (using this recurrence relation) and then $A_{n,0} + A_{n,1}B_1 + A_{n,3}B_3$
5. Operations 13-23 are executed again to calculate $A_{n,5}$ (using the same recurrence relation) and then $A_{n,0} + A_{n,1}B_1 + A_{n,3}B_3 + A_{n,5}B_5$
6. Finally, operations 24-25 calculate $B_7$ (using this recurrence relation).

Additionally, she described how to generalize this algorithm using two loops (called "cycles" in the article):

• An outer one going over $n$ to successively calculate $B_1, B_3, B_5, B_7, \ldots, B_{2n-1}$ by repeating operations 1-25 (using this recurrence relation).
• An inner one to recursively calculate $A_{n,2i+1}$ (using this recurrence relation) as well as the fenced term from the above formula by repeating operations 13-23.

JavaScript Emulation (private class fields/methods demo)

The following JavaScript program emulates Ada Lovelace's program:

Input: $n$ = ; Output $B_{\mathrm{}}\approx$.

Perform invalid operations: ; Use private fields and methods: .

This program relies on a simple JavaScript class AnalyticalEngine that emulates some basic features of the analytical machine that one can guess from the article:

• Initialization: Enter an arbitrary number of variable cards and initialize them before execution.
• Execution:
  • Basic operations: calculate the sum, difference, product or quotient of two variables and put the result into a third variable.
  • Assignment: Copy the content of one variable into another variable.
  • Comparison: Test whether two variables are equal.
• Result retrieval: Read the values of the variable cards after execution.

Isolating the analytical engine into its own class makes sure one does not "cheat" by using JavaScript features that are not supported by the analytical engine. Still, it is not obvious how some of the features were implemented, in particular:

• Handling of conditionals and loops: This is mentioned in the article but no details are provided. The program of this page relies on JavaScript's if and while.
• Access to a variable whose index is described by another variable. This is necessary to read or set the result variables (the ones where Bernouilli numbers are stored) during the execution of the two loops because the variable index depends on the loop counter.

Note that earliest versions of JavaScript do not allow developers to hide the internal structure of their classes. If you enable the "perform invalid operations" option above, the index of some result variables will be calculated by directly getting and setting the values of the internal array of variables. The program still completes correctly but this is obviously something that was unlikely to be allowed by the analytical engine, if it had ever been built.

If you browser supports private class fields and methods, you can enable the "use private fields and methods" option and verify that the invalid operations above are now prohibited.