Spigot-algoritmi

Spigot-algoritmi (kutsutaan myös "nosturialgoritmiksi" tai tarkemmin sanottuna "suljinalgoritmiksi" , koska sen toiminta on samanlainen kuin seuraavan patruunan ulos työntävän automaatin sulkimen liike) on algoritmi, jolla lasketaan matemaattisten vakioiden arvo, esimerkiksi tai e , joka mahdollistaa numeroiden määrittämisen jossain esivalitussa numerojärjestelmässä (yleensä binäärissä tai kannassa kahden potenssin muodossa) vasemmalta oikealle. Nimi tulee englanninkielisestä sanasta "spigot", joka tarkoittaa hanaa tai venttiiliä nesteen virtauksen ohjaamiseen. $\pi$

Kiinnostus Spigot-algoritmia kohtaan kasvoi laskennallisen matematiikan varhaisen kehityksen aikana muistin koon vakavien rajoitusten vuoksi. Ensimmäinen tällainen algoritmi luvun e etumerkkien laskemiseen löytyy Arthur Salen (Arthur Harry John Sale) työstä 1986 [1] . Nimen "Spigot-algoritm" loivat todennäköisesti Stanley Rabinovich ja Sten Wagon [2] .

Rabinovichin ja Vagonin ehdottama algoritmi on rajoitettu siinä mielessä, että laskettavien merkkien määrä on määritettävä etukäteen. Jeremy Gibbons esitteli vuonna 2004 yleistyksen, jota kutsutaan "streaming-algoritmiksi" [3] , jossa laskelmia voidaan suorittaa loputtomiin, mikä poistaa alkuperäisen algoritmin rajoitukset. Toinen Spigot-algoritmin parannus oli algoritmi, jonka avulla voit laskea tietyn merkin ilman, että sinun tarvitsee määrittää luvun aiempia merkkejä. Esimerkiksi Bailey - Borwain - Pluff -kaava mielivaltaisten merkkien laskemiseen luvun heksadesimaalimuodossa . $\pi$

Esimerkki

Esitellään Spigot-algoritmin toiminta esimerkillä luonnollisen logaritmin 2 binäärimerkkien laskemisesta kaavan perusteella:

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

Löytääksesi binäärinumerot 8:sta alkaen, kerro luku 27: llä (koska 7=8-1) :

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

Sitten jaamme äärettömän sarjan "pääksi", jossa kahden potenssi on suurempi tai yhtä suuri kuin nolla, ja "häntään", jolla on negatiiviset potenssit:

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

Meitä kiinnostaa vain tämän arvon murto-osa, joten korvaamme jokaisen ensimmäisen summan ("pää") termillä:

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

Laskemme jokaisen termin erikseen, hylkäämme kokonaisluvun:

k	A = 2 7 − k	B = A ( modk )	C = B / k	∑ C (mod 1)
yksi	64	0	0	0
2	32	0	0	0
3	16	yksi	1/3	1/3
neljä	kahdeksan	0	0	1/3
5	neljä	neljä	4/5	2/15
6	2	2	1/3	7/15
7	yksi	yksi	1/7	64/105

Lasketaan ensimmäiset elementit "hännästä". Tästä summasta valitaan sellainen osa, että laskuvirhe on pienempi kuin luvun haluttu 7. numero.

k	D = 1 / k2k − 7	∑D_ _	Max. virhe
kahdeksan	1/16	1/16	1/16
9	1/36	13/144	1/36
kymmenen	1/80	37/360	1/80

Yhteenvetona "pää" ja "hännän" ensimmäiset elementit saadaan:

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

joten binääriluvut 8 - 11 ovat 1, 0, 1, 1. Huomaa, että emme ole laskeneet edellisten seitsemän numeron arvoja. Näitä lukuja koskevat tiedot hylättiin tarkoituksella käytettäessä modulaarista aritmetiikkaa "päätä" laskettaessa. $\ln(2)$

Tätä lähestymistapaa voidaan käyttää mielivaltaisen n:nnen numeron laskemiseen luvun ln(2) binääriesityksessä . Termien määrä "päässä" kasvaa lineaarisesti n: n kanssa , mutta laskentaelementtien monimutkaisuus kasvaa logaritmisesti käytettäessä modulo eksponentiomenetelmiä . Laskennan tarkkuus, välilaskelmat ja tarvittavien termien lukumäärä "hännästä" eivät riipu n :stä, vaan riippuvat vain laskettavien binäärimerkkien määrästä. Käyttämällä yhden tarkkuuden murtolukuja , noin 12 binäärinumeroa löytyy aloituspaikasta riippumatta.

Muistiinpanot

↑ Myynti, AHJ. E :n laskenta moniin merkitseviin numeroihin // Tietokonepäiväkirja : päiväkirja. - 1968. - Voi. 11 , ei. 2 . - s. 229-230 . - doi : 10.1093/comjnl/11.2.229 .
↑ Rabinowitz, Stanley; Wagon, Stan. Spigot Algorithm for the Digits of Pi // American Mathematical Monthly : Journal . - 1995. - Voi. 102 , no. 3 . - s. 195-203 . - doi : 10.2307/2975006 .
↑ Gibbons, Jeremy Rajoittamattomat Spigot Algorithms for the Digits of Pi (24. toukokuuta 2004). Haettu 9. joulukuuta 2019. Arkistoitu alkuperäisestä 29. elokuuta 2008. (määrätön)

Linkit

Spigot Algorithm - Wolfram MathWorldistä - Algoritmisivu MathWorld-luettelossa.
"Kranik" tai algoritmi Pi:n numeroiden löytämiseksi on esimerkki algoritmin käyttämisestä etumerkkien laskemiseen . $\pi$