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: xex-1=1-x2+B1x22+B3x44!+B5x66!+B7x88!+B9x1010!+\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 Bi's are the Bernouilli numbers, starting at B1=16B_1 = \frac{1}{6}.

For any integer n1n \geq 1, she considered the following recurrence relation: B2n-1=-(An,0+i=0n-2An,2i+1B2i+1)B_{2n-1} = -\left(A_{n,0} + \sum_{i=0}^{n-2} A_{n,2i+1}B_{2i+1}\right) where An,0=-122n-12n+1A_{n,0} = -\frac{1}{2}\frac{2n-1}{2n+1} and for each integer 0<i<n0 < i < n An,2i+1=j=0i-12n-j2+j=2n(2n-1)(2n-2)(2n-i+1)234(i+1)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 An,1=2nnA_{n,1} = \frac{2n}{n} and used the following recurrence relation: An,2(i+1)+1=An,2i+1×2n-i2+iA_{n,2(i+1)+1}=A_{n,2i+1} \times \frac{2n-i}{2+i}

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

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

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

JavaScript Emulation (private class fields/methods demo)

The following JavaScript program emulates Ada Lovelace's program:

Input: n = ; Output B.

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:

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:

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.