Formula di Bailey–Borwein–Plouffe

La formula di Bailey–Borwein–Plouffe, nota anche come formula BBP, è una formula per il calcolo di qualsiasi cifra n-ma prefissata di ${\displaystyle \pi }$. È stata scoperta nel 1995 da Simon Plouffe ed è così chiamata in onore degli autori dell'articolo in cui è stata pubblicata: David H. Bailey, Peter Borwein e Plouffe.^[1]. La formula è la seguente:

${\displaystyle \pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]}$

La formula BBP dà origine ad un algoritmo di tipo spigot per il calcolo dell'n-esima cifra esadecimale (in base 16) di ${\displaystyle \pi }$ (e quindi anche della n-esima cifra binaria di ${\displaystyle \pi }$) senza calcolare le cifre precedenti. La formula non consente di calcolare l'n-esima cifra decimale di ${\displaystyle \pi }$ (cioè in base 10). Tuttavia lo stesso Plouffe ha scoperto un'altra formula nel 2022 che consente di estrarre l'n-esima cifra decimale di ${\displaystyle \pi }$.^[2] L'esistenza della formula BBP è stata una sorpresa: infatti si riteneva che calcolare l'n-esima cifra di ${\displaystyle \pi }$ fosse altrettanto difficile quanto calcolare le prime n cifre.^[1]

La formula può anche essere riscritta come rapporto tra due polinomi:

${\displaystyle \pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {120k^{2}+151k+47}{512k^{4}+1024k^{3}+712k^{2}+194k+15}}\right)\right]}$

la cui dimostrazione è piuttosto semplice.^[3]

A partire dalla sua scoperta, sono state trovate altre formule nella forma generale

${\displaystyle \alpha =\sum _{k=0}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {p(k)}{q(k)}}\right]}$

per molti altri numeri irrazionali ${\displaystyle \alpha }$, dove ${\displaystyle p(k)}$ e ${\displaystyle q(k)}$ sono polinomi con coefficienti interi e ${\displaystyle b\geq 2}$ è una base intera.^[4] Formule di questa tipologia sono conosciute come formule di tipo BBP.^[5] Dato un numero ${\displaystyle \alpha }$, non esiste un algoritmo noto per trovare i valori appropriati di ${\displaystyle p(k)}$, ${\displaystyle q(k)}$ e ${\displaystyle b}$; infatti tali formule vengono scoperte in modo sperimentale.

Specializzazioni

Una specializzazione della formula generale che ha prodotto molti risultati è la seguente:

${\displaystyle P(s,b,m,A)=\sum _{k=0}^{\infty }\left[{\frac {1}{b^{k}}}\sum _{j=1}^{m}{\frac {a_{j}}{(mk+j)^{s}}}\right]}$,

dove s, b e m sono numeri interi, e ${\displaystyle A=(a_{1},a_{2},\dots ,a_{m})}$ è una sequenza di numeri interi. La funzione P porta ad una notazione compatta per alcune soluzioni. Ad esempio, la formula BBP:

${\displaystyle \pi =\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]}$

può essere scritta come:

${\displaystyle \pi =P{\bigl (}1,16,8,(4,0,0,-2,-1,-1){\bigr )}.}$

Formule di tipo BBP già note

Alcune delle formule più semplici di tipo BBP, già ben note prima della scoperta della formula BBP e per le quali la funzione P porta ad una notazione compatta, sono le seguenti:

${\displaystyle {\begin{aligned}\ln {\frac {10}{9}}&={\frac {1}{10}}+{\frac {1}{200}}+{\frac {1}{3\ 000}}+{\frac {1}{40\,000}}+{\frac {1}{500\,000}}+\cdots \\&=\sum _{k=1}^{\infty }{\frac {1}{10^{k}\cdot k}}={\frac {1}{10}}\sum _{k=0}^{\infty }\left[{\frac {1}{10^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{10}}P{\bigl (}1,10,1,(1){\bigr )},\end{aligned}}}$

${\displaystyle {\begin{aligned}\ln 2&={\frac {1}{2}}+{\frac {1}{2\cdot 2^{2}}}+{\frac {1}{3\cdot 2^{3}}}+{\frac {1}{4\cdot 2^{4}}}+{\frac {1}{5\cdot 2^{5}}}+\cdots \\&=\sum _{k=1}^{\infty }{\frac {1}{2^{k}\cdot k}}={\frac {1}{2}}\sum _{k=0}^{\infty }\left[{\frac {1}{2^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{2}}P{\bigl (}1,2,1,(1){\bigr )}.\end{aligned}}}$

essendo valida la seguente identità per ogni a > 1: ${\displaystyle \ln {\frac {a}{a-1}}=\sum _{k=1}^{\infty }{\frac {1}{a^{k}\cdot k}}}$.

A Plouffe è dovuta anche la seguente formula, ricavabile a partire dallo sviluppo di Maclaurin dell'arcotangente:

${\displaystyle {\begin{aligned}\arctan {\frac {1}{b}}&={\frac {1}{b}}-{\frac {1}{b^{3}3}}+{\frac {1}{b^{5}5}}-{\frac {1}{b^{7}7}}+{\frac {1}{b^{9}9}}+\cdots \\&=\sum _{k=1}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {\sin {\frac {k\pi }{2}}}{k}}\right]={\frac {1}{b}}\sum _{k=0}^{\infty }\left[{\frac {1}{b^{4k}}}\left({\frac {1}{4k+1}}+{\frac {-b^{-2}}{4k+3}}\right)\right]\\&={\frac {1}{b}}P\left(1,b^{4},4,\left(1,0,-b^{-2},0\right)\right).\end{aligned}}}$

Notare infatti che la notazione P può essere generalizzata anche al caso in cui b non sia un numero intero.

Confronto tra la formula BBP ed altri metodi di calcolo di pi greco

L'algoritmo basato sulla formula BBP per il calcolo di ${\displaystyle \pi }$ non richiede particolari tipi di dato e consente di calcolare l'n-esima cifra senza dover calcolare le prime n − 1 cifre.

Sebbene la formula BBP possa calcolare direttamente il valore di qualsiasi cifra data di ${\displaystyle \pi }$ con meno sforzo computazionale rispetto alle formule che necessitano il calcolo delle precedenti, l'algoritmo rimane di complessità linearitmica (${\displaystyle O(n\log n)}$), il che significa che valori di n via via più grandi richiedono sempre più tempo per essere calcolati; cioè, più una cifra si trova lontana, più tempo impiega l'algoritmo BBP per calcolarla, proprio come gli algoritmi standard di calcolo di ${\displaystyle \pi }$.^[6]

Note

Collegamenti esterni

• (EN) Eric W. Weisstein, Formula di Bailey–Borwein–Plouffe, su MathWorld, Wolfram Research.

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