BBP-formel

En BBP-formel (efter David H. Bailey, Peter Borwein och Simon Plouffe) är inom matematik en formel för ett reellt tal a i form av en serie

där b är ett heltal och p samt q är polynom. Om en sådan formel existerar för ett tal a kan den användas för att beräkna siffror på godtyckliga positioner i talets representation i basen b, utan att först beräkna föregående siffror. BBP-formler är kända för diverse matematiska konstanter, däribland π.

Upptäckt av BBP-formler och BBP-formeln för π 

Den mest kända BBP-formeln är följande för π i basen 16, ibland helt enkelt omnämnd som BBP-formeln:

Formeln upptäcktes 1995 av Simon Plouffe, som publicerade resultatet i en artikel författad tillsammans med David H. Bailey och Peter Borwein. Borwein och Plouffe hade samma år observerat att den välkända formeln

för den naturliga logaritmen av 2 kan användas för att beräkna talets binära siffror på godtyckliga positioner. De insåg att en sådan beräkning är möjlig för varje konstant som har en liknande formel, och började genomsöka litteraturen i jakt på ytterligare exempel. Ett tjugotal serier för diverse tal visade sig vara kända, men ingen formel tycktes existera för π.

Borwein och Plouffe använde då en datorimplementation av PSLQ-algoritmen för att numeriskt söka efter en formel för π. Efter någon månad av beräkningar matade programmet ut formeln

där F är en hypergeometrisk funktion och arctan betecknar den inversa tangensfunktionen. Serieutveckling av högerledet ger upphov till den nämnda BBP-formeln för π.

Algoritm för beräkning av enskilda siffror 

För att effektivt beräkna siffran på position n+1 av ett tal a givet av en BBP-formel i basen b måste formeln först skrivas om. Idén är att beräkna de första siffrorna i bråkdelen av bna — finessen med en BBP-formel är att heltalsdelen kan ignoreras under beräkningen. Om {x} betecknar bråkdelen av x (x modulo 1) gäller exempelvis för ln 2-formeln att

och eftersom potensen i den första summan endast ger ett bidrag modulo k gäller även att

Den högra summan konvergerar snabbt, och den vänstra kan beräknas effektivt med hjälp av modulär binär exponentiering för potenserna. Hela beräkningen kan utföras med flyttal med fix precision, och tidsåtgången är därför endast O(n lg n), där den logaritmiska faktorn beror på potensberäkningar.

En BBP-formel för π utnyttjades 2000 av distributed computing-projektet Pihex för att beräkna 64 binära siffror i följd omkring den tusenbiljonte (som råkar vara 0).

Icke-binära BBP-formler 
De flesta kända BBP-formlerna är binära, och tillåter därmed beräkningar i baserna 2, 4, 8, 16, och så vidare. En sådan formel kan dock inte användas för att beräkna isolerade siffror av ett tal i en bas som inte är en tvåpotens. Därför kan inte någon av de binära BBP-formlerna för π användas för att effektivt beräkna exempelvis godtyckliga decimaler av π.

BBP-formler i basen 3 är kända för exempelvis ln 2, ln 3,  och , och ett exempel på en decimal BBP-formel är

Det är dessvärre bevisat att π inte har någon icke-binär BBP-formel som är baserad på inversa tangensfunktioner av rationella tal. Enligt David Bailey och Jonathan Borwein finns det därmed troligtvis inte någon icke-binär BBP-formel för π över huvud taget. Detta omöjliggör dock inte existensen av icke-binära formler av någon annan typ för siffrorna i π. Faktum är att sådana formler är kända, men ingen har kommit i närheten av den beräkningsmässiga effektiviteten hos en BBP-formel.

Diverse exempel på BBP-formler

Källor 
 Jonathan Borwein & David Bailey, Mathematics by Experiment: Plausible Reasoning in the 21st Century, A K Peters 2003, s. 118–133.
 Simon Plouffe - The story behind a formula for Pi - inlägg på sci.math och sci.math.symbolic, 23 juni 2003

Externa länkar 
 BBP Formula - MathWorld
 BBP-Type Formula - Mathworld
 PiHex
 Implementation av BBP-algoritmen för att beräkna π i Python

Matematiska konstanter
Algoritmer