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

$a=\sum _{k=0}^{\infty }{\frac {p(k)}{b^{k}q(k)}}\;$

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:

$\pi =\sum _{k=0}^{\infty }{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right).$

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

$\ln 2=\sum _{k=1}^{\infty }{\frac {1}{2^{k}k}}\;$

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

$\pi =4F(1/4,5/4;1;-1/4)+2\arctan(1/2)-\ln 5,$

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 bⁿa — 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

$\{2^{n}\ln 2\}=\left\{\left\{\sum _{k=1}^{n}{\frac {2^{n-k}}{k}}\right\}+\sum _{k=n+1}^{\infty }{\frac {2^{n-k}}{k}}\right\},$

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

$\{2^{n}\ln 2\}=\left\{\left\{\sum _{k=1}^{n}{\frac {2^{n-k}\;{\bmod {\,}}k}{k}}\right\}+\sum _{k=n+1}^{\infty }{\frac {2^{n-k}}{k}}\right\}.$

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, $\pi {\sqrt {3}}$ och $\pi ^{2}$, och ett exempel på en decimal BBP-formel är

$\ln \left({\frac {9}{10}}\right)={\frac {-1}{10}}\sum _{k=1}^{\infty }{\frac {1}{10^{k}k}}.$

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

$\ln 3=2\sum _{k=1}^{\infty }{\frac {1}{4^{k}}}\left({\frac {1}{2k+1}}\right)$

$\pi {\sqrt {3}}={\frac {9}{32}}\sum _{k=0}^{\infty }{\frac {1}{64^{k}}}\left({\frac {16}{6k+1}}+{\frac {8}{6k+2}}-{\frac {2}{6k+4}}-{\frac {1}{6k+5}}\right)$

$\pi ^{2}={\frac {9}{8}}\sum _{k=0}^{\infty }{\frac {1}{64^{k}}}\left({\frac {16}{(6k+1)^{2}}}-{\frac {24}{(6k+2)^{2}}}-{\frac {8}{(6k+3)^{2}}}-{\frac {6}{(6k+4)^{2}}}+{\frac {1}{(6k+5)^{2}}}\right)$

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