Instantly share code, notes, and snippets.

Embed
What would you like to do?
Lovelace's Note G Program in C
#include <stdio.h>
/*
* Calculates what Ada Lovelace labeled "B7", which today we would call the 8th
* Bernoulli number.
*/
int main(int argc, char* argv[])
{
// ------------------------------------------------------------------------
// Data
// ------------------------------------------------------------------------
float v1 = 1; // 1
float v2 = 2; // 2
float v3 = 4; // n
// ------------------------------------------------------------------------
// Working Variables
// ------------------------------------------------------------------------
float v4 = 0;
float v5 = 0;
float v6 = 0; // Factors in the numerator
float v7 = 0; // Factors in the denominator
float v8 = 0;
float v10 = 0; // Terms remaining count, basically
float v11 = 0; // Accumulates v6 / v7
float v12 = 0; // Stores most recent calculated term
float v13 = 0; // Accumulates the whole result
// ------------------------------------------------------------------------
// Result Variables
// ------------------------------------------------------------------------
float v21 = 1.0f / 6.0f; // B1
float v22 = -1.0f / 30.0f; // B3
float v23 = 1.0f / 42.0f; // B5
float v24 = 0; // B7, not yet calculated
// ------------------------------------------------------------------------
// Calculation
// ------------------------------------------------------------------------
// ------- A0 -------
/* 01 */ v4 = v5 = v6 = v2 * v3; // 2n
/* 02 */ v4 = v4 - v1; // 2n - 1
/* 03 */ v5 = v5 + v1; // 2n + 1
// In Lovelace's diagram, the below appears as v5 / v4, which is incorrect.
/* 04 */ v11 = v4 / v5; // (2n - 1) / (2n + 1)
/* 05 */ v11 = v11 / v2; // (1 / 2) * ((2n - 1) / (2n + 1))
/* 06 */ v13 = v13 - v11; // -(1 / 2) * ((2n - 1) / (2n + 1))
/* 07 */ v10 = v3 - v1; // (n - 1), set counter?
// A0 = -(1 / 2) * ((2n - 1) / (2n + 1))
// ------- B1A1 -------
/* 08 */ v7 = v2 + v7; // 2 + 0, basically a MOV instruction
/* 09 */ v11 = v6 / v7; // 2n / 2
/* 10 */ v12 = v21 * v11; // B1 * (2n / 2)
// A1 = (2n / 2)
// B1A1 = B1 * (2n / 2)
// ------- A0 + B1A1 -------
/* 11 */ v13 = v12 + v13; // A0 + B1A1
/* 12 */ v10 = v10 - v1; // (n - 2)
// On the first loop this calculates B3A3 and adds it on to v13.
// On the second loop this calculates B5A5 and adds it on.
while (v10 > 0)
{
// ------- B3A3, B5A5 -------
while (v6 > 2 * v3 - (2 * (v3 - v10) - 2))
{ // First Loop:
/* 13 */ v6 = v6 - v1; // 2n - 1
/* 14 */ v7 = v1 + v7; // 2 + 1
/* 15 */ v8 = v6 / v7; // (2n - 1) / 3
/* 16 */ v11 = v8 * v11; // (2n / 2) * ((2n - 1) / 3)
// Second Loop:
// 17 v6 = v6 - v1; 2n - 2
// 18 v7 = v1 + v7; 3 + 1
// 19 v8 = v6 / v7; (2n - 2) / 4
// 20 v11 = v8 * v11; (2n / 2) * ((2n - 1) / 3) * ((2n - 2) / 4)
}
// A better way to do this might be to use an array for all of the
// "Working Variables" and then index into it based on some calculated
// index. Lovelace might have intended v14-v20 to be used on the
// second iteration of this loop.
//
// Lovelace's program only has the version of the below line using v22
// in the multiplication.
if (v10 == 2)
{
/* 21 */ v12 = v22 * v11; // B3 * A3
}
else
{
/* 21 */ v12 = v23 * v11; // B5 * A5
}
// B3A3 = B3 * (2n / 2) * ((2n - 1) / 3) * ((2n - 2) / 4)
// ------- A0 + B1A1 + B3A3, A0 + B1A1 + B3A3 + B5A5 -------
/* 22 */ v13 = v12 + v13; // A0 + B1A1 + B3A3 (+ B5A5)
/* 23 */ v10 = v10 - v1; // (n - 3), (n - 4)
}
/* 24 */ v24 = v13 + v24; // Store the final result in v24
/* 25 */ v3 = v1 + v3; // Move on to the next Bernoulli number!
// This outputs a positive number, but really the answer should be
// negative. There is some hand-waving in Lovelace's notes about the
// Analytical Engine sorting out the proper sign.
printf("A0 + B1A1 + B3A3 + B5A5: %.2f\n", v24);
}
@turnspike

This comment has been minimized.

turnspike commented Aug 20, 2018

// In Lovelace's diagram, the below appears as v5 / v4, which is incorrect.

Does this mean Ada also invented the first bug?

@cbarrick

This comment has been minimized.

cbarrick commented Aug 20, 2018

@turnspike: Indeed. According to the article for which this code was written:

In her “diagram of development,” Lovelace gives the fourth operation as v5 / v4. But the correct ordering here is v4 / v5. This may well have been a typesetting error and not an error in the program that Lovelace devised. All the same, this must be the oldest bug in computing. I marveled that, for ten minutes or so, unknowingly, I had wrestled with this first ever bug.

https://twobithistory.org/2018/08/18/ada-lovelace-note-g.html

@gchilds

This comment has been minimized.

gchilds commented Aug 20, 2018

I wasn’t expecting to see floats.

@rjmunro

This comment has been minimized.

rjmunro commented Aug 20, 2018

@gchilds I think the floats would have been fixed point decimals in the original machine - they are both just the most convenient way to approximate fractional values in the relevant architecture.

@dralley

This comment has been minimized.

dralley commented Aug 20, 2018

Why are operations 17-20 commented out? Is it intentional?

@Alphadelta14

This comment has been minimized.

Alphadelta14 commented Aug 20, 2018

17-20 is the second loop of 13-16., just with updated comments.

@sdrees

This comment has been minimized.

sdrees commented Aug 25, 2018

This may well have been a typesetting error and not an error in the program

Yes! I hear this all the time ... 🐛

@ricest

This comment has been minimized.

ricest commented Aug 27, 2018

This may well have been a typesetting error and not an error in the program

Yes! I hear this all the time ...

It does just sound like an excuse but there's quite likely to be something to that. This was one of the reasons that Knuth developed TeX. Your options were bodge the notation on your typewriter or pay someone who knew typesetting but not your math to make it look good.

@neopaf

This comment has been minimized.

neopaf commented Sep 8, 2018

Thanks for the article and the code!
About “the bug”, please take a look at a column with Statement of Results. It’s contents of v4 divided by contents of v5. So the idea was perfect.
https://upload.wikimedia.org/wikipedia/commons/c/cf/Diagram_for_the_computation_of_Bernoulli_numbers.jpg

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment