Bailey-Borwein-Plouffejeva formula

Bailey-Borwein-Plouffejeva formula, oziroma formula BBP, je v matematiki formula za računanje števila π, ki jo je leta 1995 odkril kanadski matematik Simon Plouffe. Imenuje se po Davidu Haroldu Baileyju, Petru Borweinu in Plouffeju, avtorjih članka, kjer je bila formula prvič izdana. Določena je kot:

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

Formula omogoča doslej najboljši znan algoritem za računanje števk števila π (v šestnajstiškem sestavu), brez da bi poznali, oziroma računali predhodne. Takšen algoritem pipe (angl. spigot algorithm) obstaja tudi za e.

Odkritje formule je bilo presenečenje, saj so stoletja domnevali, da ne obstaja način za računanje n-te števke π, ne da bi prej izračunali n - 1 števk. Plouffe je imel zamisel o formuli dvajset let od leta 1974. Dejansko je vse delo v zvezi z odkritjem naredil sam, in bi jo upravičeno lahko imenovali Plouffejeva formula.

Formule tipa BBP

Od odkritja izvirne formule so odkrili več formul za vsote osnovnih iracionalnih konstant. Imajo obliko:

$\alpha =\sum _{k=0}^{\infty }{\frac {p(k)}{b^{k}q(k)}}\!\,,$

kjer je α konstanta, $p(k)$ in $q(k)$ polinoma s celoštevilskimi koeficienti, b pa osnova številskega sestava. Nekatere formule, kot je na primer Leibnizeva formula za π, lahko izrazimo v tej obliki, vendar je pri tem b pozitiven ali negativen, tako da nimajo lastnosti algoritma pipe, pa še v splošnem ne konvergirajo hitro. V nekaterih primerih je α pomnožen s kakšnim mnogokratnikom, na primer namesto π je 2π.

Formule v tej obliki so formule tipa BBP. Nekatere kombinacije $p(k)$, $q(k)$ in b vodijo do znanih konstant, ne obstaja pa splošni algoritem za preslikave in prave kombinacije odkrivajo z iskanjem.

Dve od najpreprostejših formul, ki so bile znane pred formulami tipa BBP, sta:

$\ln {\frac {9}{10}}=-\sum _{k=1}^{\infty }{\frac {1}{10^{k}k}}\!\,,$

$\ln 2=\sum _{k=1}^{\infty }{\frac {1}{2^{k}k}}\!\,.$

Plouffeja je navdahnila sorodna znana formula:

$\operatorname {tg} \,{\frac {1}{x}}={\frac {1}{x}}-{\frac {1}{3x^{3}}}+{\frac {1}{5x^{5}}}-{\frac {1}{7x^{7}}}+{\frac {1}{9x^{9}}}\ldots \!\,.$

Posebna vrsta splošne formule, iz katere izhaja več rezultatov, je:

$P(s,b,n,A)=\sum _{k=0}^{\infty }\left({\frac {1}{b^{k}}}\sum _{j=1}^{n}{\frac {a_{j}}{(nk+j)^{s}}}\right)\!\,,$

kjer so s, b in n cela števila, $A=(a_{1},a_{2},\ldots ,a_{n})$ pa vektor celih števil. Najpreprostejša formula za π je pri s = 1. Veliko nedavno odkritih formul je znanih za b kot eksponent 2 ali 3 in n kot eksponent 2 ali kakšen drug faktor. Pri več znanih formulah je več členov vektorja A enakih 0. Funkcija P je zgoščen zapis za nekatere rešitve. Za zgornji dve formuli je funkcija P:

$\ln {\frac {9}{10}}=-{\frac {1}{10}}P(1,10,1,(1))\!\,,$

$\ln 2={\frac {1}{2}}P(1,2,1,(1))\!\,.$

Pri iskanju se izberejo parametrične vrednosti za s, b in n, nato se izračuna n členov vsote na veliko decimalk in potem se s pomočjo iskalnega algoritma za celoštevilske zveze (po navadi s Fergusonovim algoritmom PSLQ) poišče vektor A, prek katerega dajo vmesne vsote znano konstanto ali morda vrednost nič.

Bailey-Borwein-Plouffejeva formula za π

Izvirno Plouffejevo formulo za π lahko zapišemo v enakovredni obliki kot količnik dveh polinomov:

$\pi =\sum _{n=0}^{\infty }{\frac {1}{16^{n}}}\left({\frac {120n^{2}+151n+47}{512n^{4}+1024n^{3}+712n^{2}+194n+15}}\right)\!\,,$

ali v zgoščenem zapisu s funkcijo P:

$\pi =P(1,16,8,(4,0,0,-2,-1,-1,0,0))\!\,.$

Veljavnost formule so strogo preverili.

Algoritem BBP

Formula daje algoritem za računanje šestnajstiških števk π. Za računanje števk moramo formulo prepisati v obliko:

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

Sedaj želimo najti m-to šestnajstiško števko π in prvo vsoto razdelimo prek m-tega člena:

$\sum _{n=0}^{\infty }{\frac {1}{16^{n}(8n+1)}}=\sum _{n=0}^{m}{\frac {1}{16^{n}(8n+1)}}+\sum _{n=m+1}^{\infty }{\frac {1}{16^{n}(8n+1)}}\!\,.$

Potem pomnožimo s $16^{m}$, tako da je šestnajstiška točka (delitev med ulomljenim in celim delom števila) na m-tem mestu:

$\sum _{n=0}^{\infty }{\frac {16^{m-n}}{8n+1}}=\sum _{n=0}^{m}{\frac {16^{m-n}}{8n+1}}+\sum _{n=m+1}^{\infty }{\frac {16^{m-n}}{8n+1}}\!\,.$

Ker nas zanima le ulomljeni del vsote, gledamo dva člena in ugotovimo, da le prvi člen da cela števila, drugi pa ne, ker števec ne more biti večji od imenovalca za n > m. Zato moramo odstraniti cela števila iz prve vsote. To naredimo z $\mod 8n+1$. Vsota za prvi ulomljeni del je potem:

$\sum _{n=0}^{m}{\frac {16^{m-n}\mod 8n+1}{8n+1}}+\sum _{n=m+1}^{\infty }{\frac {16^{m-n}}{8n+1}}\!\,.$

Operator modulo vedno zagotavlja, da bo ohranjen le ulomljeni del vsote. Za hitro in učinkovito računanje $16^{m-n}\mod 8n+1$ se uporabi algoritem modulskega potenciranja. Ko tekoči produkt postane večji od 1, se vzame modulo, podobno kot za tekočo skupno vrednost v vsaki vsoti.

Za celotni račun se to ponovi v vsakem koraku za vsako od štirih vsot. Potem se te šriri vsote vzamejo in se dajo nazaj v vsoto za π:

$4\Sigma _{1}-2\Sigma _{2}-\Sigma _{3}-\Sigma _{4}\!\,.$

Ker je točen le ulomljeni del, računanje želene števke zahteva da se celi del odstrani iz končne vsote in se pomnoži s 16, ter se na tem mestu »posname« šestnajstiška števka (v teoriji bo točnih nekaj naslednjih števk, kar je odvisno od točnosti računanja).

Ta postopek je podoben dolgemu množenju, kjer je treba seštevati po kakšnih srednjih stolpcih. Čeprav je treba prenašati vrednosti, ki niso vštete, računalniki po navadi računajo za več bitov (32 ali 64) in zaokrožajo, nas pa zanima le najbolj značilna števka ali števke. Obstaja majhna verjetnost, da pri računanju ne bo moč prišteti majhnega števila (na primer 1) k številu 999999999999999, in se bo napaka prenesla na najbolj značilno števko, kar se sicer pokaže pri končni vrednosti računanja.

Prednosti algoritma BBP

Ta algoritem računa π brez dodatnih podatkovnih tipov, ki bi imeli tisoče ali celo milijone števk. Z njim se izračuna n-ta števka brez računanja predhodnih n - 1 števk, in se lahko uporabljajo majhni in učinkoviti podatkovni tipi.

Algoritem je najhitrejši način za računanje n-te števke, oziroma nekaj števk v okolici n-te. Računski algoritmi za π, ki uporabljajo velike podatkovne tipe, ostajajo hitrejši, kadar je treba izračunati vse števke od 1 do n.

Posplošitve

D. J. Broadhurst je podal posplošitev algoritma BBP, s katerim se lahko izračuna vrednost drugih konstant v skoraj linearnem času in logaritemskem prostoru. Posebne vrednosti so dane za Catalanovo konstanto, $\pi ^{3}$, $\log ^{3}2$, Apéryjevo konstanto $\zeta (3)$, $\pi ^{4}$, $\log ^{4}2$, $\log ^{5}2$, $\zeta (5)$ in za različne produkte potenc $\pi$ in $\log 2$. Vrednosti so večinoma dobljene s pomočjo polilogaritemskih lestev.

Glej tudi

• Bellardova formula

Viri

• Bailey, David Harold; Borwein, Peter B.; Plouffe, Simon (april 1997). »On the Rapid Computation of Various Polylogarithmic Constants« (PDF). Mathematics of Computation. Zv. 66, št. 218. str. 903–913. Arhivirano iz prvotnega spletišča (PDF) dne 10. junija 2011. Pridobljeno 15. maja 2008.{{navedi revijo}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
• Broadhurst, D. J. (1998). »Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5)«. . {{navedi revijo}}: Sklic magazine potrebuje|magazine= (pomoč)

Zunanje povezave

• Weisstein, Eric Wolfgang. »BBP Formula«. MathWorld.
• Simon Plouffe, The story behind a formula for Pi - Zapis Newsgroup na sci.math in sci.math.symbolic, 23. junij 2003