Algoritmul spigot

Algoritmul spigot (numit și „algoritmul macaralei”, sau, mai precis, „algoritmul obturatorului” , deoarece funcționarea sa este similară cu mișcarea obturatorului unui automat care ejectează următorul cartuş) este un algoritm pentru calcularea valoarea constantelor matematice, de exemplu sau e , care permite determinarea cifrelor într-un sistem de numere preselectat (de obicei binar sau cu o bază sub forma unei puteri de doi) de la stânga la dreapta. Numele provine de la cuvântul englezesc „spigot”, adică robinet sau supapă pentru controlul fluxului de lichid. $\pi$

Interesul pentru algoritmul Spigot a crescut în timpul dezvoltării timpurii a matematicii computaționale din cauza restricțiilor severe asupra dimensiunilor memoriei. Primul astfel de algoritm pentru calcularea semnelor numărului e se găsește în lucrarea lui Arthur Sale (Arthur Harry John Sale) 1986 [1] . Denumirea „Spigot-algorithm” a fost cel mai probabil inventată de Stanley Rabinovich și Sten Wagon [2] .

Algoritmul propus de Rabinovich și Vagon este limitat în sensul că numărul de caractere de calculat trebuie determinat în prealabil. Jeremy Gibbons în 2004 introduce o generalizare numită „algoritm de streaming” [3] în care calculele pot fi efectuate pe termen nelimitat, eliminând astfel limitările algoritmului original. O altă îmbunătățire a algoritmului Spigot a fost un algoritm care vă permite să calculați un anumit semn fără a fi nevoie să determinați semnele anterioare ale unui număr. De exemplu, formula Bailey - Borwain - Pluff pentru calcularea caracterelor arbitrare într-o notație hexazecimală a unui număr . $\pi$

Exemplu

Să demonstrăm funcționarea algoritmului Spigot folosind exemplul de calcul al semnelor binare ale logaritmului natural 2 pe baza formulei:

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

Pentru a găsi cifrele binare începând cu a 8-a, înmulțiți numărul cu 27 (pentru că 7=8-1) :

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

Apoi împărțim seria infinită într-un „cap” în care puterea a doi este mai mare sau egală cu zero și o „coadă” cu puteri negative:

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

Ne interesează doar partea fracțională a acestei valori, așa că înlocuim fiecare termen din prima sumă („cap”) cu:

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

Calculăm fiecare termen separat, eliminând partea întreagă:

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

Să calculăm primele câteva elemente din „coadă”. Alegem o astfel de parte din această sumă încât eroarea de calcul să fie mai mică decât a șaptea cifră dorită a numărului.

k	D = 1 / k2k − 7	∑D _	Max. eroare
opt	1/16	1/16	1/16
9	1/36	13/144	1/36
zece	1/80	37/360	1/80

Rezumând „capul” și primele câteva elemente ale „cozii”, obținem:

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

deci cifrele de la 8 la 11 în binar sunt 1, 0, 1, 1. Rețineți că nu am calculat valorile celor șapte cifre anterioare. Informațiile despre aceste cifre au fost eliminate în mod deliberat atunci când se folosește aritmetica modulară la calcularea „capului”. $\ln(2)$

Această abordare poate fi utilizată pentru a calcula o a n- a cifră arbitrară în reprezentarea binară a numărului ln(2) . Numărul de termeni din „cap” crește liniar cu n , dar complexitatea elementelor de calcul crește logaritmic atunci când se utilizează metode de exponențiere modulo . Acuratețea calculului, calculele intermediare și numărul de termeni necesari din „coadă” nu depind de n , ci depind doar de numărul de caractere binare de calculat. Folosind numere fracționale cu precizie unică , aproximativ 12 cifre binare pot fi găsite indiferent de poziția de pornire.

Note

↑ Vânzare, AHJ. Calculul lui e la multe cifre semnificative // The Computer Journal : jurnal. - 1968. - Vol. 11 , nr. 2 . - P. 229-230 . - doi : 10.1093/comjnl/11.2.229 .
↑ Rabinowitz, Stanley; Căruță, Stan. A Spigot Algorithm for the Digits of Pi // American Mathematical Monthly : jurnal . - 1995. - Vol. 102 , nr. 3 . - P. 195-203 . - doi : 10.2307/2975006 .
↑ Gibbons, Jeremy Unbounded Spigot Algorithms for the Digits of Pi (24 mai 2004). Preluat la 9 decembrie 2019. Arhivat din original la 29 august 2008. (nedefinit)

Link -uri

Spigot Algorithm - de la Wolfram MathWorld - pagina Algoritm din catalogul MathWorld.
„Kranik”, sau un algoritm pentru găsirea cifrelor lui Pi , este un exemplu de utilizare a unui algoritm pentru calcularea semnelor . $\pi$