Algoritmus čepu

Spigot-algorithm (také označovaný jako „algoritmus jeřábu“, nebo přesněji „algoritmus závěrky“ , protože jeho činnost je podobná pohybu závěrky automatu vysouvajícího další kazetu) je algoritmem pro výpočet hodnota matematických konstant, například nebo e , což umožňuje určit číslice v nějaké předem zvolené číselné soustavě (obvykle binární nebo se základem ve tvaru mocniny dvou) zleva doprava. Název pochází z anglického slova „spigot“, což znamená kohout nebo ventil pro řízení průtoku kapaliny. $\pi$

Zájem o Spigotův algoritmus vzrostl během raného vývoje výpočetní matematiky kvůli přísným omezením velikosti paměti. První takový algoritmus pro výpočet znamének čísla e se nachází v práci Arthura Salea (Arthur Harry John Sale) 1986 [1] . Název „Spigot-algorithm“ s největší pravděpodobností vytvořili Stanley Rabinovich a Sten Wagon [2] .

Algoritmus navržený Rabinovichem a Vagonem je omezený v tom smyslu, že počet znaků, které se mají vypočítat, musí být určen předem. Jeremy Gibbons v roce 2004 zavádí zobecnění nazvané „algoritmus proudění“ [3] , ve kterém lze výpočty provádět donekonečna, čímž se odstraní omezení původního algoritmu. Dalším vylepšením algoritmu Spigot byl algoritmus, který umožňuje vypočítat konkrétní znaménko, aniž byste museli určovat předchozí znaménka čísla. Například vzorec Bailey - Borwain - Pluff pro výpočet libovolných znaků v hexadecimálním zápisu čísla . $\pi$

Příklad

Ukažme si fungování Spigotova algoritmu na příkladu výpočtu binárních znamének přirozeného logaritmu 2 na základě vzorce:

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

Chcete-li najít binární číslice začínající od 8., vynásobte číslo 27 (protože 7=8-1) :

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

Potom rozdělíme nekonečnou řadu na „hlavu“, ve které je mocnina dvou větší nebo rovna nule, a „ocas“ se zápornými mocninami:

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

Zajímá nás pouze zlomková část této hodnoty, takže každý výraz v prvním součtu („hlava“) nahradíme:

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

Vypočítáme každý člen samostatně, přičemž zahodíme celočíselnou část:

k	A = 2 7 − k	B = A ( modk )	C = B / k	∑ C (mod 1)
jeden	64	0	0	0
2	32	0	0	0
3	16	jeden	1/3	1/3
čtyři	osm	0	0	1/3
5	čtyři	čtyři	4/5	2/15
6	2	2	1/3	7/15
7	jeden	jeden	1/7	64/105

Pojďme spočítat prvních pár prvků z "ocasu". Z tohoto součtu volíme takovou část, aby chyba výpočtu byla menší než požadovaná 7. číslice čísla.

k	D = 1 / k2k − 7	∑D _	Max. chyba
osm	1/16	1/16	1/16
9	1/36	13/144	1/36
deset	1/80	37/360	1/80

Shrneme-li „hlavu“ a několik prvních prvků „ocasu“, dostaneme:

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

takže číslice 8 až 11 v binárním tvaru jsou 1, 0, 1, 1. Všimněte si, že jsme nevypočítali hodnoty předchozích sedmi číslic. Informace o těchto číslech byly záměrně vyřazeny při použití modulární aritmetiky při výpočtu "hlavy". $\ln(2)$

Tento přístup lze použít k výpočtu libovolné n-té číslice v binární reprezentaci čísla ln(2) . Počet členů v "hlavě" roste lineárně s n , ale složitost výpočetních prvků roste logaritmicky při použití metod umocňování modulo . Přesnost výpočtu, mezivýpočty a počet nezbytných členů z "ocasu" nezávisí na n , ale závisí pouze na počtu binárních znaků, které se mají vypočítat. Pomocí zlomkových čísel s jednoduchou přesností lze najít asi 12 binárních číslic bez ohledu na počáteční pozici.

Poznámky

↑ Prodej, AHJ. Výpočet e na mnoho platných číslic // The Computer Journal : deník. - 1968. - Sv. 11 , č. 2 . - S. 229-230 . - doi : 10.1093/comjnl/11.2.229 .
↑ Rabinowitz, Stanley; Vagón, Stane. A Spigot Algorithm for the Digits of Pi // American Mathematical Monthly : journal . - 1995. - Sv. 102 , č. 3 . - S. 195-203 . - doi : 10.2307/2975006 .
↑ Gibbons, Jeremy Unbounded Spigot Algorithms for the Digits of Pi (24. května 2004). Získáno 9. prosince 2019. Archivováno z originálu dne 29. srpna 2008. (neurčitý)

Odkazy

Algoritmus čepu - od Wolframa MathWorld - strana algoritmu v katalogu MathWorld.
„Kranik“, neboli algoritmus pro nalezení číslic Pi , je příkladem použití algoritmu pro výpočet znamének . $\pi$