Bailey–Borwein–Plouffe-formula

A Bailey–Borwein–Plouffe-formula (BBP-formula) $\pi$ értékét számító algoritmus. 1995-ben fedezte fel Simon Plouffe, és a cikk szerzőiről, David H. Baileyről, Peter Borweinról és Plouffe-ról kapta nevét. Korábban Plouffe saját oldalán is közölte. A képlet:

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

A képlet a $\pi$ n. számjegyét adja meg hexadecimális számrendszerben. Egy másik képlet, melyet Plouffe 2022-ben fedezett fel, lehetővé teszi a π n. számjegyének számítását decimális számrendszerben. A BBP-t és az általa ihletett algoritmusokat használja például a PiHex a π számjegyei számítására elosztott számítással. E képlet léte meglepő volt – korábban úgy tűnt, hogy a π n. számjegyének számítása az első n számjegy számításával azonos nehézségű.

Felfedezése óta általános

$\alpha =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^k}\frac{p(k)}{q(k)}\right]$

alakú képleteket fedeztek fel sok más irracionális $\alpha$-ra, ahol $p(k)$ és $q(k)$ egész együtthatós polinomok, $b\ge 2$ a számrendszer alapja. Ezek BBP-típusú formulák. Nincs ismert rendszeres algoritmus a megfelelő $p(k)$, $q(k)$ és $b$ megtalálására, ezek kísérletileg fedezhetők fel.

Specializációk

A sok eredményt adó általános képlet egy specializációja:

$P(s,b,m,A)=\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^k}\sum _{j=1}^m\frac{a_j}{(mk+j{)}^s}\right],$

ahol s, b és m egészek, $A=(a_1,a_2,\dots ,a_m)$ egészszám-sorozat. A P függvény egyes megoldásokra kompakt jelölést ad. Például az eredeti BBP képlet:

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

felírható az alábbi alakban:

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

Korábban ismert BBP-szerű formulák

Néhány egyszerű ilyen képlet, mely a BBP előtt ismert volt, és ahol a P függvény jelölése egyszerű:

$\begin{array}{cc}\ln \frac{10}{9}& =\frac{1}{10}+\frac{1}{200}+\frac{1}{3000}+\frac{1}{40000}+\frac{1}{500000}+\cdots \\ & =\sum _{k=1}^{\mathrm{\infty }}\frac{1}{10^k\cdot k}=\frac{1}{10}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{10^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{10}P(1,10,1,(1)),\end{array}$

$\begin{array}{cc}\ln 2& =\frac{1}{2}+\frac{1}{2\cdot 2^2}+\frac{1}{3\cdot 2^3}+\frac{1}{4\cdot 2^4}+\frac{1}{5\cdot 2^5}+\cdots \\ & =\sum _{k=1}^{\mathrm{\infty }}\frac{1}{2^k\cdot k}=\frac{1}{2}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{2^k}\left(\frac{1}{k+1}\right)\right]\\ & =\frac{1}{2}P(1,2,1,(1)).\end{array}$

Általában az alábbi azonosság igaz $a>1$-re:

$\ln \frac{a}{a-1}=\sum _{k=1}^{\mathrm{\infty }}\frac{1}{k{a}^k}$

Plouffe-ot ihlette az árkusz tangens végtelen sora, melynek képlete (a P jelölés általánosítható nem egész b-re is):

$\begin{array}{cc}\arctan \frac{1}{b}& =\frac{1}{b}-\frac{1}{b^{3}3}+\frac{1}{b^{5}5}-\frac{1}{b^{7}7}+\frac{1}{b^{9}9}+\cdots \\ & =\sum _{k=1}^{\mathrm{\infty }}\left[\frac{1}{b^k}\frac{\sin \frac{k\pi }{2}}{k}\right]=\frac{1}{b}\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{b^{4k}}(\frac{1}{4k+1}+\frac{-b^{-2}}{4k+3})\right]\\ & =\frac{1}{b}P(1,b^4,4,(1,0,-b^{-2},0)).\end{array}$

Új egyenlőségek keresése

A fenti P függvény használatával a legegyszerűbb képlet π-re $s=1;m>1$ esetén adódik. Számos képlet ismert egyes sok osztóval rendelkező b-re és m-re, ahol az A sorozat számos tagja 0. E formulák felfedezése ilyen lineáris kombinációk számítógépes keresését igényli az egyes összegek számítása után. A keresési folyamat s, b és m tartományainak kiválasztásából, az összeg hosszú kiértékeléséből, egészreláció-kereső algoritmust (általában Helaman Ferguson PSLQ-algoritmusát) használva A megtalálásából áll, melyeknél az összeg ismert állandó vagy 0.

A pi BBP-képlete

Az eredeti BBP π-összegző képletet 1995-ben fedezte fel Plouffe a PSLQ algoritmussal. A P függvénnyel is felírható:

$\begin{array}{cc}\pi & =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})\right]\\ & =P(1,16,8,(4,0,0,-2,-1,-1,0,0)),\end{array}$

Ez két polinom hasonló arányára egyszerűsödik:

$\pi =\sum _{k=0}^{\mathrm{\infty }}\left[\frac{1}{16^k}\left(\frac{120k^2+151k+47}{512k^4+1024k^3+712k^2+194k+15}\right)\right].$

E képlet π-vel való egyenlőségének bizonyítása egyszerű volt.

A π BBP számjegyszámító algoritmusa

Az n. hexadecimális számjegy képletéhez néhány változtatás szükséges. Először a képlet átírása az alábbi alakra:

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

Adott n-re az első összeget számítva a végtelen összeget az n. tagnál elválasztva:

$\sum _{k=0}^{\mathrm{\infty }}\frac{1}{\left(16^k\right)(8k+1)}=\sum _{k=0}^n\frac{1}{\left(16^k\right)(8k+1)}+\sum _{k=n+1}^{\mathrm{\infty }}\frac{1}{\left(16^k\right)(8k+1)}.$

$16^n$-nel szorozva, mely a szám egész és törtrészét az n. helyre helyezi:

$\sum _{k=0}^{\mathrm{\infty }}\frac{16^{n-k}}{8k+1}=\sum _{k=0}^n\frac{16^{n-k}}{8k+1}+\sum _{k=n+1}^{\mathrm{\infty }}\frac{16^{n-k}}{8k+1}.$

Mivel csak a törtrész a fontos, összehasonlítva a két tagot, látható, hogy csak az első összeg ad ki egészeket, vagyis a második összeg nem ad ki egészt, mivel a számláló $k>n$ esetén nem lehet a nevezőnél nagyobb. Így az első összegből ki kell vonni az egészeket a $8k+1$-es maradék számításával. Az első törtrész összege:

$\sum _{k=0}^n\frac{16^{n-k}mod(8k+1)}{8k+1}+\sum _{k=n+1}^{\mathrm{\infty }}\frac{16^{n-k}}{8k+1}.$

Látható, hogy a maradékoperátor biztosítja, hogy csak a törtrész marad. $16^{n-k}mod(8k+1)$ számításához a moduláris hatványozás használható. Ha a szorzat 1-nél nagyobb, a modulus kivonása történik, hasonlóan az összegekhez. A számítás végén ez mind a 4 összegre elvégzendő, ezután a 4 összeg visszakerül a π-hez tartozó összegbe:

$4{\mathrm{\Sigma }}_1-2{\mathrm{\Sigma }}_2-{\mathrm{\Sigma }}_3-{\mathrm{\Sigma }}_4.$

Mivel csak a törtrész pontos, a szükséges számjegy számítása az egész rész eltávolítását és a 16-tal való szorzást igényli (elvben a számítási pontosságig terjedő számjegyek is pontosak).

E folyamat hasonló a szorzáshoz, de csak néhány középső oszlop adandó össze. Bár vannak nem számított átvitelek, általában a számítógépek sok (32 vagy 64) biten végeznek számításokat, majd kerekítenek, és csak a legértékesebb számjegyek a fontosak. Lehetséges azonban, hogy egy adott számítás hasonló lehet egy kis szám (például az 1) Sablon:Adat-hez való hozzáadásakori hibával, amely hiba a legértékesebb számjegyekig végigmegy.

A BBP és más π-számító módszerek összehasonlítása

Ez az algoritmus a π-t speciális, több ezer vagy millió számjegyes adattípusok nélkül számítja, az n. számjegyet az azt megelőző $n-1$ nélkül számítja, és kis, hatékony adattípusokat használ.

Bár a BBP-formula tetszőleges számjegyet kisebb erőforrásigénnyel számít az összes köztes számjegyet számító képleteknél, a BBP linearitmikus ($O(n\log n)$) marad: minél nagyobb n, vagyis minél későbbi a számítandó számjegy, annál több idő kell a számításhoz, hasonlóan a hagyományos π-számító algoritmusokhoz.

Általánosítás

D. J. Broadhurst a BBP algoritmust más konstansok számítására általánosítja nagyjából lineáris idő- és logaritmikus helyigénnyel. Eredményeket ad meg a Catalan-állandóra, a ${\pi }^3$-ra, a ${\pi }^4$, az Apéry-állandóra ($\zeta (3)$), $\zeta (5)$-re (ahol $\zeta (x)$ a Riemann-féle zéta-függvény), ${\ln }^{3}2$-re, ${\ln }^{4}2$-re, ${\ln }^{5}2$-re és $\pi$ és $\ln 2$ különböző hatványainak szorzataira. Ezeket elsősorban polilogaritmus-létrák használatával éri el.

Források

• D. J. Broadhurst, "Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5)", (1998) arXiv math.CA/9803067

• Richard J. Lipton, "Making An Algorithm An Algorithm — BBP", weblog post, July 14, 2010.
• Richard J. Lipton, "Cook’s Class Contains Pi", weblog post, March 15, 2009.
• Sablon:Cite web
• David H. Bailey, "BBP Code Directory", web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006.