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 $\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}^{\mathrm{\infty }}\left[\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})\right]$

La formula BBP dà origine ad un algoritmo di tipo spigot per il calcolo dellTemplate:'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 lTemplate:'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 lTemplate:'n-esima cifra decimale di $\pi$. L'esistenza della formula BBP è stata una sorpresa: infatti si riteneva che calcolare lTemplate:'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}^{\mathrm{\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}^{\mathrm{\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\ge 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}^{\mathrm{\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}^{\mathrm{\infty }}\left[\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})\right]$

può essere scritta come:

$\pi =P(1,16,8,(4,0,0,-2,-1,-1)).$

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{array}{cc}\ln \frac{10}{9}& =\frac{1}{10}+\frac{1}{200}+\frac{1}{3000}+\frac{1}{40000}+\frac{1}{500000}+\cdots \\ & =\sum _{k=1}^{\mathrm{\infty }}\frac{1}{10^k\cdot k}=\frac{1}{10}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{10^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{10}P(1,10,1,(1)),\end{array}$

$\begin{array}{cc}\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}^{\mathrm{\infty }}\frac{1}{2^k\cdot k}=\frac{1}{2}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{2^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{2}P(1,2,1,(1)).\end{array}$

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

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

$\begin{array}{cc}\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}^{\mathrm{\infty }}\left[\frac{1}{b^k}\frac{\sin \frac{k\pi }{2}}{k}\right]=\frac{1}{b}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^{4k}}(\frac{1}{4k+1}+\frac{-b^{-2}}{4k+3})\right]\\ & =\frac{1}{b}P(1,b^4,4,(1,0,-b^{-2},0)).\end{array}$

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 lTemplate:'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$.

Collegamenti esterni

• Template:Collegamenti esterni