title: Formula di Bailey–Borwein–Plouffe
text: # Formula di Bailey–Borwein–Plouffe
  
  La formula di Bailey–Borwein–Plouffe, nota anche come formula BBP, è una formula per il calcolo di $\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.. La formula è la seguente:
  
      $\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 $\pi$ (e quindi anche della n-esima cifra binaria di $\pi$) senza calcolare le cifre precedenti. La formula non consente di calcolare l'n-esima cifra decimale di $\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 $\pi$. L'esistenza della formula BBP è stata una sorpresa: infatti si riteneva che calcolare l'n-esima cifra di $\pi$ fosse altrettanto difficile quanto calcolare le prime n cifre.
  
  La formula può anche essere riscritta come rapporto tra due polinomi:
  
      $\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.
  
  A partire dalla sua scoperta, sono state trovate altre formule nella forma generale
  
      $\alpha =\sum _{k=0}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {p(k)}{q(k)}}\right]$
  
  per molti altri numeri irrazionali $\alpha$, dove $p(k)$ e $q(k)$ sono polinomi con coefficienti interi e $b\geq 2$ è una base intera. Formule di questa tipologia sono conosciute come formule di tipo BBP. Dato un numero $\alpha$, non esiste un algoritmo noto per trovare i valori appropriati di $p(k)$, $q(k)$ e $b$; infatti tali formule vengono scoperte in modo sperimentale.
  
  ## Specializzazioni
  
  Una specializzazione della formula generale che ha prodotto molti risultati è la seguente:
  
      $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 $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:
  
      $\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:
  
      $\pi =P{\bigl1,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:
  
      ${\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{\bigl1,10,1,(1){\bigr )},\end{aligned}}$
      ${\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{\bigl1,2,1,(1){\bigr )}.\end{aligned}}$
  
  essendo valida la seguente identità per ogni a > 1: $\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:
  
      ${\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 $\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 $\pi$ con meno sforzo computazionale rispetto alle formule che necessitano il calcolo delle precedenti, l'algoritmo rimane di complessità linearitmica ($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 $\pi$.
  
  