February 8, 2011
Beginning in the 1820s, and continuing until his death in 1871, Charles Babbage, an English mathematician (he was for ten years the Lucasian Professor of Mathematics at Cambridge, a chair once held by Sir Isaac Newton and currently held by Stephen Hawking), engineer, scientist and inventor was fascinated with the idea of a machine that could perform arithmetic calculations. His first machine, the Difference Engine, first described in 1822, used finite differences to compute the values of polynomials. His second machine, the Analytical Engine, first described in 1837, was much more ambitious, consisting of a control unit, an arithmetic processor, and a storage space for intermediate calculations, and could be programmed to perform specific calculations by use of punched cards. Both machines were mechanical, not electrical, powered by steam. Neither machine was built prior to his death, due to a lack of money and the expertise to manufacture the needed parts with the required precision.
Augusta Ada King (née Byron), Countess of Lovelace, daughter of the English poet Lord Byron and an amateur mathematician, was fascinated by Babbage’s plans for the Analytical Engine. In 1842, at Babbage’s request, she translated a manuscript about the Analytical Engine by the Italian mathematician Luigi Menabrea (who later became the Prime Minister of Italy), adding her own notes, which were more extensive than the original manuscript. Note G describes the use of the Analytical Engine to compute the Bernoulli numbers; it is complete and rigorous, and is now recognized as the first computer program, making the Countess the first computer programmer.
The Countess’ translated manuscript and notes, available from FourmiLab, make fascinating reading, a terrific way to pass a cold winter evening. She was clearly in full command of her subject, and anticipated much of computer architecture and modern computer programming languages a full century before they were discovered. For instance, if you ignore the stilted language, this quote could have been written last week:
In studying the action of the Analytical Engine, we find that the peculiar and independent nature of the considerations which in all mathematical analysis belong to operations, as distinguished from the objects operated upon and from the results of the operations performed upon those objects, is very strikingly defined and separated.
It is hard to overstate the Countess' accomplishment. She had no high-level programming language, no libraries, no integrated development environment, not even an assembler or a debugger; she was working on "bare metal" — literally! The only documentation she had was that which she wrote herself. And she was working in untrodden territory, as there were no textbooks about programming, no tutors, no "Learn X in 21 Days" to help her. She didn't even have a machine to run her program. It is amazing that she wrote the program at all; incredibly, modern computer scientists have examined the program and declared it bug-free, and today’s programmers must simply stand in awe. The Countess was not only the first computer programmer, she was also an extremely talented one.
The program that the Countess chose to demonstrate the Analytical Engine was a program to compute the Bernoulli numbers and is based on Equation 8 of Note G:
Thus, B1 = -1/2 when n = 1, B3 = 1/6 when n = 2, B5 = -1/30 when n = 3, B7 = 1/42 when n = 4, B9 = -1/30 when n = 5, B11 = 5/66 when n = 6, B13 = -691/2730 when n = 7, B15 = 7/6 when n = 8, B17 = -3617/510 when n = 9, B19 = 43867/798 when n = 10, and so on. The successive Bernoulli numbers are computed in order, each feeding the computation of the next, the various numerators and denominators being computed according to the pattern in the formula.
Your task is to write a program to calculate the Bernoulli numbers, using the method of the Countess’ Note G. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.