Don't take life too seriously: it's just a temporary situation

Calcolo di cifre singole di π (problema del)

Analisi  Problemi 

Nel 1995 David H. Bailey, Peter Benjamin Borwein e Simon Plouffe stupirono il mondo della matematica con un algoritmo che per la prima volta permetteva di calcolare l’n-esima cifra di π in base 2, senza calcolare le precedenti, un numero di operazioni che cresce come nlog3n.

 

Algoritmi analoghi furono poi scoperti per il calcolo di altre costanti, come log2, log3, log10, log22, πlog2 e π2, sempre in base 2.

 

Algoritmi simili furono anche scoperti per il calcolo di cifre singole di alcune costanti in basi diverse da 2, per esempio, π2 e vari logaritmi di interi in base 3, e addirittura alcuni per il calcolo di cifre singole di alcune costanti in qualsiasi base.

 

I matematici iniziarono quindi a cercare un algoritmo del genere, capace di dare una singola cifra di π o di un’altra costante trascendente in base 10, ma nel 2002 Bailey raffreddò gli entusiasmi, dimostrando che non esiste alcun algoritmo del tipo di quello scoperto da lui e dai suoi colleghi per calcolare le cifre di π in una base che non sia 2 o una potenza di 2.

 

Questo non esclude l’esistenza di un algoritmo del genere, ma rende più ardua la ricerca.

 

Si conosce un algoritmo per il calcolo della n-esima cifra di π in qualsiasi base, ma il tempo di calcolo cresce circa come n2, quindi non è utilizzabile per n molto grande.

 

Il problema più importante relativo al calcolo di cifre singole di π è quindi l’esistenza di un algoritmo per il calcolo della n-esima cifra decimale, che richieda un numero di operazioni all’incirca proporzionale a n.

Vedi anche

π.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.