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 *B _{n}*.

Define the numbers *A _{n,m}* as follows. For

The *n*^{th} Bernoulli number, *B _{n}*, is simply the

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.*

[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).

- Djun Kim's blog
- Log in to post comments