Retro Computer Laboratory

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Note G and the calculation of Bernoulli numbers ======

See [[wp>Bernoulli numbers|Bernoulli numbers]] in Wikipedia for details on Bernoulli numbers.

They may have been selected as an example because:

    * They cannot be enumerated using the //Difference Engine//
    * The values seem to be fairly random
    * The values require a machine that can handle very large numbers
    * In approximations of trigonometric functions, they allow less calculating steps than other approximations known at that time. Note that Tchebysheff's Approximation was published several years later (1859).
    * They are a sequence where the n-th number can be calculated from the previous numbers

Note that variants for the indexing and sign for Bernoulli numbers were proposed since that time; the later forms allow shorter writing of the formulas.

In //Note G//, equation 8 shows the recursion formula used by AAL:

<nowiki> `0 = -1/2 * (2n-1)/(2n+1) + B_1 ((2n)/2) + B_3 ((2n*(2n-1)*(2n-2)) /(2*3*4)) + ... + B_(2n-1)` </nowiki>

and  in terms of the number to be calculated:

<nowiki> `-B_(2n-1) = -1/2 * (2n-1)/(2n+1) + B_1 ((2n)/2) + B_3 ((2n*(2n-1)*(2n-2)) /(2*3*4)) + B_5 ((2n*(2n-1)... (2n-4)) /(2*3*4*5*6)) +...` </nowiki>

Using `A_i` as abbreviation for the factors gives

<nowiki> `B_(2n-1) = A_0(n) + A_1(n) * B_1 + A_3(n) * B_3 + ... + A_5(n) * B_(2n-3)` </nowiki>

In the text, AAL wrote: //A<sub>1</sub>, A<sub>3</sub>, &c. being … functions of n …//, but does not use a corresponding notation in the equation, which was done in the above equation.

Thus, the coefficients – which are not given in //Note G//   – are:

`A_0(n) = 1/2 * (2n-1)/(2n+1)`

`A_1(n) = -(2n) / 2`

`A_3(n) = A_1(n) * (2n-1)/3 * (2n-2)/4`

`A_5(n) = A_3(n) * (2n-3)/5 * (2n-4)/6`

As each `A_i(n)` depends only on the previous  `A_(i-1)(n)` (for `i>3`), they can be enumerated within a loop, as the memory places for the earlier numbers can be reused.

However, to calculate the n-th Bernoulli number, all previuos ones must be present, used each for multiplication, and left there for the next round.

This is done in later computers by either using an index register or dynamically modifying operation addresses during execution.

Note that the signs are different to those in //Note G//.

====== Why not equation 2 or 3? ======

On page 725, AAL shows two commonly used formulas in equation 2 and 3, that do calculate the n-th Bernoulli number just as a series without recursion to other Bernoulli numbers, i.e. as a function of n alone. Then she writes:
> As however our object is not simplicity or facility of computation, but the illustration of the powers of the engine, we prefer selecting the formula below, marked (8.)

Thus she probably delibrately took into account the indexing problem.

While equation (2.) looks fairly simple, it is an inifinite sum of terms, which by itself would rule out using the AE. (Still need to write down examples, as elements to be summed up are not integer numbers.)

Equation (3.) looks like a finite sequence, but needs some rewriting to avoid arbitrary large numbers as intermediate results. (Would required deeper inspection too.)

So the version in equation (8.) looks to me the most simple soulution that has a facility of computation; so why did AAL deny this fairly good argument? 


====== The problem in line 21 ======

The tabular programme in the //Diagram accompanying Translator's Note G//   is fairly straightforward upto line 12; the wrong indices in line 4 is evidently a typographic error.

To calculate `B_7`, the lines 13 to 23 are executed once, then in line 24 and 25 the result is stored.

To calculate `B_9` afterwards, lines 13 to 23 are a loop executed twice, i.e. until `V_10` is reduced to `1`. Let us ignore that the lines are missing that compare `V_10` to one, and raise the overflow lever in the mill, as to control the loop exit condition. This would be added easily.

Howerver, in line 21 during the second round, the value to be multiplied is not `V_22`, containing `B_5`, but `V_23`, contining the just calculated `B_7`.

AAL has evidently see that problem and writes on page 729 bottom: 
>The only exception to a //perfect identity//   in all the processes and columns used, for every repetition of Operations (13…23), is, that Operation 21 always requires one of its factors from a new column, and Operation 24 always puts its result on a new column. But as these variations follow the same law at each repetition (Operation 21 always requiring its factor from a column one in advance of that which it used the previous time, and Operation 24 always putting its result on the column one in advance of that which received the previous result), they are easily provided for in arranging the recurring group (or cycle) of Variable-cards.

However, while it is correctly assumed that this may be solved, there is no hint of how this is //easily provided//, that the loom of variable cards are changed with each round.

It may be considered only to loop the operation cards, and to //unravel the loop//, although that contradicts her remark earlier on the page, that  >when `n>2`, twenty-five Operation-cards are used; but no //more//   are needed, however great `n` may be.

On page 729, there is a footnote (for which I did not found the corresponding reference place), that millions of Bernoulli numbers could be calculated this way.

However, to calculate millions of Bernoulli numbers, the AE would need a store of millions of numbers; this may be a place where she did not fully understand the problem.

Alan Bromley in his 1998 article on page 44 left column, second to last paragraph, writes: 
>With hindsight, we can note that in the Analytical Engine (at least until 1840), Babbage did not posess the variable-address concept; that is, there was no mechanism by which the machine could, as a result of a calculation, specify a particular variable in the store to be used of an operand for an instruction.

He refers this to solving matrices, and thus to a much much more complex problem.

====== Actual Calculation ======

`A_0(1) = 1/2 * 1/3 = 1/6`

`B_1 = A_0(1) = 1/6`

`A_0(2) = 3/10`

`A_1(2) = -2`

`B_3 = A_0(2) + A_1(2) * B_1 = 3/10 - 2/6 = (9 - 10)/30 = - 1/30`

`A_0(3) = 5/14`

`A_1(3) = -3`

`A_3(3) = -3 * 5/3 * 4/4 = -5`

`B_5 = 5/14 - 3/6 + 5/30 = (5 - 7)/14 + 1/6 = -1/7 + 1/6 = 1/42`

`A_0(4) = 7/18`

`A_1(4) = -4`

`A_3(4) = -4 * 7/3 * 6/4 = -14`

`A_5(4) = -14 * 5/5 * 4/6 = - 28/3`

`B_7 = 7/18 - 4/6 + 14/30 - 28/(3*42) = (7 - 12)/18 + 7/15 - 2/9 = -5/18 + (21-10)/45 = (-25 + 22)/90 = -3/90 = - 1/30`