Algoritmo di Ada Lovelace per i numeri di Bernoulli

Ada Byron e l'algoritmo per il calcolo dei numeri di Bernoulli

L'algoritmo di Ada permette di calcolare i numeri di Bernoulli, senza dover conteggiare tutti quelli ad essi precedenti. Tuttora, questo algoritmo è considerato un risultato brillante, non soltanto per la valenza computazionale, quanto soprattutto nel campo della programmazione informatica. Infatti costituisce un chiaro esempio in cui la Matematica offre validi strumenti anche per lo sviluppo informatico.

Gli algoritmi di Ada Byron e di Bernoulli a confronto

Secondo alcune fonti storiche, per la costruzione del suo programma Ada Lovelace si servì della seguente funzione generatrice esponenziale:

(1)

${\displaystyle \sum _{k=0}^{n}B_{k}{{x^{n}} \over n!}}$ 

opportunamente semplificata e modificata nell'espressione:

(2)

${\displaystyle {1 \over 2}{{2x-1} \over {2x+1}}=B_{2}{{2x} \over 2}-B_{4}{{2x(2x-1)(2x-2)} \over 4!}+B_{6}{{2x(2x-1)...(2x-4)} \over 6!}+...}$ 

Altre fonti non concordano con tale versione per diverse ragioni. In primo luogo perché, pur essendo vero che lo sviluppo della (1), insieme ad altri sviluppi in serie di funzioni trascendenti, contiene numeri di Bernoulli, come osservato dallo stesso Bernoulli nell'Ars conjectandi e successivamente anche da Eulero e Stirling, non esiste tuttavia alcuna relazione matematica in grado di trasformare la (1) nella (2). In secondo luogo, pare esistere una lettera della Byron scritta nel luglio del 1843, nella quale chiedeva a Babbage di inviarle la formula generatrice dei numeri di Bernoulli e non uno sviluppo che li contenesse (il che prevede anche una lista dei numeri). Infine, sempre in base a tali fonti, la formula (2) utilizzata dalla Byron non è altro che una rielaborazione della seguente formula utilizzata da Bernoulli:

(3)

${\displaystyle 2n=(-1)^{k-1}\sum _{k=1}^{n}{{{2n+1} \choose {2k}}2^{k}B_{2k}}}$ 

e che Ada fra l'altro aveva studiato qualche anno prima, sotto la guida di De Morgan. Per confrontare la formula effettivamente utilizzata dalla Byron con la (3), è sufficiente riscrivere lo sviluppo di quest’ultima sostituendo ${\displaystyle n}$  con ${\displaystyle x}$  e sottraendo ${\displaystyle 1}$  da entrambi i membri dell'uguaglianza:

${\displaystyle 2x-1={{2x+1} \choose {2}}2^{2}B_{2}-{{2x+1} \choose {4}}2^{4}B_{4}+{{2x+1} \choose {6}}2^{6}B_{6}-...}$ 

da cui, dividendo ciascun termine per il fattore ${\displaystyle 2(2x+1)}$ , si ottiene:

(4)

${\displaystyle {{2x-1} \over {2(2x+1)}}={{{{2x+1} \choose 2}2^{2}B_{2}} \over {2(2x+1)}}-{{{{2x+1} \choose 4}2^{4}B_{4}} \over {2(2x+1)}}+{{{{2x+1} \choose 6}2^{6}B_{6}} \over {2(2x+1)}}-...{-1 \over {2(2x+1)}}}$ 

È possibile riscrivere ciascun coefficiente binomiale che compare nella (4) in modo più semplice. Ad esempio per il primo coefficiente si ha:

${\displaystyle {{2x+1} \choose 2}={{(2x+1)!} \over {2!(2x+1-2)!}}={{(2x+1)(2x)(2x-1)!} \over {2!(2x-1)!}}={{(2x+1)2x} \over 2}}$ 

oppure per il secondo si ha:

${\displaystyle {{2x+1} \choose 4}={{(2x+1)!} \over {4!(2x-3)!}}={{(2x+1)(2x)(2x-1)(2x-2)} \over {4!}}}$ 

Dunque, semplificando la (4), si perviene in definitiva alla:

(5)

${\displaystyle {{2x} \over {2(2x+1)}}=2^{3}B_{4}{{2x(2x-1)(2x-2)} \over {4!}}+2^{5}B_{6}{{2x(2x-1)(2x-2)(2x-3)(2x-4)} \over {6!}}-...}$ 

dalla quale, per ricorsività e grazie al supporto di una macchina quale l'Analithycal Engine di Babbage, è assai facile generare progressivamente i numeri di Bernoulli ${\displaystyle B_{n}}$  con ${\displaystyle n>1}$  , come Ada stessa propose.

In realtà, la Byron usò la formula (2) che differisce leggermente dalla (5) sia per l'alternanza dei segni sia per la presenza delle potenze dispari di ${\displaystyle 2}$ , oltre che nel numeratore dell'uguaglianza, dove il fattore ${\displaystyle 2x}$  compare al posto del fattore ${\displaystyle 2x-1}$  della (5).

Mediante una congettura piuttosto geniale per quell'epoca, la Byron riuscì a generare i coefficienti incogniti ${\displaystyle B_{n}}$  semplicemente mediante iterazioni successive, attribuendo ad ${\displaystyle x}$  valori interi via via crescenti ${\displaystyle 1}$ , ${\displaystyle 2}$ , ${\displaystyle 3}$ , ... In questo modo, sostituendo ${\displaystyle x=1}$ , tanto nella (2) quanto nella (5), tutti i termini dello sviluppo contenenti ${\displaystyle (2x-2)}$  si annullano, ossia tutti i termini dal secondo in poi. Ad esempio, per la (5) si ottiene:

${\displaystyle {{2\cdot 1} \over {2(2\cdot +1)}}=2^{1}B_{2}{{2\cdot 1} \over {2!}}}$ 

dalla quale risulta agevole ricavare ${\displaystyle B_{2}={1 \over 6}}$ . In modo analogo, attribuendo ad ${\displaystyle x}$  il valore ${\displaystyle 2}$  si annullano invece tutti i termini che contengono il fattore ${\displaystyle (2x-4)}$  , ovvero tutti quelli a partire dal terzo:

${\displaystyle {{2\cdot 2} \over {2(2\cdot 2+1)}}=2^{1}B_{2}{{2\cdot 2} \over {2!}}-2^{3}B_{4}{{2\cdot 2(2\cdot 2-1)(2\cdot 2-1)} \over {4!}}}$ 

da cui, una volta noto ${\displaystyle B_{2}}$  , si ottiene il secondo coefficiente dello sviluppo ${\displaystyle B_{4}}$  . Per ${\displaystyle x=3}$  spariscono tutti i termini a partire dal quarto e così via per valori sempre crescenti di ${\displaystyle x}$ . Anche Bernoulli, un secolo prima della Byron, propose un procedimento analogo in base al quale partendo dallo sviluppo (3) e ponendo di volta in volta ${\displaystyle n=1}$ , ${\displaystyle 2}$ , ${\displaystyle 3,}$  ... si riesce ad arrestare la somma e a calcolare ricorsivamente i coefficienti ${\displaystyle B_{n}}$  . Così ad esempio per ${\displaystyle n=1}$  , e di conseguenza ${\displaystyle k=1}$  , si ha:

${\displaystyle 2={3 \choose 2}2^{2}B_{2}}$ 

da cui si ricava immediatamente ${\displaystyle B_{2}={1 \over 6}}$  . Ovviamente il numero successivo significativo ${\displaystyle B_{4}}$  si ottiene arrestando lo stesso sviluppo per ${\displaystyle n=2}$  e dunque facendo variare ${\displaystyle k}$  da ${\displaystyle 1}$  a ${\displaystyle 2}$ 

${\displaystyle 4={5 \choose 2}2^{2}B_{2}-{5 \choose 4}2^{4}B_{4}}$ 

sapendo che ${\displaystyle B_{2}={1 \over 6}}$ , si ottiene:

${\displaystyle 4={{20} \choose 3}-80B_{4}}$ 

cioè ${\displaystyle B_{4}={1 \over 30}}$ . Dunque la vera innovazione introdotta dall'algoritmo della Byron rispetto al metodo di Bernoulli sta nell'aver usato ad ogni iterazione la stessa formula, riuscendo a semplificarla di volta in volta al variare del valore dell'incognita ${\displaystyle x}$ . Il calcolo di ciascun numero, uno alla volta, costituisce il ciclo esterno del programma, mentre per calcolare ogni valore frazionario successivo si fa ricorso ad un ciclo secondario. Riportiamo qui di seguito gli algoritmi proposti dalla Byron e da Bernoulli:

Algoritmo di Ada Byron

${\displaystyle {1 \over 2}{{2x-1} \over {2x+1}}=B_{2}{{2x-1} \over {2!}}+B_{4}{{2x(2x-1)(2x-2)} \over {4!}}+B_{6}{{2x(2x-1)(2x-2)(2x-3)(2x-4)} \over {6!}}+...}$ 

Algoritmo di Bernoulli

${\displaystyle {{2x} \over {2x+1}}=2^{1}B_{2}{{2x} \over {2!}}-2^{3}B_{4}{{2x(2x-1)(2x-2)} \over {4!}}+2^{5}B_{6}{{2x(2x-1)(2x-2)(2x-3)(2x-4)} \over {6!}}-...}$ 

  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica