Algoritmo di Ada Lovelace per i numeri di Bernoulli

L'algoritmo di Ada Lovelace (nata Ada Byron) permette di calcolare i numeri di Bernoulli. Questo algoritmo è noto soprattutto per essere stato il primo programma della storia dell'informatica.

Nota G, diagramma di Ada Lovelace: fu il primo algoritmo per computer pubblicato

La formula utilizzata

Come si vede dal diagramma in figura e dal testo relativo disponibile in lingua inglese[1], Ada Lovelace nell'implementare il suo algoritmo si servì della seguente formula:

0 = − 1 2 2 n − 1 2 n + 1 + B 2 2 n 2 + B 4 2 n ( 2 n − 1 ) ( 2 n − 2 ) 4 ! + B 6 2 n ( 2 n − 1 ) . . . ( 2 n − 4 ) 6 ! + . . . + B 2 n {\displaystyle 0=-{1 \over 2}{{2n-1} \over {2n+1}}+B_{2}{{2n} \over 2}+B_{4}{{2n(2n-1)(2n-2)} \over 4!}+B_{6}{{2n(2n-1)...(2n-4)} \over 6!}+...+B_{2n}}

dove abbiamo sostituito gli indici dispari usati da Ada con i pari secondo la moderna notazione dei Numeri di Bernoulli. Utilizzando il fattoriale decrescente possiamo scrivere in forma compatta:

1 2 2 n − 1 2 n + 1 = ∑ k = 1 n ( 2 n ) 2 k − 1 _ ( 2 k ) ! B 2 k {\displaystyle {1 \over 2}{{2n-1} \over {2n+1}}=\sum _{k=1}^{n}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}}

essendo il ( 2 n ) 2 n − 1 _ = ( 2 n ) ! {\displaystyle {(2n)}^{\underline {2n-1}}=(2n)!} la precedente equivale a

B 2 n = 1 2 2 n − 1 2 n + 1 − ∑ k = 1 n − 1 ( 2 n ) 2 k − 1 _ ( 2 k ) ! B 2 k       p e r   n > 1               p e r   n = 1       B 2 = 1 2 2 − 1 2 + 1 = 1 6 {\displaystyle B_{2n}={1 \over 2}{{2n-1} \over {2n+1}}-\sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}~~~per~n>1~~~~~~~per~n=1~~~B_{2}={1 \over 2}{{2-1} \over {2+1}}={1 \over 6}}

Le fonti concordano[2] con Ada stessa[1], sul fatto che questa formula derivi dalla funzione generatrice e anche nel fornire solo un accenno di dimostrazione per giustificarlo: 


  
    
      
        
          
            x
            
              
                e
                
                  x
                
              
              −
              1
            
          
        
        =:
        
          ∑
          
            k
            =
            0
          
          
            ∞
          
        
        
          
            
              
                x
              
              
                k
              
            
            
              k
              !
            
          
        
        
          B
          
            k
          
        
      
    
    {\displaystyle {\frac {x}{e^{x}-1}}=:\sum _{k=0}^{\infty }{\frac {{x}^{k}}{k!}}B_{k}}

La funzione generatrice può considerarsi una uguaglianza fra serie formali di potenze o fra funzioni analitiche; in questo caso per la convergenza della serie si chiede che x abbia valore assoluto minore di 2π (il raggio di convergenza della serie stessa).

È sicuramente più semplice mostrare invece che la formula usata dalla Byron non è altro che la consueta formula di ricorrenza:[3]

B m = − 1 m + 1 ∑ j = 0 m − 1 ( m + 1 j ) B j         o s s i a :       ∑ j = 0 m ( m + 1 j ) B j = 0             ( c o n   m > 0   e   B 0 = 1 )   {\displaystyle B_{m}=-{1 \over {m+1}}\sum _{j=0}^{m-1}{m+1 \choose {j}}B_{j}~~~~ossia:~~~\sum _{j=0}^{m}{m+1 \choose {j}}B_{j}=0~~~~~~(con~m>0~e~B_{0}=1)~}

resa più efficiente per il calcolo automatico. Per questo è sufficiente notare che:

∑ k = 1 n − 1 ( 2 n ) 2 k − 1 _ ( 2 k ) ! B 2 k = 1 2 n + 1 ∑ k = 1 n − 1 ( 2 n + 1 2 k ) B 2 k {\displaystyle \sum _{k=1}^{n-1}{\frac {{(2n)}^{\underline {2k-1}}}{(2k)!}}B_{2k}={\frac {1}{2n+1}}\sum _{k=1}^{n-1}{{2n+1} \choose {2k}}B_{2k}}

e che

1 2 n + 1 ∑ k = 0 1 ( 2 n + 1 k ) B k = 1 2 n + 1 ( ( 2 n + 1 0 ) ( 1 ) + ( 2 n + 1 1 ) ( − 1 2 ) ) = {\displaystyle {\frac {1}{2n+1}}\sum _{k=0}^{1}{{2n+1} \choose {k}}B_{k}={\frac {1}{2n+1}}({{2n+1} \choose {0}}(1)+{{2n+1} \choose {1}}(-{\frac {1}{2}}))=}
= 1 2 n + 1 ( 1 + ( 2 n + 1 ) ( − 1 2 ) ) = 1 2 n + 1 ( − 1 2 ) ( − 2 + 2 n + 1 ) = − 1 2 2 n − 1 2 n + 1 {\displaystyle ={\frac {1}{2n+1}}(1+(2n+1)(-{\frac {1}{2}}))={\frac {1}{2n+1}}(-{\frac {1}{2}})(-2+2n+1)=-{\frac {1}{2}}{\frac {2n-1}{2n+1}}}

Come si può controllare nella nota G in figura questa è la funzione utilizzata da Ada dato che ai suoi tempi, come aveva indicato anche Jacob Bernoulli nel suo "Ars Conjectandi" più di un secolo prima i numeri di Bernoulli cominciavano dopo i primi due attuali che quindi vanno sostituiti con i loro valori numerici per ottenere la formula usata. Nella nota Ada scrive B 1 B 3 B 5 . . . {\displaystyle B_{1}B_{3}B_{5}...} che chiaramente corrispondono ai nostri B 2 B 4 B 6 . . . {\displaystyle B_{2}B_{4}B_{6}...} .

Note

  1. ^ a b Lovelace.
  2. ^ Adity Kar, Ada Lovelace, su people.maths.ox.ac.uk (archiviato dall'url originale il 3 luglio 2017).
  3. ^ SUPSI.

Bibliografia

  • (EN) Luigi F. Menabrea, Nota G di Ada Lovelace, in Sketch the analytical engine invented by Charles Babbage, Bibliothèque Universelle de Genève, 1842. URL consultato il 19 giugno 2017.
  • Giorgio Pietrocola, Dialogo con una formula d'altri tempi (PDF), su SUPSI. URL consultato il 16 giugno 2023.

Voci correlate

  • Ada Lovelace
  • Numeri di Bernoulli
  Portale Informatica
  Portale Matematica