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}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\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}^{\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\geq 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}^{\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}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]$

felírható az alábbi alakban:

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

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{aligned}\ln {\frac {10}{9}}&={\frac {1}{10}}+{\frac {1}{200}}+{\frac {1}{3\ 000}}+{\frac {1}{40\,000}}+{\frac {1}{500\,000}}+\cdots \\&=\sum _{k=1}^{\infty }{\frac {1}{10^{k}\cdot k}}={\frac {1}{10}}\sum _{k=0}^{\infty }\left[{\frac {1}{10^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{10}}P{\bigl (}1,10,1,(1){\bigr )},\end{aligned}}$

${\begin{aligned}\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}^{\infty }{\frac {1}{2^{k}\cdot k}}={\frac {1}{2}}\sum _{k=0}^{\infty }\left[{\frac {1}{2^{k}}}\left({\frac {1}{k+1}}\right)\right]\\&={\frac {1}{2}}P{\bigl (}1,2,1,(1){\bigr )}.\end{aligned}}$

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

$\ln {\frac {a}{a-1}}=\sum _{k=1}^{\infty }{\frac {1}{ka^{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{aligned}\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}^{\infty }\left[{\frac {1}{b^{k}}}{\frac {\sin {\frac {k\pi }{2}}}{k}}\right]={\frac {1}{b}}\sum _{k=0}^{\infty }\left[{\frac {1}{b^{4k}}}\left({\frac {1}{4k+1}}+{\frac {-b^{-2}}{4k+3}}\right)\right]\\&={\frac {1}{b}}P\left(1,b^{4},4,\left(1,0,-b^{-2},0\right)\right).\end{aligned}}$

Ú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{aligned}\pi &=\sum _{k=0}^{\infty }\left[{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)\right]\\&=P{\bigl (}1,16,8,(4,0,0,-2,-1,-1,0,0){\bigr )},\end{aligned}}$

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

$\pi =\sum _{k=0}^{\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}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+1)}}-2\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+4)}}-\sum _{k=0}^{\infty }{\frac {1}{\left(16^{k}\right)(8k+5)}}-\sum _{k=0}^{\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}^{\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}^{\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}^{\infty }{\frac {16^{n-k}}{8k+1}}=\sum _{k=0}^{n}{\frac {16^{n-k}}{8k+1}}+\sum _{k=n+1}^{\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}{\bmod {(}}8k+1)}{8k+1}}+\sum _{k=n+1}^{\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\Sigma _{1}-2\Sigma _{2}-\Sigma _{3}-\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) 999 999 999 999 999-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.

Fordítás

Ez a szócikk részben vagy egészben a Bailey–Borwein–Plouffe formula című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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.
• A compendium of BBP-type formulas for mathematical constants, updated 15 Aug 2017. (Hozzáférés: 2019. március 31.)
• David H. Bailey, "BBP Code Directory", web page with links to Bailey's code implementing the BBP algorithm, September 8, 2006.