Visualizza wikitesto di 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 greco|<math>\pi</math>]]. È stata scoperta nel 1995 da [[Simon Plouffe]] ed è così chiamata in onore degli autori dell'articolo in cui è stata pubblicata: [[David Harold Bailey|David H. Bailey]], [[Peter Borwein]] e Plouffe.<ref name="BBP">{{cita pubblicazione
 | cognome= Bailey | nome= David H. |wkautore=David Harold Bailey| cognome2= Borwein | nome2= Peter B. |wkautore2=Peter Borwein| cognome3= Plouffe | nome3= Simon|
wkautore3=Simon Plouffe
 | anno= 1997
 | titolo= On the Rapid Computation of Various Polylogarithmic Constants
 | url= https://archive.org/details/sim_mathematics-of-computation_1997-04_66_218/page/903 | rivista= Mathematics of Computation
 | volume = 66 | numero= 218 | pp= 903-913
 | lingua=en
 | doi = 10.1090/S0025-5718-97-00856-9}}</ref> La formula è la seguente:
:<math>  \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]</math>

La formula BBP dà origine ad un algoritmo di tipo ''spigot'' per il calcolo dell{{'}}''n''-esima cifra [[Sistema numerico esadecimale|esadecimale]] (in base 16) di <math>\pi</math> (e quindi anche della ''n''-esima cifra [[Sistema numerico binario|binaria]] di <math>\pi</math>) senza calcolare le cifre precedenti. La formula non consente di calcolare l{{'}}''n''-esima cifra [[Sistema numerico decimale|decimale]] di <math>\pi</math> (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 <math>\pi</math>.<ref name="MathWorld">{{MathWorld|id=Digit-ExtractionAlgorithm|nome=Digit-Extraction Algorithm}}</ref> L'esistenza della formula BBP è stata una sorpresa: infatti si riteneva che calcolare l{{'}}''n''-esima cifra di <math>\pi</math> fosse altrettanto difficile quanto calcolare le prime ''n'' cifre.<ref name="BBP" />

La formula può anche essere riscritta come rapporto tra due polinomi:
: <math>\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]</math>

la cui dimostrazione è piuttosto semplice.<ref name=QuestForPi>{{Cita pubblicazione | cognome= Bailey | nome= David H. |wkautore=David Harold Bailey| cognome2= Borwein | nome2= Jonathan M. | cognome3= Borwein | nome3= Peter B. |wkautore3=Peter Borwein| cognome4= Plouffe | nome4= Simon |wkautore4=Simon Plouffe| anno= 1997 | rivista= [[Mathematical Intelligencer]] | volume = 19 | numero= 1 | pp= 50-57 | doi=10.1007/BF03024340 | titolo=The quest for pi| url= https://archive.org/details/sim_mathematical-intelligencer_winter-1997_19_1/page/50 | lingua=en}}</ref>

A partire dalla sua scoperta, sono state trovate altre formule nella forma generale
:<math>\alpha = \sum_{k = 0}^\infty \left[ \frac{1}{b^k} \frac{p(k)}{q(k)} \right]</math>
per molti altri numeri irrazionali <math>\alpha</math>, dove <math>p(k)</math> e <math>q(k)</math> sono polinomi con coefficienti interi e <math>b \geq 2</math> è una [[Base (aritmetica)|base]] intera.<ref name="compendium">{{Cita web
|url=https://www.davidhbailey.com/dhbpapers/bbp-formulas.pdf
|nome=David H.
|cognome=Bailey
|wkautore=David Harold Bailey
|titolo=A compendium of BBP-type formulas for mathematical constants, updated 15 Aug 2017
|lingua=en}}</ref>
Formule di questa tipologia sono conosciute come '''formule di tipo BBP'''.<ref name="Ref_a">{{MathWorld|id=BBPFormula|nome=BBP Formula}}</ref> Dato un numero <math>\alpha</math>, non esiste un algoritmo noto per trovare i valori appropriati di <math>p(k)</math>, <math>q(k)</math> e <math>b</math>; infatti tali formule vengono scoperte in [[Matematica sperimentale|modo sperimentale]].

== Specializzazioni ==
Una specializzazione della formula generale che ha prodotto molti risultati è la seguente:
: <math> 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]</math>,
dove ''s'', ''b'' e ''m'' sono numeri interi, e <math>A = (a_1, a_2, \dots, a_m)</math> è una sequenza di numeri interi.
La funzione ''P'' porta ad una notazione compatta per alcune soluzioni. Ad esempio, la formula BBP:
:<math> \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]</math>
può essere scritta come:
: <math> \pi = P\bigl(1, 16, 8, (4, 0, 0, -2, -1, -1) \bigr).</math>

=== 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:
: <math>\begin{align}
 \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{align}</math>
: <math>\begin{align}
 \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{align}</math>

essendo valida la seguente identità per ogni ''a'' > 1: <math>\ln\frac{a}{a-1} = \sum_{k=1}^\infty \frac{1}{a^k \cdot k}</math>.

A Plouffe è dovuta anche la seguente formula, ricavabile a partire dallo [[Serie_di_Taylor#Serie_di_Maclaurin|sviluppo di Maclaurin]] dell'[[arcotangente]]:
: <math>\begin{align}
 \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{align}</math>
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 <math>\pi</math> non richiede particolari [[Tipo_di_dato|tipi di dato]] e consente di calcolare l{{'}}''n''-esima cifra  ''senza'' dover calcolare le prime ''n''&nbsp;−&nbsp;1 cifre.

Sebbene la formula BBP possa calcolare direttamente il valore di qualsiasi cifra data di <math>\pi</math> con meno sforzo computazionale rispetto alle formule che necessitano il calcolo delle precedenti, l'algoritmo rimane di [[Complessità_temporale#Tempo_linearitmico|complessità linearitmica]] (<math>O(n \log n)</math>), 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 <math>\pi</math>.<ref>{{Cita web
 | cognome= Bailey
 | nome= David H.
|wkautore=David Harold Bailey
 | titolo= The BBP Algorithm for Pi
 | data= 8 settembre 2006
 | url    = https://www.experimentalmath.info/bbp-codes/bbp-alg.pdf
 | lingua=en}}</ref>

== Note ==
{{reflist}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Pi greco]]
[[Categoria:Formule matematiche]]
[[Categoria:Algoritmi per il calcolo del pi greco]]