Bailey – Borwein – Plouffe formel - Bailey–Borwein–Plouffe formula

Den Bailey-Borwein-Plouffe formel ( BBP formel ) er en formel for $π$ . Den ble oppdaget i 1995 av Simon Plouffe og er oppkalt etter forfatterne av artikkelen der den ble publisert, David H. Bailey , Peter Borwein og Plouffe. Før det hadde den blitt utgitt av Plouffe på hans eget nettsted. Formelen er

{\ displaystyle \ 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]}

BBP formel gir opphav til en spissende algoritme for beregning av den n te basis-16 (heksadesimalt) siffer av $π$ (og dermed også den n- te binærsiffer av $π$ ) uten beregning av de foregående siffer. Dette betyr ikke beregne den n te desimal av $π$ (dvs. i bunnen 10). BBP- og BBP-inspirerte algoritmer har blitt brukt i prosjekter som PiHex for å beregne mange sifre på $π$ ved hjelp av distribuert databehandling. Eksistensen av denne formelen kom som en overraskelse. Det var en utbredt oppfatning at å beregne det n. sifferet i $π$ er like vanskelig som å beregne de første n -sifrene.

Siden oppdagelsen, formler av den generelle formen

{\ displaystyle \ alpha = \ sum _ {k = 0}^{\ infty} \ left [{\ frac {1} {b^{k}}} {\ frac {p (k)} {q (k) }}\Ikke sant]}

er blitt oppdaget i mange andre irrasjonale tall , hvor og er polynomer med heltallige koeffisienter og er et helt tall basen . Formler av denne formen er kjent som BBP-formler . Gitt et tall , er det ingen kjent systematisk algoritme for å finne passende , og ; slike formler oppdages eksperimentelt . ${\ displaystyle \ alpha}$ ${\ displaystyle p (k)}$ ${\ displaystyle q (k)}$ ${\ displaystyle b \ geq 2}$ ${\ displaystyle \ alpha}$ ${\ displaystyle p (k)}$ ${\ displaystyle q (k)}$ ${\ displaystyle b}$

Spesialiseringer

En spesialisering av den generelle formelen som har gitt mange resultater er

{\ displaystyle P (s, b, m, A) = \ sum _ {k = 0}^{\ infty} \ left [{\ frac {1} {b^{k}}} \ sum _ {j = 1}^{m} {\ frac {a_ {j}} {(mk+j)^{s}}} \ høyre],}

hvor s , b og m er heltall, og er en sekvens av heltall. De P funksjons fører til en kompakt notasjon for noen løsninger. For eksempel den opprinnelige BBP -formelen ${\ displaystyle A = (a_ {1}, a_ {2}, \ dots, a_ {m})}$

{\ displaystyle \ 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]}

kan skrives som

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

Tidligere kjente formler av BBP-type

Noen av de enkleste formlene av denne typen som var godt kjent før BBP og som P -funksjonen fører til en kompakt notasjon, er:

{\ displaystyle {\ begin {align} \ 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}}} \ venstre ({\ frac {1} {k+1}} \ høyre) \ høyre] \\ & = {\ frac {1} {10}} P { \ bigl (} 1,10,1, (1) {\ bigr)}, \ ende {justert}}}

{\ displaystyle {\ begin {align} \ 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} \ venstre [{\ frac {1} {2^{k}}} \ venstre ({\ frac {1} {k+1}} \ høyre) \ høyre] \\ & = {\ frac {1} {2}} P {\ bigl (} 1,2,1, (1) {\ bigr)}. \ end {align}}}

(Faktisk gjelder denne identiteten for en > 1:

{\ displaystyle \ ln {\ frac {a} {a-1}} = \ sum _ {k = 1}^{\ infty} {\ frac {1} {a^{k} \ cdot k}}}

.)

Plouffe ble også inspirert av arctan power -serien i formen ( P -notasjonen kan også generaliseres til tilfellet der b ikke er et heltall):

{\ displaystyle {\ begin {align} \ 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} \ venstre [{\ frac {1} {b^{k}}} {\ frac {\ sin {\ frac {k \ pi} {2 }}} {k}} \ høyre] = {\ frac {1} {b}} \ sum _ {k = 0}^{\ infty} \ venstre [{\ frac {1} {b^{4k}} } \ venstre ({\ frac {1} {4k+1}}+{\ frac {-b^{-2}} {4k+3}} \ høyre) \ høyre] \\ & = {\ frac {1 } {b}} P \ venstre (1, b^{4}, 4, \ venstre (1,0, -b^{-2}, 0 \ høyre) \ høyre). \ ende {justert}}}

Jakten på nye likheter

Ved å bruke P- funksjonen nevnt ovenfor, er den enkleste kjente formelen for $π$ for s = 1, men m > 1. Mange nå oppdagede formler er kjent for b som en eksponent på 2 eller 3 og m som en eksponent på 2 eller noen annen faktorrik verdi, men hvor flere av begrepene i sekvens A er null. Oppdagelsen av disse formlene innebærer et datasøk etter slike lineære kombinasjoner etter beregning av de enkelte summene. Søkeprosedyren består i å velge et område av parameterverdier for s , b , og m , evaluere de beløp seg til mange sifre, og deretter ved hjelp av et heltall forhold finn algoritme (typisk Hela Ferguson 's PSLQ algoritme ) for å finne en sekvens A som summerer mellomliggende summer til en velkjent konstant eller kanskje til null.

BBP -formelen for $π$

Den opprinnelige BBP $π$ summeringsformelen ble funnet i 1995 av Plouffe ved bruk av PSLQ . Den er også representabel ved å bruke P -funksjonen ovenfor:

{\ displaystyle {\ begin {align} \ 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}} \ høyre) \ høyre] \\ & = P {\ bigl (} 1,16,8, (4,0,0, -2, -1, -1,0,0) {\ bigr)}, \ end {justert} }}

som også reduserer til dette ekvivalente forholdet på to polynomer:

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

Denne formelen har blitt vist gjennom et ganske enkelt bevis som er lik $π$ .

BBP sifferekstraksjonsalgoritme for $π$

Vi ønsker å definere en formel som returnerer den n- te heksadesimale siffer av $π$ . Noen få manipulasjoner kreves for å implementere en tappalgoritme ved hjelp av denne formelen.

Vi må først skrive om formelen som

{\ displaystyle \ pi = 4 \ sum _ {k = 0}^{\ infty} {\ frac {1} {\ venstre (16^{k} \ høyre) (8k+1)}}-2 \ sum _ {k = 0}^{\ infty} {\ frac {1} {\ venstre (16^{k} \ høyre) (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)}}.}

Nå, for en bestemt verdi av n og ved å ta den første summen, deler vi summen til uendelig på tvers av den n. Termen:

{\ displaystyle \ sum _ {k = 0}^{\ infty} {\ frac {1} {\ venstre (16^{k} \ høyre) (8k+1)}} = \ sum _ {k = 0} ^{n} {\ frac {1} {\ venstre (16^{k} \ høyre) (8k+1)}}+\ sum _ {k = n+1}^{\ infty} {\ frac {1 } {\ venstre (16^{k} \ høyre) (8k+1)}}}}

Vi multipliserer nå med 16 ⁿ , slik at det heksadesimale punktet (skillet mellom brøkdel og heltall av tallet) er på n: e plass:

{\ displaystyle \ sum _ {k = 0}^{\ infty} {\ frac {16^{nk}} {8k+1}} = \ sum _ {k = 0}^{n} {\ frac {16 ^{nk}} {8k+1}}+\ sum _ {k = n+1}^{\ infty} {\ frac {16^{nk}} {8k+1}}.}

Siden vi bare bryr oss om brøkdelen av summen, ser vi på våre to termer og innser at bare den første summen er i stand til å produsere hele tall; omvendt kan ikke den andre summen produsere hele tall, siden telleren aldri kan være større enn nevneren for k > n . Derfor trenger vi et triks for å fjerne hele tallene for den første summen. Det trikset er mod 8 k + 1. Vår sum for den første brøkdelen blir da

{\ displaystyle \ sum _ {k = 0}^{n} {\ frac {16^{nk} {\ bmod {(}} 8k+1)} {8k+1}}+\ sum _ {k = n +1}^{\ infty} {\ frac {16^{nk}} {8k+1}}.}

Legg merke til hvordan modulo -operatøren alltid garanterer at bare brøkbeløpet blir beholdt. For å beregne 16 ^{n - k} mod (8 k + 1) raskt og effektivt, brukes den modulære eksponentieringsalgoritmen . Når det løpende produktet blir større enn ett, tas modulen, akkurat som for løpende sum i hver sum.

For å fullføre beregningen må denne brukes på hver av de fire summene etter tur. Når dette er gjort, settes de fire summasjonene tilbake i summen til $π$ :

{\ displaystyle 4 \ Sigma _ {1} -2 \ Sigma _ {2}-\ Sigma _ {3}-\ Sigma _ {4}.}

Siden bare brøkdelen er nøyaktig, krever det å trekke ut ønsket siffer at man fjerner hele talldelen av den endelige summen og multipliserer med 16 for å "skumme av" det heksadesimale sifferet ved denne posisjonen (i teorien de neste sifrene opp til nøyaktigheten av beregningene som ble brukt, ville også være nøyaktige).

Denne prosessen ligner på å utføre lang multiplikasjon , men trenger bare å utføre summeringen av noen mellomkolonner. Selv om det er noen bær som ikke telles, utfører datamaskiner vanligvis aritmetikk for mange biter (32 eller 64) og runde, og vi er bare interessert i de mest betydningsfulle sifferene. Det er en mulighet for at en bestemt beregning vil ligne på å ikke legge til et lite tall (f.eks. 1) til tallet 999999999999999, og at feilen vil spre seg til det mest betydningsfulle sifferet.

BBP sammenlignet med andre beregningsmetoder $π$

Denne algoritmen beregner $π$ uten å kreve tilpassede datatyper som har tusenvis eller til og med millioner av sifre. Metoden beregner det n. Sifferet uten å beregne de første n - 1 -sifrene og kan bruke små, effektive datatyper.

Selv om BBP -formelen direkte kan beregne verdien av et gitt siffer på $π$ med mindre beregningsinnsats enn formler som må beregne alle mellomliggende sifre, forblir BBP lineæritmisk ( ), hvor større verdier av n etter hvert krever stadig mer tid å beregne; det vil si at "lengre ut" et siffer er, jo lengre tid tar det BBP å beregne det, akkurat som standard $π$ -databaserte algoritmer. ${\ displaystyle O (n \ logg n)}$

Generaliseringer

DJ Broadhurst gir en generalisering av BBP -algoritmen som kan brukes til å beregne en rekke andre konstanter i nesten lineær tid og logaritmisk plass. Resultater som er gitt for katalansk konstant , , , apery konstant , , (der er den Riemann zeta-funksjonen ), , , , og ulike produkter av krefter og . Disse resultatene oppnås først og fremst ved bruk av polylogaritmstiger . ${\ displaystyle \ pi ^{3}}$ ${\ displaystyle \ pi ^{4}}$ ${\ displaystyle \ zeta (3)}$ ${\ displaystyle \ zeta (5)}$ ${\ displaystyle \ zeta (x)}$ ${\ displaystyle \ log ^{3} 2}$ ${\ displaystyle \ log ^{4} 2}$ ${\ displaystyle \ log ^{5} 2}$ ${\ displaystyle \ pi}$ ${\ displaystyle \ log 2}$