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 . È 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:
La formula BBP dà origine ad un algoritmo di tipo spigot per il calcolo dell'n-esima cifra esadecimale (in base 16) di (e quindi anche della n-esima cifra binaria di ) senza calcolare le cifre precedenti. La formula non consente di calcolare l'n-esima cifra decimale di (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 .[2] L'esistenza della formula BBP è stata una sorpresa: infatti si riteneva che calcolare l'n-esima cifra di fosse altrettanto difficile quanto calcolare le prime n cifre.[1]
La formula può anche essere riscritta come rapporto tra due polinomi:
la cui dimostrazione è piuttosto semplice.[3]
A partire dalla sua scoperta, sono state trovate altre formule nella forma generale
per molti altri numeri irrazionali , dove e sono polinomi con coefficienti interi e è una base intera.[4] Formule di questa tipologia sono conosciute come formule di tipo BBP.[5] Dato un numero , non esiste un algoritmo noto per trovare i valori appropriati di , e ; infatti tali formule vengono scoperte in modo sperimentale.
Specializzazioni
[modifica | modifica wikitesto]Una specializzazione della formula generale che ha prodotto molti risultati è la seguente:
- ,
dove s, b e m sono numeri interi, e è una sequenza di numeri interi. La funzione P porta ad una notazione compatta per alcune soluzioni. Ad esempio, la formula BBP:
può essere scritta come:
Formule di tipo BBP già note
[modifica | modifica wikitesto]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:
essendo valida la seguente identità per ogni a > 1: .
A Plouffe è dovuta anche la seguente formula, ricavabile a partire dallo sviluppo di Maclaurin dell'arcotangente:
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
[modifica | modifica wikitesto]L'algoritmo basato sulla formula BBP per il calcolo di 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 con meno sforzo computazionale rispetto alle formule che necessitano il calcolo delle precedenti, l'algoritmo rimane di complessità linearitmica (), 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 .[6]
Note
[modifica | modifica wikitesto]- ^ a b (EN) David H. Bailey, Peter B. Borwein e Simon Plouffe, On the Rapid Computation of Various Polylogarithmic Constants, in Mathematics of Computation, vol. 66, n. 218, 1997, pp. 903–913, DOI:10.1090/S0025-5718-97-00856-9.
- ^ (EN) Eric W. Weisstein, Digit-Extraction Algorithm, in MathWorld, Wolfram Research.
- ^ (EN) David H. Bailey, Jonathan M. Borwein, Peter B. Borwein e Simon Plouffe, The quest for pi, in Mathematical Intelligencer, vol. 19, n. 1, 1997, pp. 50–57, DOI:10.1007/BF03024340.
- ^ (EN) David H. Bailey, A compendium of BBP-type formulas for mathematical constants, updated 15 Aug 2017 (PDF), su davidhbailey.com.
- ^ (EN) Eric W. Weisstein, BBP Formula, in MathWorld, Wolfram Research.
- ^ (EN) David H. Bailey, The BBP Algorithm for Pi (PDF), su experimentalmath.info, 8 settembre 2006.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Formula di Bailey-Borwein-Plouffe, su MathWorld, Wolfram Research.