What did Ada Lovelace compute?

Primary tabs

Today is Ada Lovelace day, a day to celebrate the achievements of women in Science and Technology.

Countess Lovelace is credited with writing the first computer program, for Charles Babbage's Analytical Engine, a computer that was never built. Poor estimation, scope creep, bad project management,... you know the story. It's been with us since day one!

I thought it would be interesting to have a look at what Ada Lovelace actually computed...

A transcription of Ada's notes, originally published around 1843, can be found here: http://www.fourmilab.ch/babbage/sketch.html

In this, she considers the computational potential of the Analytical engine, including the possibility of integrating and differentiating functions numerically, and in certain cases, symbolically. This is a truly remarkable leap of understanding - one that would not see a full implementation and dissemination into the mainstream of computation and mathematics until well over a hundred years later.

She closes with a detailed description of the computation of Bernoulli numbers, remarking that there are many identities which define them, and choosing a particular one as the basis for her algorithm.

It is fascinating to note that the computation of these numbers still seems to have a certain mystery - Wikipedia[1] notes that "There is a widespread misinformation that no simple closed formulas for the Bernoulli numbers exist." It was not until 1999 that Akiyama and Tanigawa [2,3] discovered the following efficient, elegant, and curious algorithm to compute the Bernoulli numbers Bn.

Define the numbers An,m as follows. For n = 0, the first row of the table, we define A0,m to be 1/(m+1). For subsequent rows, an entry Ai,j is defined by (j+1) * (Ai-1, j - Ai-1, j+1). For example, the entry in column 2 of row 2 of the table below is given by 3 * (1/4 - 1/5).

The nth Bernoulli number, Bn, is simply the nth entry in column 0: Bn = An, 0.

This computation is very reminiscent of the calculation of the binomial coefficients using Pascal's triangle.

Note we can compute this table by proceding down along anti-diagonals k = 0, 1, 2, 3, ... where i + j = k.

However, if we want to compute only up to n, a more straightforward approach initializes the first n+1 entries of the first row and then proceeds left to right filling in the upper left triangle in rows 1 through n.

This could doubtless be implemented in two lines of a clean, functional language like Haskell, but I'll present some pseudocode in a 'C'-like language, just because it's more familiar to many people.

So, here it is, 167 years later: a polished up re-implementation of the first computer program, ever.


function bernoulli(n) {
  // initialize first row
  for (j = 0; j 

This post is respectfully dedicated to Angie Byron (webchick), Katherine Bailey, Audrey Foo, Ariane Khachatourians, and all of the other women who make the Drupal community such a wonderful place.

References:

[1] Wikipedia: http://en.wikipedia.org/wiki/Bernoulli_number, downloaded Mar 24, 2010 @ 22:30

[2] Masanobu Kaneko: The Akiyama-Tanigawa algorithm for Bernoulli numbers, Journal of Integer Sequences, Vol. 3 (2000). (http://www.cs.uwaterloo.ca/journals/JIS/vol3.html)

[3] Akiyama, S. and Tanigawa, Y. : Multiple zeta values at non-positive integers, preprint (1999).