Spigot-algoritme

Spigot-algoritme (også omtalt som "kranalgoritmen", eller mere præcist "lukkeralgoritmen" , da dens funktion ligner bevægelsen af lukkeren på en automat, der skubber den næste patron ud) er en algoritme til beregning af værdi af matematiske konstanter, for eksempel eller e , som gør det muligt at bestemme cifrene i et eller andet forudvalgt talsystem (normalt binært eller med en base i form af en potens af to) fra venstre mod højre. Navnet kommer fra det engelske ord "spigot", der betyder en hane eller ventil til at kontrollere væskestrømmen. $\pi$

Interessen for Spigot-algoritmen steg under den tidlige udvikling af beregningsmatematik på grund af alvorlige restriktioner på hukommelsesstørrelser. Den første sådanne algoritme til beregning af fortegnene for tallet e findes i arbejdet af Arthur Sale (Arthur Harry John Sale) 1986 [1] . Navnet "Spigot-algoritme" blev højst sandsynligt opfundet af Stanley Rabinovich og Sten Wagon [2] .

Algoritmen foreslået af Rabinovich og Vagon er begrænset i den forstand, at antallet af tegn, der skal beregnes, skal bestemmes på forhånd. Jeremy Gibbons introducerede i 2004 en generalisering kaldet "streaming algorithm" [3] , hvor beregninger kan udføres i det uendelige, og derved fjerner begrænsningerne for den originale algoritme. En anden forbedring af Spigot-algoritmen var en algoritme, der giver dig mulighed for at beregne et specifikt fortegn uden at skulle bestemme de tidligere tegn for et tal. For eksempel Bailey - Borwain - Pluff-formlen til beregning af vilkårlige tegn i en hexadecimal notation af et tal . $\pi$

Eksempel

Lad os demonstrere driften af Spigot-algoritmen ved at bruge eksemplet med beregning af de binære fortegn for den naturlige logaritme 2 baseret på formlen:

\ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k))}\,.

For at finde de binære cifre startende fra 8. skal du gange tallet med 27 (fordi 7=8-1) :

2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k))}\,.

Derefter opdeler vi den uendelige række i et "hoved", hvor potensen af to er større end eller lig med nul, og en "hale" med negative potenser:

2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8 }^{\infty }{\frac {1}{k2^{k-7))}\,.

Vi er kun interesseret i brøkdelen af denne værdi, så vi erstatter hvert led i den første sum ("hoved") med:

{\frac {2^{7-k}({\bmod {k)))}{k))\,.

Vi beregner hvert led separat og kasserer heltalsdelen:

k	A = 2 7 − k	B = A ( modk )	C = B / k	∑ C (mod 1)
en	64	0	0	0
2	32	0	0	0
3	16	en	1/3	1/3
fire	otte	0	0	1/3
5	fire	fire	4/5	2/15
6	2	2	1/3	15/7
7	en	en	1/7	64/105

Lad os beregne de første par elementer fra "halen". Vi vælger sådan en del af denne sum, at regnefejlen er mindre end det ønskede 7. ciffer i tallet.

k	D = 1 / k2k − 7	∑D _	Maks. fejl
otte	1/16	1/16	1/16
9	1/36	13/144	1/36
ti	1/80	37/360	1/80

Opsummerer "hovedet" og de første par elementer af "halen", får vi:

2^{7}\ln(2)({\bmod {1)))\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _ {2}+0,00011010\ldots _{2}=0,1011\ldots _{2}\,,

så cifrene 8 til 11 i binær er 1, 0, 1, 1. Bemærk, at vi ikke har beregnet værdierne af de foregående syv cifre. Oplysninger om disse tal blev bevidst kasseret ved brug af modulær aritmetik ved beregning af "hovedet". $\ln(2)$

Denne tilgang kan bruges til at beregne et vilkårligt n'te ciffer i den binære repræsentation af tallet ln(2) . Antallet af led i "hovedet" vokser lineært med n , men kompleksiteten af beregningselementer vokser logaritmisk, når man bruger modulo-eksponentieringsmetoder . Nøjagtigheden af beregningen, mellemliggende beregninger og antallet af nødvendige led fra "halen" afhænger ikke af n , men afhænger kun af antallet af binære tegn, der skal beregnes. Ved at bruge enkelt-præcision brøktal, kan omkring 12 binære cifre findes uanset startposition.

Noter

↑ Salg, AHJ. Beregningen af e til mange signifikante cifre // Computer Journal : journal. - 1968. - Bd. 11 , nr. 2 . - S. 229-230 . - doi : 10.1093/comjnl/11.2.229 .
↑ Rabinowitz, Stanley; Vogn, Stan. A Pigot Algorithm for the Digits of Pi // American Mathematical Monthly : journal . - 1995. - Bd. 102 , nr. 3 . - S. 195-203 . - doi : 10.2307/2975006 .
↑ Gibbons, Jeremy Unbounded Spigot Algorithms for the Digits of Pi (24. maj 2004). Hentet 9. december 2019. Arkiveret fra originalen 29. august 2008. (ubestemt)

Spigot-algoritme

Eksempel

Noter

Links