Algoritmus Ziggúratu Algoritmus Ziggúratu je algoritmus pro generovaní náhodných čísel ze spojitého rozdelení. Patří do třídy algoritmů pro generovaní náhodných čísel, které využívají podkladový zdroj rovnoměrně rozložených náhodných čísel, typicky z generátoru náhodných čísel s rovnoměrný rozložením, a také předpočítané tabulky. Algoritmus se používá k generovaní hodnot z monotonně klesajícího rozdelení pravděpodobnosti. Lze jej také použít na nesymetrická rozdelení, jako je normální rozdelení, výběrem hodnoty z jedné poloviny rozdelení a následnou volbou, ze které poloviny byla hodnota vybrána. Algoritmus vyvinul George Marsaglia a další v 60. letech 20. století. Typická hodnota vygenerovaná algoritmem vyžaduje pouze generovaní jednoho náhodného čísla s pohyblivou řádovou čárkou a jednoho náhodného indexu tabulky, po kterém následuje jedno vyhledání v tabulce, jedna operace násobení a jedno porovnání. Někdy (2,5 % času, v případě normálního nebo exponenciálního rozdelení při použití typických velikostí tabulky) jsou vyžadovány další výpočty. Algoritmus je však výpočetně podstatně rychlejší neż dva nejčastěji používaná metody generovaní náhodných čísel s normálním rozložením, polární metoda Marsaglia a Box-Müllerova trasformace, které vyžadují pro každý pár generovaných hodnot alespň jeden výpočtu dekadického algoritmu a jeden výpočtu druhé odmocniny. Vzhledem k tomu, že algoritmus Ziggúratu je však složitější na implementaci, nejlépe se používá, pokud je vyžadováno velké množství náhodných čísel. Termín algoritmus Ziggúratu pochází z článku Marsaglii s Wai Tsangem z roku 2000; je tak pojmenován, protože je koncepčně založen na pokrytí rozdelení pravděpodobnosti segmenty naskládanými v sestupném pořadí velikosti, což má za následek útvar, jenž připomíná zikkurat.
Facebook Twitter